700. Remove nodes from Binary Search Tree

0

Medium

Given an array A1 of integers, you need to construct a Binary Search Tree (BST) using the elements of A1. Then, you are given another array A2. Your task is to delete each node from the BST that is present in A2. Finally, print the preorder traversal of the resulting tree. It is guaranteed that the elements of A2 will be present in the tree.

Note: If a node has two children, consider its inorder successor as its replacement.

Note: If a node has two children, consider its inorder successor as its replacement.

Input Format

The first line contains an integer t, which represents the number of test cases.

Each test case consists of four lines. The first line contains an integer n, which represents the length of array A1. The next line contains n space-separated integers denoting the elements of A1. Similarly, the third line contains an integer m, which represents the length of array A2. The next line contains m space-separated integers denoting the elements of A2.

Each test case consists of four lines. The first line contains an integer n, which represents the length of array A1. The next line contains n space-separated integers denoting the elements of A1. Similarly, the third line contains an integer m, which represents the length of array A2. The next line contains m space-separated integers denoting the elements of A2.

Output Format

Print the preorder traversal of the final resultant tree.

Example

Input

1
7
5 3 2 4 7 6 8
3
2 3 5

Output

6 4 7 8

Constraints

1 < t < 100

1< n,m < 1000

1< n,m < 1000

Loading...

View Submissions

Console