수족관의 먹이통 한 바퀴

문제

한 수족관의 관리 구역에는 먹이통 N개가 원형으로 놓여 있다. 먹이통에는 시계 방향으로 1번부터 N번까지 번호가 붙어 있다. 1번 먹이통의 다음은 2번이고, 같은 방식으로 이어져 N번 먹이통의 다음은 다시 1번이다. 각 먹이통에는 나눌 수 없는 작은 먹이 알갱이가 들어 있으며, 관리자는 자동 장치를 이용해 먹이 일부를 다음 먹이통으로 옮기려 한다. 자동 장치는 한 번 작동할 때 모든 먹이통에서 동시에 알갱이를 옮긴다. 각 먹이통이 내보낼 알갱이 수는 작동 직전에 그 먹이통에 있던 알갱이 수를 3으로 나눈 몫이다. 나머지는 내보내지 않고 원래 먹이통에 남겨 둔다. 예를 들어 작동 직전에 알갱이가 11개 있었다면 다음 먹이통으로 3개를 보내고, 자신이 원래 가지고 있던 알갱이 중 8개를 남긴다. 이동은 동시에 이루어지므로, 다른 먹이통에서 이번에 받은 알갱이를 곧바로 다시 내보내지는 않는다. 모든 먹이통이 내보낼 수량을 작동 직전의 상태만으로 정한 뒤, 정해진 수량을 한꺼번에 이동한다고 생각하면 된다. 각 먹이통은 자신의 바로 앞 먹이통에서 알갱이를 받고, 자신의 바로 다음 먹이통으로 알갱이를 보낸다. 특히 1번 먹이통은 N번 먹이통이 보낸 알갱이를 받는다. 장치를 작동하는 동안 알갱이를 새로 넣거나 꺼내는 일은 없고, 이동 중에 알갱이가 사라지는 일도 없다. 알갱이가 3개보다 적은 먹이통은 아무것도 내보내지 않지만, 앞 먹이통에서 알갱이를 받을 수는 있다. 작동 직전 각 먹이통의 알갱이 수가 주어질 때, 장치를 정확히 한 번 작동한 뒤 각 먹이통에 들어 있는 알갱이 수를 구한다. 결과는 처음과 같은 번호 순서로 출력한다.

입력

첫째 줄에 먹이통 수를 나타내는 정수 N이 주어진다.
둘째 줄에 작동 직전 1번부터 N번 먹이통까지의 알갱이 수 A₁, A₂, …, Aₙ이 공백으로 구분되어 주어진다.
2 ≤ N ≤ 1,000
0 ≤ Aᵢ ≤ 1,000,000
모든 입력 값은 정수다.

출력

장치를 한 번 작동한 뒤 1번부터 N번 먹이통까지의 알갱이 수를 공백으로 구분하여 한 줄에 출력한다.

4
8 3 0 5

7 4 1 4

2
0 6

2 4

3
2 2 2

2 2 2

출처: Devin.KR 자체 제작