Problem Description

Please note the special time limit of this problem.

You are given a permutation $p$ of $1 \sim n$.

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

• Every element in sequence $a$ is a positive integer not greater than $n$.
• There does not exist an ordered integer pair $(l,r)$ satisfying $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 there is no solution.

A permutation of $1 \sim n$ means a sequence in which every positive integer not greater than $n$ appears exactly once.

Input Format

This problem has multiple test cases.

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

Then each test case is given as follows:

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

Output Format

For each test case, output one line:

• If there exists a sequence $a$ that satisfies the conditions, output $n$ integers separated by spaces, representing the sequence $a$ you constructed.
• If no such sequence $a$ exists, output $-1$.

Any output that meets the requirements will be accepted.

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

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

Hint

"Sample Explanation #1"

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

For the $2$-nd test case, it can be proven that no valid sequence $a$ exists.

For the $3$-rd test case, besides $\{5,3,2,1,1 \}$, $\{3,4,5,3,2 \}$, $\{1,4,5,3,4 \}$, $\{5,3,3,4,5\}$, etc. are all valid sequences $a$.

Constraints

Let $\sum n$ denote the sum of $n$ within a single test.

For all testdata, $1 \le T \le 5000$, $2 \le n \le 10^6$, $\sum n \le 10^6$. It is guaranteed that $p$ is a permutation of $1 \sim n$.

You can get the score for this problem only if you pass all test points.

The input and output size is large, so please use fast I/O.

Translated by ChatGPT 5