Photoshoot timer 2초 memory 512MB

농부 존은 사진 촬영을 위해 그의 N마리의 소들을 줄 세우고 있습니다.

소들은 1번부터 N번까지 번호가 매겨져 있으며, 존은 처음에 왼쪽에서 i번째 소가 번호 a_i인 순열 a_1, a_2, ..., a_N을 종이에 적어두었습니다. 하지만 그 종이는 최근 도난당했습니다!

다행히도, 존이 처음에 적었던 순열을 복구하는 것이 여전히 가능할지도 모릅니다. 종이가 도난당하기 전에 베시는 b_1, b_2, ..., b_{N-1}이라는 수열을 기록했으며, 이 수열은 각 1 ≤ i < N에 대해 b_i = a_i + a_{i+1}을 만족합니다.

베시의 정보를 바탕으로 존이 작성한 "사전순으로 최소"인 순열 a를 복구하는 것을 도와주세요.

순열 x가 순열 y보다 사전순으로 작다는 것은 어떤 j에 대해 x_i = y_i (모든 i < j에 대해)이고 x_j < y_j인 경우를 의미합니다 (다시 말해, 두 순열은 특정 지점까지 동일하고, 그 지점에서 x가 y보다 작습니다). 적어도 하나 이상의 그런 a가 존재하는 것이 보장됩니다.