18945번 - 조작된 ㄱ 폭탄 게임

Ahgus 와 Bagus는 ㄱ 폭탄 게임을 하려고 한다.

ㄱ폭탄 게임은 N개의 게임판에서 진행된다. i번째 게임판은 가로와 세로의 길이가 각각 R_i, C_i이고 1×1 정사각형 칸으로 이루어진 직사각형 모양이다.

게임판의 각 칸에는 ㄱ 폭탄이 하나씩 놓여 있으며, 폭탄에는 총 세 개의 모양 A, B, C가 존재한다. A 폭탄은 Ahgus만 선택할 수 있고, B 폭탄은 Bagus만 선택할 수 있으며, C 폭탄은 누구도 선택할 수 없다.

ㄱ 폭탄은 터질 때 자신의 왼쪽과 아래쪽 칸의 폭탄을 점화한다. 점화된 폭탄은 곧 폭발하고, 그 왼쪽과 아래쪽에 있는 폭탄을 다시 점화하게 된다. 예를 들어 게임판의 가장 오른쪽 위 칸의 폭탄을 터뜨리면 모든 칸의 폭탄이 터지게 된다. 이렇게 연쇄적인 과정 끝에 더 이상 폭발하는 폭탄이 발생하지 않으면 해당 플레이어의 턴이 끝난다.

모든 게임은 Ahgus부터 시작하며 두 사람이 순서대로 한 턴씩 진행하고, 각 사람은 자신의 턴에 남아있는 폭탄 중 하나를 선택해 터뜨린다. 이때 자신의 턴에 터트릴 수 있는 폭탄이 더 이상 남아있지 않는 사람이 패배하게 된다.

두 사람은 게임에서 이기기 위해 몇몇 폭탄을 바꿔치기했고, 각 게임판에서 A와 B중 한 종류 이상의 폭탄은 단 한 개만 존재하게 되었다.

이를 지켜보던 연금술사 stonejjun이 나타나 총 T판의 게임을 진행할 것을 제안했다. 그는 각 게임마다 K번 게임판을 선택해 A 폭탄은 B 폭탄으로, B 폭탄은 A 폭탄으로 바꿔치기하고, 두 정수 U와 V에 대해 번호가 U 이상 V 이하인 게임판만을 사용할 수 있도록 나머지 게임판을 숨길 것이다.

그의 횡포에 화가 난 Ahgus와 Bagus는 게임을 하지 않고 승자를 결정하려고 한다. 만약 두 사람 모두 이기기 위한 최선의 선택을 할 경우, 각 게임마다 누가 이기게 될지 구해보자!

첫째 줄에는 게임판의 수 N이 주어진다.

그 후 각 N개의 게임판에 대해서 한 줄에 두 양의 정수 R_i, C_i가 주어진다.

그 아래 세로 R_i, 가로 C_i 개의 문자로 i번째 게임판이 주어진다. 게임판은 가장 왼쪽 위의 칸부터 주어진다.

그 다음 줄에는 둘이 진행할 게임의 수 T가 주어진다.

이후 T개의 줄에 걸쳐 세 양의 정수 K, U, V 가 주어진다.

T판의 각 게임별로 이기게 될 사람의 이름 Ahgus 또는 Bagus를 한 줄에 출력한다.

• 1 ≤ N ≤ 30,000
• 1 ≤ R_i, C_i, R_i × C_i ≤ 40
• 1 ≤ T ≤ 100,000
• 1 ≤ K ≤ N
• 1 ≤ U ≤ V ≤ N
• 게임판에서 등장하는 모든 문자는 A, B, C 중 하나이며, A와 B 중 한 종류 이상의 문자는 각 게임판에서 1개임이 보장된다.