Given the root node of a binary search tree and a key, return the subtree rooted at the node containing the key. If it does not exist, return null.

Note: The tree contains only unique values.

Example

Testing

Input Format

The first line contains an integer T denoting the number of test cases.

For each test case, the input has 3 lines:

• The first line contains an integer n denoting the number of nodes in the tree (including the NULL nodes).
• The second line contains n space-separated integers that will form the binary search tree. The integers follow level order traversal of the tree where -1 indicates a NULL node.
• The third line contains the key value to be searched.

Output Format

For each test case, the output has a line containing the level order traversal of the subtree.

Sample Input

4
9
2 1 3 -1 -1 -1 5 4 7
2
12
6 2 9 1 5 8 -1 -1 -1 4 -1 7
2
12
8 3 9 -1 4 -1 10 -1 -1 -1 12 11
11
4
28 14 -1 11
0

Expected Output

2 1 3 5 4 7 
2 1 5 4 
11 

Constraints

1 <= T <= 10
1 <= n <= 104
1 <= node value <= 104