离散微波变换是一种流行的信号压缩方式。现在，我们要你来写一个程序，以解压一条由简单微波变换压缩的一维信号（一列整数）。
为了理解这个简单微波变换如何工作，假设我们有一列整数。我们对于每一对连续采样计算其和与差，得出两个长度为原串一半的新的序列。一般地，如果原序列为
a[1],a[2],...,a[n]
那么第i个和s[i]及差d[i]计算方式如下：
for i = 1 to n/2 begin
s[i]=a[$2*i-1$]+a[$2*i$];
d[i]=a[$2*i-1$]-a[$2*i$];
end;
然后把两个序列组合起来，得出转换后的信号。例如，如果输入信号为：
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<=N<=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