2023 Winter Waterloo Local Contest, Problem C

The Abelian Sandpile Model is a famous dynamical system displaying self-organized criticality. It has been studied for decades since it was introduced by Per Bak, Chao Tang and Kurt Wiesenfeld in a 1987 paper. The sandpile prediction is of wide interest in physics, computer science, and mathematics, both for its beautiful algebraic structure and for its relevance to applications like load balancing and derandomization of models like internal diffusion-limited aggregation. The sandpile model is related to many other models and physical phenomena, like the rotor-routing model, avalanche models.

In the sandpile model, we are given an undirected graph ~G~ whose vertices are indexed from ~1~ to ~n~. We're also given ~n~ integers ~a_1, a_2, \ldots, a_n~ where ~a_i~ indicates that there are ~a_i~ chips placed on vertex ~i~ initially. Each turn we will pick an arbitrary vertex ~v~ such that the number of chips on ~v~ is not smaller than the number of edges connecting ~v~, denoted as ~d_v~. For each neighbor of ~v~, it will receive one chip from ~v~. Therefore, ~v~ will lose ~d_v~ chips. This process is called firing or toppling. Firing will keep happening until no vertex ~v~ has at least ~d_v~ chips.

It can be proven that the order of firing doesn't affect the result. Meanwhile, it is also possible that the firing will never terminate. This instance is described as "recurrent". Now you are given a clique and the initial number of chips. Determine whether this instance is a recurrent one. If not, please output the final number of chips for each node respectively.

A clique (also called a complete graph) is a graph where every two vertices are connected with an edge.

Input Specification

There is only one test case in each test file.

The first line of the input contains an integer ~n~ ~(2 \le n \le 5 \times 10^5)~ indicating the size of the clique.

The second line contains ~n~ integers ~a_1, a_2, \ldots, a_n~ ~(0 \le a_i \le 10^9)~ where ~a_i~ indicates the initial number of chips placed on vertex ~i~.

Output Specification

Output one line. If the given sandpile instance will terminate, output ~n~ integers separated by a space where the ~i^{\text{th}}~ integer indicates the final number of chips on the ~i^{\text{th}}~ vertex. Otherwise output Recurrent instead.

Please, DO NOT output extra spaces at the end of each line, or your answer may be considered incorrect!

Sample Input 1

5
5 0 3 0 3

Sample Output 1

3 3 1 3 1

Explanation for Sample 1

For the first sample test case:

• We can only select vertex ~1~ at the beginning. The number of chips becomes ~\{1, 1, 4, 1, 4\}~.
• We can now select vertex ~3~ or ~5~ because both of them have at least ~4~ chips. We select vertex ~3~ and the number of chips becomes ~\{2, 2, 0, 2, 5\}~. Selecting vertex ~5~ will lead to the same result.

Sample Input 2

2
1 0

Sample Output 2

Recurrent

Explanation for Sample 2

For the second sample test case, we can select vertex ~1~ and ~2~ repeatedly. The firing never terminates.