#P7485. [2017年杭电多校]Rikka with Subset

    ID: 7498 传统题 1000ms 256MiB 尝试: 1 已通过: 1 难度: 5 上传者: 标签>CF1700普及+/提高-逆向还原操作极端元素优先处理线性 DP

[2017年杭电多校]Rikka with Subset

Rikka with Subset

Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them: Yuta has nn positive A1−AnA_1-A_n and their sum is mm. Then for each subset SS of AA, Yuta calculates the sum of SS. Now, Yuta has got 2n2^n numbers between [0,m][0,m]. For each i∈[0,m]i \in [0,m], he counts the number of iis he got as BiB_i. Yuta shows Rikka the array BiB_i and he wants Rikka to restore A1−AnA_1-A_n. It is too difficult for Rikka. Can you help her?

Input

The first line contains a number t(1≤t≤70)t(1 \leq t \leq 70), the number of the testcases. For each testcase, the first line contains two numbers n,m(1≤n≤50,1≤m≤104)n,m(1 \leq n \leq 50,1 \leq m \leq 10^4). The second line contains m+1m+1 numbers B0−Bm(0≤Bi≤2n)B_0-B_m(0 \leq B_i \leq 2^n).

Output

For each testcase, print a single line with nn numbers A1−AnA_1-A_n. It is guaranteed that there exists at least one solution. And if there are different solutions, print the lexicographic minimum one.

Sample Input

2
2 3
1 1 1 1
3 3
1 3 3 1

Sample Output

1 2
1 1 1

Hint

In the first sample, AA is [1,2][1,2]. AA has four subsets [],[1],[2],[1,2][],[1],[2],[1,2] and the sums of each subset are 0,1,2,30,1,2,3. So B=[1,1,1,1]B=[1,1,1,1]

Source

2017 Multi-University Training Contest - Team 5

https://acm.hdu.edu.cn/showproblem.php?pid=6092