\begin{problem}{Преобразования звука}{input.txt}{output.txt}{1 секунда}

Трансформация дискретных волн - распространенный инструмент для компрессии звукового сигнала. 
В этой задаче ваша цель - написать программу, которая будет распаковывать сигнал (список целых чисел), который сжат простой волновой трансформацией.

Чтобы понять, как работает простая волновая трансформация, предположим, что у нас есть список целых чисел. 
Мы вычисляем сумму и разность каждой пары последовательно идущих чисел, занося результаты в 2 списка сумм и разностей, каждый из которых имеет длину в половину длины начального списка. 

Формально: 

оригинальный список - \emph{a(1), a(2), ..., a(n)}.

i-тая сумма \emph{s(i)} и разность \emph{d(i)} вычисляются следующим образом: \emph{s(i)=a(2*i-1)+a(2*i), d(i)=a(2*i-1)-a(2*i)} для i от 1 до n/2.

Затем идет перестроение - вначале записывается набор сумм, а затем - набор разностей. 

Например, если исходный сигнал имеет вид:

5, 2, 3, 2, 5, 7, 9, 6, то сигнал после преобразования будет иметь вид:

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

Затем этот же процесс применяется к первой половине трансформированного сигнала, и далее рекурсивно, пока длина сигнала вывода не станет равна 1. 
В нашем примере окончательно трансформированный сигнал такой:

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

Длина начального списка кратна степени 2, а каждое число в сигнале - это целое число от 0 до 255 (включительно).

\InputFile

Входной файл состоит из одной строки, которая начинается с целого числа N ($1 \le N \le 256$) - длины сигнала. 
Следующие N целых чисел - это значения закодированного сигнала. 

\OutputFile

Выходной файл должен содержать раскодированный сигнал (значения разделяются пробелами).

\Examples

\begin{example}%
\exmp{
8 39 -15 2 -3 3 1 -2 3
}{
5 2 3 2 5 7 9 6
}%
\exmp{
4 10 -4 -1 -1
}{
1 2 3 4
}%
\end{example}

\end{problem}
