완전 그래프 위의 샌드파일

아벨 샌드파일 모델(Abelian Sandpile Model)은 자기조직 임계 현상을 보이는 유명한 동역학 시스템이다. 1987년 Per Bak, Chao Tang, Kurt Wiesenfeld가 논문에서 처음 소개했고, 이후 수십 년 동안 연구되어 왔다. 샌드파일 모델은 물리학, 컴퓨터 과학, 수학에서 모두 관심을 받는다. 대수 구조가 아름답고, 부하 분산과 internal diffusion-limited aggregation 모델의 비무작위화에도 쓰인다. 이 모델은 rotor-routing 모델, 눈사태 모델과도 관련이 있다.

샌드파일 모델에서는 정점이 1부터 $n$까지 번호로 구분된 무방향 그래프 $G$가 주어진다. 또한 정수 $a_1, a_2, \cdots, a_n$이 주어지며, $a_i$는 정점 $i$에 처음 놓인 칩의 개수다.

매 턴마다 칩 수가 정점 $v$의 간선 수 $d_v$ 이상인 정점 $v$를 임의로 고른다. $v$의 이웃 각각은 $v$에서 칩을 하나씩 받고, $v$는 $d_v$개의 칩을 잃는다. 이 과정을 발화(firing) 또는 톱플링(toppling)이라 한다. 칩 수가 $d_v$ 이상인 정점이 더 이상 없을 때까지 발화가 계속된다.

발화 순서는 결과에 영향을 주지 않는다. 그러나 발화가 끝나지 않을 수도 있다. 이 경우를 "recurrent"라 한다. 완전 그래프(모든 두 정점 사이에 간선이 있는 그래프, clique)와 초기 칩 수가 주어진다. 이 상황이 recurrent인지 판별하라. recurrent가 아니라면 각 정점의 최종 칩 수를 출력하라.

첫 번째 줄에 클릭의 크기 $n$($2 \le n \le 5 \times 10^5$)이 주어진다.

두 번째 줄에 $n$개의 정수 $a_1, a_2, \cdots, a_n$($0 \le a_i \le 10^9$)이 주어진다. $a_i$는 정점 $i$의 초기 칩 수다.

테스트 케이스는 하나뿐이다.

발화가 끝나면 $n$개의 정수를 공백으로 구분해 출력한다. $i$번째 정수는 정점 $i$의 최종 칩 수다. 끝나지 않으면 "Recurrent"를 출력한다.

첫 번째 예제에서는 처음에 정점 1만 고를 수 있다. 칩 수는 {1, 1, 4, 1, 4}가 된다.

이제 칩이 4개 이상인 정점 3이나 정점 5를 고를 수 있다. 정점 3을 고르면 {2, 2, 0, 2, 5}가 된다. 정점 5를 골라도 결과는 같다.

다음으로 정점 5를 고르면 {3, 3, 1, 3, 1}이 된다. 칩이 4개 이상인 정점이 없으므로 발화가 멈춘다.

두 번째 예제에서는 정점 1과 정점 2를 반복해서 고를 수 있다. 발화는 끝나지 않는다.