Farmer John은 사진 촬영을 위해 \(1\)번부터 \(N\)번까지 번호가 붙은 \(N\)마리의 소를 한 줄로 세우고 있다. \((2 \le N \le 1,000)\)

Farmer John은 처음에 왼쪽에서 \(i\)번째에 \(a_i\)번 소를 세울 계획이었고, 순열 \(a_1,a_2,\dots,a_N\)을 종이에 적어 두었다. 하지만 최근 Farmer Nhoj가 그 종이를 훔쳐 갔다!

다행히 Farmer John이 원래 적었던 순열을 복원할 수 있을지도 모른다. 종이를 도둑맞기 전에 Bessie는 모든 \(1 \le i < N\)에 대하여 \(b_i=a_i+a_{i+1}\)을 만족하는 수열 \(b_1,b_2,\dots,b_{N-1}\)을 기록해 두었다.

Bessie가 기록한 정보를 바탕으로 \(b\)를 만들 수 있는 순열 \(a\) 중 사전식으로 가장 작은 순열을 복원하라.

순열 \(x\)가 순열 \(y\)보다 사전식으로 작다는 것은, 어떤 \(j\)가 존재하여 모든 \(i<j\)에 대해 \(x_i=y_i\)이고 \(x_j<y_j\)임을 뜻한다. 다시 말해 두 순열은 어떤 위치까지 서로 같고, 처음으로 달라지는 위치에서 \(x\)의 원소가 \(y\)의 원소보다 작다.

조건을 만족하는 순열 \(a\)가 적어도 하나 존재함이 보장된다.

입력

첫째 줄에 정수 \(N\)이 주어진다.

둘째 줄에 \(N-1\)개의 정수 \(b_1,b_2,\dots,b_{N-1}\)이 공백으로 구분되어 주어진다.

출력

한 줄에 \(N\)개의 정수 \(a_1,a_2,\dots,a_N\)을 공백으로 구분하여 출력한다.

예제 입력 1

5
4 6 7 6

예제 출력 1

3 1 5 2 4

예제 설명 1

\(3+1=4\), \(1+5=6\), \(5+2=7\), \(2+4=6\)이므로 순열 \(a=(3,1,5,2,4)\)는 주어진 수열 \(b\)를 만든다.

출처

USACO 2020 January Contest, Bronze, Problem 2. Photoshoot