Given a permutation $p$ of $1 \sim n$.

You need to construct a sequence $a$ of length $n$ such that:

• Each element in sequence $a$ is a positive integer no greater than $n$;
• There exists no ordered pair of integers $(l, r)$ such that $1 \le l \le r \le n$ and $\sum\limits_{i=l}^r a_i = \sum\limits_{i=l}^r p_i$;

Or report that no such sequence exists.

A permutation of $1 \sim n$ is a sequence where every positive integer no greater than $n$ appears exactly once.

Input

This problem contains multiple test cases.

The first line contains an integer $T$, representing the number of test cases.

The following lines contain the test cases. For each test case:

• The first line contains an integer $n$.
• The second line contains $n$ integers, representing the given permutation $p$.

Output

For each test case, output one line:

• If a sequence $a$ satisfying the conditions exists, output $n$ space-separated integers representing the constructed sequence $a$;
• If no such sequence $a$ exists, output $-1$.

Any valid output will be accepted.

Examples

Input 1

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

Output 1

1 3 3
-1
5 3 2 1 1
2 3 5 4 6 3 1

Note 1

For the first test case, both $\{1, 3, 3\}$ and $\{1, 1, 3\}$ are valid sequences $a$.

For the second test case, it can be proven that no such sequence $a$ exists.

For the third test case, besides $\{5, 3, 2, 1, 1\}$, sequences such as $\{3, 4, 5, 3, 2\}$, $\{1, 4, 5, 3, 4\}$, and $\{5, 3, 3, 4, 5\}$ are also valid sequences $a$.

Constraints

Let $\sum n$ denote the sum of $n$ over all test cases.

For all data, $1 \le T \le 5000$, $2 \le n \le 10^6$, $\sum n \le 10^6$, and $p$ is guaranteed to be a permutation of $1 \sim n$.