Sandpile on Clique

The Abelian Sandpile Model is a well-known dynamical system that shows self-organized criticality. Per Bak, Chao Tang, and Kurt Wiesenfeld introduced it in a 1987 paper, and researchers have studied it for decades. The sandpile model draws interest in physics, computer science, and mathematics. Its algebraic structure is elegant, and it applies to load balancing and to the derandomization of models such as internal diffusion-limited aggregation. The model is also related to the rotor-routing model and avalanche models.

In the sandpile model, we are given an undirected graph $G$ whose vertices are numbered from $1$ to $n$. We are also given $n$ integers $a_1, a_2, \cdots, a_n$, where $a_i$ is the number of chips initially placed on vertex $i$.

Each turn, we pick any vertex $v$ whose chip count is at least $d_v$, the number of edges connected to $v$. Each neighbor of $v$ receives one chip from $v$, so $v$ loses $d_v$ chips. This is called firing or toppling. Firing continues until no vertex $v$ has at least $d_v$ chips.

The order of firing does not affect the result. However, firing may never terminate. In that case the instance is called "recurrent". You are given a clique (a complete graph, where every two vertices are connected by an edge) and the initial chip counts. Determine whether the instance is recurrent. If it is not, output the final chip count of each vertex.

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

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

There is only one test case per input file.

If the firing terminates, output $n$ integers separated by spaces, where the $i$-th integer is the final number of chips on vertex $i$. Otherwise, output "Recurrent".

For the first sample, only vertex 1 can be chosen at the start. The chip counts become {1, 1, 4, 1, 4}.

Now vertex 3 or vertex 5 can be chosen, since both have at least 4 chips. Choosing vertex 3 gives {2, 2, 0, 2, 5}. Choosing vertex 5 gives the same result.

Next, vertex 5 is chosen, giving {3, 3, 1, 3, 1}. No vertex has at least 4 chips, so firing stops.

For the second sample, vertices 1 and 2 can be chosen repeatedly. Firing never terminates.