CF2220A.Blocked

Given an array $ a $ of integers of size $ n $ , we say that a position $ 1 \le i \le n $ is blocked if $ a_i $ can be expressed as the sum of a subset of $ a_1, a_2, \ldots, a_{i-1} $ (i.e. there exist $ 1 \le j_1 \lt j_2 \lt \ldots \lt j_k \le i-1 $ such that $ a_{j_1} + a_{j_2} + \ldots + a_{j_k} = a_i $ ). Reorder $ a $ so that no position is blocked or report that it is impossible.

For example, reordering the array [ $ 3, 2, 5 $ ] to [ $ 2, 3, 5 $ ] makes position $ 3 $ blocked, since we can express $ 5 = 2 + 3 $ , but if we reorder it to [ $ 3, 5, 2 $ ], no position is blocked.

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \le t \le 400 $ ). The description of the test cases follows.

The first line of each test case contains an integer $ n $ ( $ 1 \le n \le 200 $ ).

The second line contains $ n $ integers, denoting the array $ a $ ( $ \textbf{1} \le a_i \le 100 $ ).

For each test case, print any order of $ a $ such that no position is blocked if it exists, otherwise print $ -1 $ .

In the third test case, the array [ $ 3, 1, 2 $ ] has no position blocked:

Position $ 1 $ is not blocked since $ 3 $ can't be expressed as the sum of a subset of [].

Position $ 2 $ is not blocked since $ 1 $ can't be expressed as the sum of a subset of [ $ 3 $ ].

Position $ 3 $ is not blocked since $ 2 $ can't be expressed as the sum of a subset of [ $ 3, 1 $ ].