Gnome

시민 소요가 벌어지는 동안 경찰관이 겪는 일 가운데 가장 달갑지 않은 것 하나가 기다림이다. 성난 군중이 어느 쪽으로 움직일지 몇 시간이고 빗속에서 기다리는 장면을 떠올려 보자. 어떤 면에서는 치과 대기실보다 나쁘다. 대기실에서는 적어도 비를 맞지는 않는다. 그래서 경찰 지휘부는 모든 경찰관에게 방수 게임기를 지급하기로 했다. 이 게임기는 전설적인 게임 Gnome의 변형인 Same-Gnome을 돌린다.

여러분이 할 일은 이 게임의 시뮬레이터를 작성하는 것이다. 휴대용 PMD-85(이른바 PMD-Pilot)에서 돌아갈 만큼 단순해야 한다. 규칙은 짧다. 게임판은 N x M 칸으로 이루어지고, 각 칸에는 색이 있는 돌이 정확히 하나씩 놓여 있다. 목표는 돌을 최대한 많이 없애면서 점수를 최대한 많이 얻는 것이다. 돌을 없애는 규칙은 다음과 같다.

• 같은 색 돌과 하나 이상 맞닿은 돌만 없앨 수 있다. 맞닿은 칸은 위, 아래, 왼쪽, 오른쪽이고 대각선은 아니다.
• 돌 하나를 없애면 그 돌이 속한 같은 색 연결 영역 전체가 함께 사라진다.
• 게임판에는 중력이 작용한다. 돌이 사라지면 그 위에 있던 돌이 아래로 떨어져 빈자리를 채운다.
• 돌이 사라지고 위쪽 돌이 떨어진 뒤 빈 열이 생기면, 오른쪽 열이 왼쪽으로 밀려와 빈 열이 남지 않게 된다.
• 한 수로 돌 K개를 없애면 $(K-2)^2$점을 얻는다.
• 게임 도중 이 방식으로 게임판의 돌을 모두 없애면 1000점을 더 얻는다.

첫 줄에 양의 정수 Z가 주어지고, 이어서 Z개의 게임 데이터가 차례로 주어진다. 각 데이터의 첫 줄에는 게임판의 열 개수 C와 행 개수 R이 공백으로 구분되어 주어진다($1 \le R < 150$, $1 \le C < 300$). 다음 R개 줄에는 게임판의 각 행이 위에서 아래 순서로 주어진다. 각 줄에는 A부터 Z까지의 알파벳 대문자가 정확히 C개 있고, 그 행의 돌 색을 왼쪽에서 오른쪽 순서로 나타낸다.

게임판 다음에는 플레이어가 둔 수의 목록, 즉 없앨 돌의 좌표가 온다. 먼저 한 줄에 수의 개수 M이 주어진다. 이어서 M개 줄에 정수 I와 J가 공백으로 구분되어 주어진다. I($1 \le I \le C$)는 선택한 돌의 열 번호로 왼쪽에서부터 1로 시작하고, J($1 \le J \le R$)는 행 번호로 아래에서부터 1로 시작한다.

게임 전체를 시뮬레이션하면서 입력에 주어진 순서대로 같은 색 돌의 연결 영역을 없앤다. 지정된 자리에 돌이 없거나 고른 돌을 없앨 수 없으면 그 수는 무시하고 다음 수로 넘어간다. 각 게임 데이터마다 다음 다섯 줄을 출력한다.

Game over!
Score dosazene v teto hre je S bodu.
Byli bychom radi, kdybyste si zahrali jeste jednou.
Prejete si hrat znovu?
Prijemnou zabavu Vam preje firma ACMTENDO.

S는 위 규칙으로 얻은 점수이다. 각 문장은 한 줄씩 출력한다.