A binary tree can be converted into a doubly linked list (DLL) whose traversal will give the tree's inorder traversal.

Use the left and right pointers of a tree node as previous and next pointers respectively in the DLL.

Given the root node, convert the binary tree into a doubly linked list, in-place. Return the head of the DLL.

Testing

Input Format

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

For each test case, the input has two 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 tree. The integers follow level order traversal of the tree where -1 indicates a NULL node.

Output Format

For each test case, the output contains a line with space-separated integers representing each element of the doubly linked list.

Sample Input

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

Expected Output

5 4 6 2 1
6 4
15 8 9 11 10 12
14 48 28 11

1 <= T <= 10
1 <= n <= 2*104
1 <= node value <= 109