现在灰狼与蔷薇请你写一个程序，来解压一个被一种简单的 jsoi 压缩技术压缩过的一串 信号（一列数）。考虑我们有一列包含偶数个数字的数列，将其分成 n/2 组，计算出每组两 个数的和与差，分别写成两列长度为原来一半的数，如数列：a(1),a(2)……a(n) For i=1,2……n/2，s(i)=a(2i-1)+a(2i)，d(i)=a(2i-1)-a(2i)。 如输入信号为：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

以同样的方式对变换后的信号的前半段（即以 s(i)为输入信号）作变换，如此循环，直 到输入信号的长度为 1 为止，这样变换之后，原来的输入信号就变成了：39,-15,2,-3,3,1,-2,3。 你可以假定输入信号的长度一定是 2n，并且每个数字信号的范围都在 0~255 之间。

Input

输入文件 wavelet.in 包括多组测试数据（不多于 900 组）。 每组数据首先包括一个数字 n（1≤n≤256）表示压缩后的信号长度。接下来 n 个数字， 表示压缩后的信号。 一行单独的 0 表示输入文件结束。 Output

输出文件 wavelet.out 每组数据输出一行，表示原来的输入信号，共 n 个数，每两 个数之间用一个空格隔开。 Sample

wavelet.in wavelet.out

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

Data

(X*10)%的数据：n≤2^(X-1) (X = 1,2,…,9) 100%的数据：n≤256

对于 C++选手，为防止输入输出时间过长，建议： 读入一个 int 类型整数 a 使用 scanf(“%d”,&a); 输出一个 int 类型整数 a使用 printf(“%d”,a);

输出一个空格使用 printf(“ “); 输出一个回车使用 printf(“\n”); 这道题