플러드필

기술자들은 건물에서 발견한 정보를 바탕으로 아틀란티스가 어떻게 가라앉았는지 알아내려 하고 있다. 아틀란티스의 과학자들은 홍수가 닥칠 것을 알고 있었다. 그들은 강우량 자료를 모으고, 대륙을 정사각형 칸으로 나눈 격자를 만들어 어느 지역이 얼마나 심하게 잠길지 계산했다. 각 칸은 물이 고이기 전까지 일정량의 물(단위는 헬레노미터)을 담을 수 있다.

시뮬레이션 자료에는 칸마다 물을 담을 수 있는 용량이 적힌 격자와 강우 사건이 들어 있다. 강우 사건마다 격자의 한 칸에 X 헬레노미터의 비가 내린다. 물이 가득 찬 칸 중 서로 인접한 칸들(한 칸을 둘러싼 8칸으로 정의한다)은 물을 나누는 목적에서 하나의 큰 칸으로 본다. 칸이 가득 차면 그 칸의 물은 인접한 미포화 칸에 고르게 나뉘어 들어간다. 그중 어떤 칸이 가득 차면, 물은 새로 합쳐진 하나의 큰 칸에 인접한 미포화 칸들 사이에 고르게 나뉜다. 즉, 넘친 칸에 인접한 칸과 방금 가득 찬 칸에 인접한 칸이 대상이다.

시뮬레이션은 여러 날 동안 진행되며, 기간이 끝난 시점의 각 칸의 포화 수준을 출력한다. 물이 찬 칸에 인접한 칸들은 모두 같은 시점에 함께 잠긴다. 날마다의 자료는 비가 내린 순서대로 주어지므로, 아틀란티스에서는 한 번에 두 곳 이상에 비가 내린 적이 없으므로, 다음 강우로 넘어가기 전에 각 강우 자료를 끝까지 처리해야 한다. 각 케이스가 시작될 때 모든 칸은 비어 있다.

한 케이스의 자료를 모두 처리한 뒤에는 아틀란티스가 가라앉았는지 판단한다. 모든 칸이 가득 차서 물이 흘러갈 곳이 없으면 "Atlantis Sank"를 출력한다. 그렇지 않고 물이 흘러갈 여유가 있었다면, 격자의 각 칸에 담긴 물의 양을 출력한다. 격자 가장자리의 칸이 가득 차면 바다 쪽 공간은 무시한다. 아틀란티스는 미국 공병대가 만들지 않은 거대한 제방으로 둘러싸여 있으므로, 그 제방이 터질 것으로 기대하지 마라.

격자는 왼쪽 위 칸을 0,0으로 하여 번호를 매긴다. 칸은 왼쪽에서 오른쪽으로, 위에서 아래로 순서대로 계산한다. 넘침과 관련된 모든 계산은 소수점 둘째 자리까지 반올림한다.

첫 줄에는 케이스의 수 $1 \le x \le 100$이 주어진다. 각 케이스는 행의 길이와 열의 길이(각각 $1 \le x \le 10$)로 시작하고, 이어서 격자 순서대로 각 칸의 물 보유량 $0 < x < 10^7$이 주어진다. 다음에는 날짜 수가 오고, 그 뒤에 각 날의 자료가 행, 열, 강우량의 형태로 주어진다.