题目翻译

描述

离散小波变换是信号压缩的常用工具。在这个问题中，你的任务是编写一个程序，对通过简单小波变换压缩的一维信号（整数列表）进行解压缩。

为了理解这种简单小波变换的工作原理，假设我们有一个偶数个整数的列表。我们计算每对连续样本的和与差，得到两个分别包含和与差的列表，每个列表的长度是原始长度的一半。形式上，如果原始样本是：

a(1), ..., a(n)

对于 $i = 1, \ldots, n/2$，第 $i$个和 $s(i)$与差 $d(i)$ 计算如下：

s(i) = a(2*i-1) + a(2*i)
d(i) = a(2*i-1) - a(2*i)

然后，通过先列出和，再列出差，重新排列得到变换后的信号。例如，输入信号为：

5, 2, 3, 2, 5, 7, 9, 6

则和与差信号为：

s(i) = 7, 5, 12, 15
d(i) = 3, 1, -2, 3

因此，变换后的信号是：

7, 5, 12, 15, 3, 1, -2, 3

对变换后的信号的前半部分（即和的部分）递归应用相同的过程，直到输入信号的长度为$1$。在上面的例子中，最终的变换信号是：

39, -15, 2, -3, 3, 1, -2, 3

假设原始输入的长度是$2$的幂，输入信号仅包含$0$到$255$（含）之间的整数。

输入

输入包含多个测试用例。每个测试用例在一行中指定，以整数 $N$（$1 \leq N \leq 256$）开头，表示样本数量。接下来的 $N$ 个整数是变换后的样本。输入以 $N = 0$ 的情况结束。

输出

对于每个测试用例，在一行上输出原始样本，用单个空格分隔。

输入数据示例

8 39 -15 2 -3 3 1 -2 3
4 10 -4 -1 -1
0

输出数据示例

5 2 3 2 5 7 9 6
1 2 3 4

来源

落基山地区 2007年