CF2254E Chronostasis

Yousef has a hidden array $ a $ of length $ n $ consisting entirely of strictly positive integers. An operation was performed exactly once to create an array $ b $ : - Set $ b_1 = a_1 $ . - For every $ i $ from $ 2 $ to $ n $ , set $ b_i = a_i - a_{i-1} $ . - After this, the elements of $ b $ were completely shuffled. You are given the shuffled array $ b $ . Reconstruct the lexicographically smallest original array $ a $ . If it's impossible for any arrangement of $ b $ to produce an array $ a $ of strictly positive integers, output $ -1 $ .

The first line of input contains an integer $ t $ ( $ 1 \le t \le 10^4 $ ) — the number of test cases. The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 2 \cdot 10^5 $ ) — the size of the array. The second line of each test case contains $ n $ integers $ b_1, b_2, \dots, b_n $ ( $ -10^9 \le b_i \le 10^9 $ ) — the elements of the shuffled array $ b $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

For each test case, output $ n $ strictly positive integers $ a_1, a_2, \dots, a_n $ ( $ a_i \ge 1 $ ) — the lexicographically smallest original array $ a $ . If it's impossible to create a valid array $ a $ , output $ -1 $ instead.

In the first test case, the only valid array is $ a = [5] $ . In the second test case, there is no valid arrangement of the elements of $ b $ that reconstructs an array $ a $ consisting entirely of strictly positive integers. Therefore, the answer is $ -1 $ . In the third test case, one valid arrangement reconstructs the array $ a=[1,1,3,2,6,3] $ . The resulting sequence of differences $ [1, 0, 2, -1, 4, -3] $ is a permutation of the given array $ b $ , and among all valid reconstructions, this array is lexicographically smallest.