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 $ \].