웨이블릿 압축

이산 웨이블릿 변환은 신호 압축에 널리 쓰이는 도구입니다. 이 문제에서는 아래에 설명하는 간단한 웨이블릿 변환으로 압축된 1차원 신호(정수 목록)를 복원하는 프로그램을 작성합니다.

이 간단한 웨이블릿 변환이 어떻게 동작하는지 살펴봅시다. 짝수 개의 정수로 이루어진 목록이 있다고 합시다. 이웃한 두 표본마다 합과 차를 구하면, 각각 원래 길이의 절반인 합 목록과 차 목록이 만들어집니다. 원래 표본이

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

일 때, $i = 1, \dots, n/2$ 에 대해 $i$번째 합 $s(i)$ 와 차 $d(i)$ 는 다음과 같습니다.

$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

입니다. 그런 다음 같은 과정을 변환된 신호의 앞쪽 절반(합 부분)에 재귀적으로 적용하며, 이때 그 합들을 새로운 입력 신호로 취급합니다. 변환하는 신호의 길이가 1이 될 때까지 이 과정을 반복합니다. 위 예에서 최종 변환된 신호는

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

입니다. 원래 신호의 길이는 2의 거듭제곱이며, 원래 표본은 모두 0 이상 255 이하의 정수입니다. 변환된 신호가 주어질 때 원래 표본을 복원하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스는 한 줄에 주어지며, 표본의 개수를 나타내는 정수 $N$ ($1 \le N \le 256$, 2의 거듭제곱)으로 시작하고 그 뒤에 변환된 표본 $N$개가 이어집니다. 입력의 끝은 $N = 0$인 줄로 표시되며, 이 줄은 처리하지 않습니다.

각 테스트 케이스마다 원래 표본을 한 줄에 공백 하나로 구분하여 출력합니다.