Sandpile Avalanches

A table is divided into a grid of squares, and grid[r][c] is the number of grains of sand on square (r, c). A square holding 4 or more grains is unstable and topples: it loses 4 grains and sends one grain to each of its neighbours above, below, left and right. Grains sent off the edge of the table fall to the floor and are gone. A topple can make a neighbour unstable, and the avalanche goes on until every square holds 3 grains or fewer.

A surprising fact makes this a fair puzzle: whatever order you topple the unstable squares in, the final grid is always the same, and so is the number of times each square topples.

Write settle(grid) that returns a tuple (stable, topples): the final grid as a new list of lists, and the total number of topples (a square that topples three times counts 3).

Examples

settle([[4]])                              # returns ([[0]], 1)
settle([[0, 0, 0], [0, 4, 0], [0, 0, 0]])  # returns ([[0, 1, 0], [1, 0, 1], [0, 1, 0]], 1)
settle([[3, 3], [3, 4]])                   # returns ([[1, 1], [1, 2]], 4)

In the last example the bottom right square topples and pushes both of its neighbours to 4 grains. They topple too, which brings the top left square to 5 grains, and it topples last: 4 topples in all.

Constraints

• The grid has 1 to 600 rows and 1 to 600 columns.
• It holds at most 5,000 grains in all.