P10033 "Cfz Round 3" Sum of Permutation

**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.

**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$.

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.**

#### "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