G. Binary Tree Traversal
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an array $$$a$$$ of size $$$n$$$, and an integer $$$r$$$.

Your task is to find a binary tree of size $$$n$$$ satisfying:

  • The binary tree is rooted at $$$r$$$.
  • For every node $$$i$$$ from $$$1$$$ to $$$n$$$, $$$a_i$$$ is the last traversed node in the subtree of node $$$i$$$ using In-order Traversal.

You need to output the In-order Traversal sequence of this binary tree. If there can be multiple possible answers, output any. If there is no such binary tree, output $$$-1$$$ instead.

Input

The first line of input contains $$$t$$$, the number of test cases $$$(1\le t\le 10^4)$$$.

For each testcase:

  • The first line of input contains $$$n$$$ and $$$r(1\le r\le n\le 2 \cdot 10^5)$$$, the number of nodes in the binary tree and the root of the binary tree.
  • The next line contains $$$n$$$ integers $$$a_1,a_2,...a_n$$$, where $$$a_i$$$ is the last node traversed in the subtree of node $$$i$$$ using In-order Traversal.

The sum of $$$n$$$ over all test cases doesn't exceed $$$2\cdot10^5$$$.

Output

For each test case, you have to output a sequence of $$$n$$$ integers — the In-order Traversal sequence of this binary tree. Since there can be multiple possible answers, output any. If there is no such tree, output $$$-1$$$ instead.

Example
Input
4
5 1
2 2 3 3 5
4 1
1 2 3 4
4 2
4 4 4 4
2 2
2 1
Output
5 1 4 3 2
3 2 4 1
2 3 1 4
-1
Note

In the first test case, the binary tree is as follows:

We can see that node $$$1$$$ is the root and for each testcase:

  • for node $$$1$$$ , the last traversed node is $$$2$$$.
  • for node $$$2$$$ , the last traversed node is $$$2$$$.
  • for node $$$3$$$ , the last traversed node is $$$3$$$.
  • for node $$$4$$$ , the last traversed node is $$$3$$$.
  • for node $$$5$$$ , the last traversed node is $$$5$$$.

In the fourth test case, it can be shown that there exists no valid binary tree.