Guess Permutation

3.5

8 votes
, Binary Search, Algorithms, Linear Search
Problem

A permutation of length N is an array of N integers such that every integer from 1 to N appears exactly once. For example, [2,3,5,4,1] is a permutation of length 5, while [1,2,2],[4,5,1,3] are not permutations.

For a given array B of length N+1, the difference array is an array A of length N such that Ai=Bi+1Bi for each 1iN. For example, the difference array of the array [3,7,5,1,4] is [4,2,4,3].

Alice gives you an array A of length N. Find a permutation P of length (N+1) such that the difference array of the permutation P and the given array A are equal. Print 1 if no such permutation exists.

Input format

  • The first line of input contains an integer T denoting the number of test cases. The description of each test case is as follows:
  • The first line of each test case contains an integer N denoting the length of the permutation.
  • The second line of each test case contains N integers A1,A2,,AN, denoting the elements of the array A.

Output format

For each test case, print 1 if no suitable permutation exists or print N+1 space-separated integer denoting the elements of the permutation.

Constraints

1T1051N3105NAiNSum of N over all test cases does not exceed 3105.

Sample Input
2
4
2 -4 3 -2
3
3 -1 2
Sample Output
3 5 1 4 2
-1
Time Limit: 1
Memory Limit: 256
Source Limit:
Explanation

In the first test case, the difference array of the permutation [3,5,1,4,2] is [2,4,3,2] which is equal to the array A.

In the second test case, there is no permutation of length 4 for which the difference array is equal to the array A.

Editor Image

?