수족관의 먹이 순환

문제

한 수족관은 작은 수조 N개를 원형으로 배치하고, 각 수조의 수면에 떠 있는 먹이 알갱이 수를 관리한다. 수조에는 원을 따라 1번부터 N번까지 번호가 붙어 있다. i번 수조의 다음 수조는 i가 N보다 작으면 i+1번 수조이고, N번 수조의 다음 수조는 1번 수조이다. 처음에 i번 수조에는 먹이 알갱이가 A_i개 있다. 알갱이는 모두 같은 크기이며 쪼갤 수 없다. 관리자는 먹이가 한 수조에 지나치게 몰리는 것을 줄이기 위해 이송 장치를 딱 한 번 작동한다. 장치를 작동하면 각 수조는 작동 직전에 들어 있던 먹이 알갱이를 세 개씩 묶는다. 만들 수 있는 묶음을 최대한 만든 뒤, 각 묶음에서 알갱이 하나씩을 다음 수조로 보낸다. 묶음에 남은 두 알갱이와 묶음을 만들지 못한 알갱이는 원래 수조에 남는다. 예를 들어 작동 직전에 먹이가 8개인 수조는 세 개짜리 묶음을 두 개 만들 수 있으므로 알갱이 2개를 다음 수조로 보내고, 원래 먹이 중 6개를 남긴다. 작동 직전에 먹이가 2개 이하인 수조는 묶음을 만들 수 없으므로 아무것도 보내지 않는다. 이송되는 알갱이 수는 항상 정수이다. 모든 수조의 이송은 동시에 이루어진다. 각 수조가 보낼 양은 오직 장치 작동 직전의 먹이 수로 정한다. 다른 수조에서 이번 작동으로 받은 먹이는 보낼 양을 계산할 때 포함하지 않으며, 같은 작동 중에 다시 다음 수조로 보내지도 않는다. 따라서 수조 번호 순서대로 먹이가 여러 수조를 연달아 통과하는 일은 없다. 수조가 하나뿐이면 그 수조의 다음 수조도 자기 자신이다. 이 경우에도 같은 규칙을 적용하므로 보내기로 한 먹이를 자신이 그대로 돌려받는다. 이송 과정에서 먹이가 새로 생기거나 사라지는 일은 없다. 장치를 한 번 작동한 뒤 각 수조에 들어 있는 먹이 알갱이 수를 수조 번호 순서대로 구한다.

입력

첫째 줄에 수조 수인 정수 N이 주어진다. 1 ≤ N ≤ 20,000이다.
둘째 줄에 정수 A_1, A_2, …, A_N이 공백으로 주어진다. 0 ≤ A_i ≤ 1,000,000,000이다. 모든 수조의 먹이 수가 0일 수도 있다.

출력

장치를 한 번 작동한 뒤의 먹이 알갱이 수 N개를 1번 수조부터 N번 수조까지 순서대로 한 줄에 공백으로 구분하여 출력한다. 먹이가 없는 수조는 0을 출력한다.

4
8 1 6 0

6 3 4 2

1
11

11

5
0 2 0 1 2

0 2 0 1 2

출처: Devin.KR 자체 제작