Rami has n points that lie on the non-negative part of the x-axis. One of the points is always at 0. He wrote down the distances between each pair of points in some arbitrary order.
Asem accidentally erased Rami's points, and he wants to restore them before Rami finds out. Can you help Asem restore the coordinates of the points?
The first line of the input contains an integer T the number of the test cases.
Each case contains two lines. The first line contains an integer n (2 ≤ n ≤ 18), the number of points Rami has.
The second line contains m integers d1, d2, ..., dm (0 ≤ di ≤ 106), where m = , the distances between each pair of points.
Print T lines. Each line contains n integers p1, p2, ..., pn which represent the coordinates of the points in ascending order.
It is guaranteed that an answer always exists. If there is more than one solution, you can print any of them.
## Input
The first line of the input contains an integer T the number of the test cases.Each case contains two lines. The first line contains an integer n (2 ≤ n ≤ 18), the number of points Rami has.The second line contains m integers d1, d2, ..., dm (0 ≤ di ≤ 106), where m = , the distances between each pair of points.
## Output
Print T lines. Each line contains n integers p1, p2, ..., pn which represent the coordinates of the points in ascending order.It is guaranteed that an answer always exists. If there is more than one solution, you can print any of them.
[samples]
**Definitions**
Let $ T \in \mathbb{Z} $ be the number of test cases.
For each test case:
- Let $ n \in \mathbb{Z} $, $ 2 \leq n \leq 18 $, be the number of points on the non-negative x-axis, one of which is at 0.
- Let $ D = \{d_1, d_2, \dots, d_m\} $ be the multiset of pairwise distances, where $ m = \binom{n}{2} $.
**Constraints**
1. $ 1 \leq T \leq \text{unspecified} $
2. For each test case:
- $ 2 \leq n \leq 18 $
- $ m = \binom{n}{2} $
- $ 0 \leq d_i \leq 10^6 $ for all $ d_i \in D $
- The multiset $ D $ is generated from some set of points $ P = \{p_1, p_2, \dots, p_n\} \subset \mathbb{R}_{\geq 0} $ with $ p_1 = 0 $ and $ p_1 < p_2 < \dots < p_n $.
**Objective**
Reconstruct the sorted point set $ P = \{p_1, p_2, \dots, p_n\} $ with $ p_1 = 0 $, such that the multiset of pairwise distances $ \{ |p_i - p_j| \mid 1 \leq i < j \leq n \} $ equals $ D $.