311284: CF1965D. Missing Subarray Sum

D. Missing Subarray Sumtime limit per test5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

There is a hidden array $a$ of $n$ positive integers. You know that $a$ is a palindrome, or in other words, for all $1 \le i \le n$, $a_i = a_{n + 1 - i}$. You are given the sums of all but one of its distinct subarrays, in arbitrary order. The subarray whose sum is not given can be any of the $\frac{n(n+1)}{2}$ distinct subarrays of $a$.

Recover any possible palindrome $a$. The input is chosen such that there is always at least one array $a$ that satisfies the conditions.

An array $b$ is a subarray of $a$ if $b$ can be obtained from $a$ by the deletion of several (possibly, zero or all) elements from the beginning and several (possibly, zero or all) elements from the end.

Input

The first line of the input contains a single integer $t$ ($1 \le t \le 200$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($3 \le n \le 1000$) — the size of the array $a$.

The next line of each test case contains $\frac{n(n+1)}{2} - 1$ integers $s_i$ ($1\leq s_i \leq 10^9$) — all but one of the subarray sums of $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $1000$.

Additional constraint on the input: There is always at least one valid solution.

Hacks are disabled for this problem.

Output

For each test case, print one line containing $n$ positive integers $a_1, a_2, \cdots a_n$ — any valid array $a$. Note that $a$ must be a palindrome.

If there are multiple solutions, print any.

ExampleInput

7
3
1 2 3 4 1
4
18 2 11 9 7 11 7 2 9
4
5 10 5 16 3 3 13 8 8
4
8 10 4 6 4 20 14 14 6
5
1 2 3 4 5 4 3 2 1 1 2 3 2 1
5
1 1 2 2 2 3 3 3 3 4 5 5 6 8
3
500000000 1000000000 500000000 500000000 1000000000

Output

1 2 1 
7 2 2 7 
3 5 5 3 
6 4 4 6 
1 1 1 1 1 
2 1 2 1 2 
500000000 500000000 500000000 

Note

For the first example case, the subarrays of $a = [1, 2, 1]$ are:

• $[1]$ with sum $1$,
• $[2]$ with sum $2$,
• $[1]$ with sum $1$,
• $[1, 2]$ with sum $3$,
• $[2, 1]$ with sum $3$,
• $[1, 2, 1]$ with sum $4$.

So the full list of subarray sums is $1, 1, 2, 3, 3, 4$, and the sum that is missing from the input list is $3$.

For the second example case, the missing subarray sum is $4$, for the subarray $[2, 2]$.

For the third example case, the missing subarray sum is $13$, because there are two subarrays with sum $13$ ($[3, 5, 5]$ and $[5, 5, 3]$) but $13$ only occurs once in the input.

题目大意：
给定一个由n个正整数组成的隐藏数组a，并且知道a是一个回文数组，即对于所有1≤i≤n，都有ai=an+1-i。给出了除了一个不同的子数组的和之外的所有不同子数组的和，这个未给出的子数组的和可以是a的任意一个不同的子数组。需要恢复出任何一个可能的回文数组a。输入保证至少存在一个满足条件的数组a。

输入数据格式：
第一行包含一个整数t（1≤t≤200），表示测试用例的数量。接下来是每个测试用例的描述。
每个测试用例的第一行包含一个整数n（3≤n≤1000），表示数组a的大小。
接下来的一行包含n(n+1)/2-1个整数si（1≤si≤109），表示除了一个未给出的子数组的和之外的所有子数组的和。
保证所有测试用例的n之和不超过1000。
输入数据还保证至少存在一个有效的解决方案。

输出数据格式：
对于每个测试用例，输出一行包含n个正整数a1,a2,...,an，表示一个有效的回文数组a。如果有多个解决方案，输出其中任意一个。

示例：
输入：
7
3
1 2 3 4 1
4
18 2 11 9 7 11 7 2 9
4
5 10 5 16 3 3 13 8 8
4
8 10 4 6 4 20 14 14 6
5
1 2 3 4 5 4 3 2 1 1 2 3 2 1
5
1 1 2 2 2 3 3 3 3 4 5 5 6 8
3
500000000 1000000000 500000000 500000000 1000000000

输出：
1 2 1
7 2 2 7
3 5 5 3
6 4 4 6
1 1 1 1 1
2 1 2 1 2
500000000 500000000 500000000

注意：
对于第一个示例，数组a=[1, 2, 1]的所有子数组的和为1, 1, 2, 3, 3, 4，输入列表中缺失的和是3。
对于第二个示例，缺失的和是4，对应子数组[2, 2]。
对于第三个示例，缺失的和是13，因为有两个子数组的和为13（[3, 5, 5]和[5, 5, 3]），但输入中只出现了一次。题目大意： 给定一个由n个正整数组成的隐藏数组a，并且知道a是一个回文数组，即对于所有1≤i≤n，都有ai=an+1-i。给出了除了一个不同的子数组的和之外的所有不同子数组的和，这个未给出的子数组的和可以是a的任意一个不同的子数组。需要恢复出任何一个可能的回文数组a。输入保证至少存在一个满足条件的数组a。 输入数据格式： 第一行包含一个整数t（1≤t≤200），表示测试用例的数量。接下来是每个测试用例的描述。 每个测试用例的第一行包含一个整数n（3≤n≤1000），表示数组a的大小。 接下来的一行包含n(n+1)/2-1个整数si（1≤si≤109），表示除了一个未给出的子数组的和之外的所有子数组的和。 保证所有测试用例的n之和不超过1000。 输入数据还保证至少存在一个有效的解决方案。 输出数据格式： 对于每个测试用例，输出一行包含n个正整数a1,a2,...,an，表示一个有效的回文数组a。如果有多个解决方案，输出其中任意一个。 示例： 输入： 7 3 1 2 3 4 1 4 18 2 11 9 7 11 7 2 9 4 5 10 5 16 3 3 13 8 8 4 8 10 4 6 4 20 14 14 6 5 1 2 3 4 5 4 3 2 1 1 2 3 2 1 5 1 1 2 2 2 3 3 3 3 4 5 5 6 8 3 500000000 1000000000 500000000 500000000 1000000000 输出： 1 2 1 7 2 2 7 3 5 5 3 6 4 4 6 1 1 1 1 1 2 1 2 1 2 500000000 500000000 500000000 注意： 对于第一个示例，数组a=[1, 2, 1]的所有子数组的和为1, 1, 2, 3, 3, 4，输入列表中缺失的和是3。 对于第二个示例，缺失的和是4，对应子数组[2, 2]。 对于第三个示例，缺失的和是13，因为有两个子数组的和为13（[3, 5, 5]和[5, 5, 3]），但输入中只出现了一次。