ASM – 아벨 모래 더미 모형

모래 더미를 모형화하는 것은 통계 물리학의 흥미로운 문제이다. 이미 쌓여 있는 더미 위에 모래알 하나를 떨어뜨리면 대개 그 알갱이는 그대로 붙어 있거나 몇 알이 흘러내리는 데 그친다. 그러나 가끔은 알갱이 하나를 더 얹는 것만으로 거대한 모래 사태가 일어나기도 한다.

이를 간단하게 모형화한 것이 아벨 모래 더미 모형(Abelian Sandpile Model)이다. 이 모형에서 모래 더미는 2차원 격자로 표현되며, 각 격자 칸에는 높이(그 칸에 쌓인 모래알의 수)가 정해져 있다. 어떤 칸에 알갱이를 하나 떨어뜨리면 그 칸의 높이가 1 증가한다. 만약 어떤 칸의 높이가 정해진 임계 높이보다 커지면 그 칸이 무너진다. 무너지는 칸은 높이가 4만큼 줄고, 상하좌우로 인접한 네 칸의 높이가 각각 1씩 늘어난다. 이 과정에서 인접한 칸이 임계 높이를 넘게 되면 그 칸들도 잇따라 무너지며, 모든 칸이 다시 안정될 때까지 이 과정이 계속된다. 격자 밖으로 나가는 모래알은 사라진다.

처음 모래 더미와 알갱이를 떨어뜨리는 위치들이 주어질 때, 최종적으로 안정된 모래 더미를 구하여라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스의 형식은 다음과 같다.

• 첫 줄에 네 정수 $y$, $x$, $n$, $h$가 주어진다. 이때 $1 \le y, x \le 100$, $0 \le n \le 100$, $3 \le h \le 9$이며, 각각 격자의 세로 길이, 가로 길이, 떨어뜨리는 알갱이의 수, 임계 높이를 뜻한다.
• 이어서 $y$개의 줄에 각각 0부터 9까지의 문자 $x$개가 주어지며, 이는 처음 모래 더미의 높이를 나타낸다. 처음 높이는 모두 임계 높이 이하이다.
• 이어서 $n$개의 줄에 각각 두 정수 $y_i$, $x_i$가 주어진다($1 \le y_i \le y$, $1 \le x_i \le x$). 이는 알갱이를 떨어뜨리는 위치(행, 열, 1부터 시작)를 나타낸다.

각 테스트 케이스마다 $y$개의 줄을 출력한다. 각 줄에는 0부터 9까지의 문자 $x$개를 출력하며, 이는 최종 모래 더미의 높이를 나타낸다.