Wavelet Compression

The discrete wavelet transform is a popular tool for signal compression. Your task is to decompress a one-dimensional signal (a list of integers) that was compressed by the simple wavelet transform described below.

To see how this simple wavelet transform works, suppose we have a list containing an even number of integers. We compute the sum and the difference of each pair of consecutive samples, producing a list of sums and a list of differences, each half the original length. Formally, if the original samples are

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

then for $i = 1, \dots, n/2$ the $i$-th sum $s(i)$ and difference $d(i)$ are

$$s(i) = a(2i-1) + a(2i)$$

$$d(i) = a(2i-1) - a(2i)$$

The transformed signal is formed by listing all the sums first, followed by all the differences. For instance, if the input signal is

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

then the sums and differences are

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

so the transformed signal is

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

The same process is then applied recursively to the first half of the transformed signal (the sums), treating those sums as a new input signal, and it continues until the signal being transformed has length 1. For the example above, the final transformed signal is

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

The length of the original signal is a power of 2, and every original sample is an integer between 0 and 255 inclusive. Given a transformed signal, recover the original samples.

The input consists of several test cases. Each test case is given on its own line: it begins with an integer $N$ ($1 \le N \le 256$, a power of 2) giving the number of samples, followed by the $N$ transformed samples. The input ends with a line containing $N = 0$, which is not processed.

For each test case, print the original samples on a single line, separated by single spaces.