ASM – The Abelian Sandpile Model

Modelling sandpiles is an interesting problem in statistical physics. When you drop a grain of sand onto an existing pile, most of the time the grain simply sticks, or a few grains slide down. Occasionally, however, adding a single extra grain triggers a huge avalanche of sand.

A simple way to model this is the Abelian Sandpile Model. Here the sandpile is a two-dimensional lattice, and each lattice site holds a height (the number of grains on that site). Dropping a grain on a site increases its height by one. If a site's height ever becomes larger than a fixed critical height, the site topples: its height is reduced by four, and each of its four orthogonal neighbours gains one grain. Toppling can push neighbours above the critical height, so they topple in turn, and so on until every site is stable again. Any grain that would leave the lattice is lost.

Given an initial sandpile and the positions at which grains are dropped, determine the final (stable) sandpile.

The first line contains a single integer $T$, the number of test cases. Each test case has the following format:

• One line with four integers $y$, $x$, $n$, and $h$ where $1 \le y, x \le 100$, $0 \le n \le 100$, and $3 \le h \le 9$: the height and width of the lattice, the number of dropped grains, and the critical height.
• $y$ lines follow, each with $x$ characters in the range 0 to 9: the heights of the initial sandpile. Every initial height is at most the critical height.
• $n$ lines follow, each with two integers $y_i$ and $x_i$ where $1 \le y_i \le y$ and $1 \le x_i \le x$: the positions (row, column, 1-indexed) where grains are dropped.

For each test case, output $y$ lines, each with $x$ characters in the range 0 to 9: the heights of the final sandpile.