Battle Sheep

Battle Sheep은 두 사람이 하는 게임이고, 규칙은 다음과 같다.

각 선수는 $N \times N$ 격자를 하나씩 가지고 그 위에 배 네 척을 놓는다. 배끼리는 겹치지 않고, 모든 배는 두 축 중 하나와 나란하다. 두 선수 모두 아래 네 종류를 정확히 한 척씩 놓는다.

두 선수는 번갈아 칸을 부른다. A가 부른 칸이 B의 격자에서 배가 덮은 칸이면 B는 명중이라고 알린다. 그 배가 덮은 칸이 모두 명중되면 B는 그 배가 침몰했다고 알리고, A가 한 번 더 부른다. A가 부른 칸이 어떤 배도 침몰시키지 못하면 차례는 B에게 넘어간다. 상대의 배 네 척을 모두 침몰시킨 선수가 이기고, 게임은 거기서 끝난다.

Alice와 Bob은 직접 칸을 부르고 결과를 알리는 일이 번거로워져서, 배를 놓은 위치와 칸을 부를 순서를 미리 적어 두기로 했다. 둘 다 같은 칸을 두 번 부르지 않는다. Bob은 신사라서 늘 Alice에게 선공을 양보한다.

두 격자와 두 사람이 부를 순서가 주어진다. 어떤 배가 어떤 순서로 침몰했는지, 그리고 누가 이겼는지 구하라.

첫째 줄에 테스트 케이스의 개수 $T$가 주어진다.

각 테스트 케이스의 첫째 줄에는 격자의 크기 $N$이 주어진다.

다음 $N$개 줄에는 Alice의 격자가 한 줄에 $N$개 문자씩 주어진다. 각 문자는 ., 1, 2, 3, 4 중 하나다. .은 빈 칸이다. 숫자는 그 칸을 Alice의 배 하나가 덮고 있다는 뜻이고, 같은 숫자가 적힌 칸은 모두 같은 배에 속한다. 숫자가 배의 길이를 뜻하지는 않는다.

다음 $N$개 줄에는 Bob의 격자가 같은 형식으로 주어진다.

다음 $N^2$개 줄에는 Alice가 부를 순서가 주어진다. 각 줄에는 정수 $R_i$와 $C_i$가 주어지며, 게임이 그 차례까지 이어졌을 때 Alice가 부를 행과 열이다.

다음 $N^2$개 줄에는 Bob이 부를 순서가 같은 형식으로 주어진다.

• $1 \le T \le 20$
• $4 \le N \le 10$
• $1 \le R_i, C_i \le N$
• 모든 배는 한 축과 나란하게 이어진 같은 문자의 직선이다.
• 두 선수 모두 같은 칸을 두 번 부르지 않으므로, 각 순서 목록은 격자의 모든 칸을 정확히 한 번씩 담는다.

각 테스트 케이스마다 침몰한 배를 침몰한 순서대로 한 줄에 하나씩 출력한다.

PlayerX sank PlayerY's ShipName

PlayerX는 칸을 부른 선수, PlayerY는 그 배의 주인, ShipName은 표에 적힌 배의 이름이다. 두 선수의 이름은 Alice와 Bob으로 쓴다.

그 줄들을 모두 출력한 다음, 마지막 줄에 이긴 선수의 이름을 출력한다.