Serialization is the process of translating a data structure or object state into a format that can be stored (for example, in a file or memory data buffer) or transmitted (for example, over a computer network) and reconstructed later (possibly in a different computer environment).

The opposite operation, extracting a data structure from a series of bytes, is deserialization.

Design an algorithm to serialize and deserialize a BST.

• The serialize method should return a string. The format of the string does not matter. Try to keep it as compact as possible to avoid getting TLE/MLE.
• The deserialize method when provided the serialized string should return the original BST.

Testing

Input Format

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

For each test case, the input has 2 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.

Output Format

For each test case, the output has two lines containing the level order traversal of the tree. The traversal will be printed only if both the trees are identical.

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

Expected Output

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

Constraints

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