Farmer John은 번호가 $1\ldots N$인 $N$마리의 소 ($2\le N\le 10^3$)를 사진 촬영을 위해 줄 세운다. FJ는 왼쪽에서 $i$번째 소를 번호 $a_i,$인 소로 정하고 순열 $a_1,a_2,\ldots,a_N$을 종이에 적었다. 안타깝게도 최근 Farmer Nhoj가 그 종이를 훔쳤다!

다행히 FJ는 원래 적은 순열을 복원할 수 있을지도 모른다. 도둑맞기 전에 Bessie는 모든 $1\le i<N.$에 대해 $b_i=a_i+a_{i+1}$을 만족하는 수열 $b_1,b_2,\ldots,b_{N-1}$을 기록했다.

Bessie의 정보로 $b$를 만들 수 있는 “사전순으로 가장 작은” 순열 $a$를 복원하라. 어떤 $j$에 대해 모든 $i<j$에서 $x_i=y_i$이고 $x_j<y_j$이면 순열 $x$가 $y$보다 사전순으로 작다 (즉 어느 위치까지 같고 그 위치에서 $x$가 $y$보다 작다). 그런 $a$가 적어도 하나 존재함이 보장된다.

입력

첫 줄에 정수 하나 $N.$이 주어진다.

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

출력

공백으로 구분된 $N$개의 정수 $a_1,a_2,\ldots,a_{N}.$을 한 줄에 출력하라.

예제

입력 1

5
4 6 7 6

출력 1

3 1 5 2 4

참고

$3+1=4$, $1+5=6$, $5+2=7$, $2+4=6.$이므로 $a$는 $b$를 만든다.

서브태스크

• 테스트 케이스 $2$–$4$는 $N\le 8.$을 만족한다.

• 테스트 케이스 $5$–$10$에는 추가 제약이 없다.

문제 출제: Benjamin Qi와 Chris Zhang