32249번 - 보드게임

문제

Alice와 Bob은 두 명이서 보드게임을 진행하려고 한다. 이 보드게임은 어떤 양의 정수 $N,ドル $M$에 대해 총 2ドルNM$장의 카드를 가지고 진행한다. 이 카드들 중 정확히 $NM$장의 카드에는 알파벳 A가, 나머지 $NM$장의 카드에는 알파벳 B가 적혀 있다. Alice와 Bob은 게임이 시작하기 전 각자 $NM$장의 카드를 적당히 나누어 가져가고, 각자의 앞에 $N\times M$ 모양으로 카드를 배치한다. Alice와 Bob은 서로의 카드 배치를 알고 있다.

게임의 첫 턴은 Alice가 시작한다. 각 플레이어는 자신의 턴에 자신 앞에 있는 $M$개의 열 중 하나를 고른 후, 그 열에 놓인 가장 위쪽의 카드를 제거한다. 이때 제거한 카드에 적힌 알파벳이 A이면 다음 턴을 Alice가 진행하며, B이면 다음 턴은 Bob이 진행한다. 각 플레이어는 자신의 턴에 카드를 제거해야 하므로, 카드가 비어 있는 열은 고를 수 없다. 또한 어떤 턴에 플레이어가 카드를 제거함으로써 앞에 놓인 카드가 전부 제거된다면, 즉시 그 플레이어가 승리한다.

Alice와 Bob은 서로 이기기 위해 최선을 다한다. 두 사람은 카드의 배치가 주어졌을 때 게임의 승자가 누가 될지 궁금해 하고 있다. 또한 이 배치로부터 시작해, Alice와 Bob이 자신 앞에 놓인 카드를 하나씩 골라 선택한 두 카드를 교환할 때마다 게임의 승자가 어떻게 바뀌는지도 궁금해하고 있다. 이때 카드의 교환은 누적되어 적용된다.

초기 카드 배치와 어떤 두 카드가 교환되는 시행이 주어질 때마다 게임의 승자를 알아내는 프로그램을 작성해 이들의 궁금증에 답해 주자!

입력

첫째 줄에 양의 정수 $N,ドル $M$이 공백을 사이에 두고 주어진다. (1ドル\leq N\leq 10$; 1ドル\leq M\leq 1,円 000,円 000$; $NM\leq 1,円 000,円 000$)

둘째 줄부터 $N$개의 줄에 걸쳐 Alice의 카드 배치가 주어진다. $(i+1)$번째 줄에는 Alice의 $i$행에 놓인 카드들의 배치가 주어진다.

$(N+2)$째 줄부터 $N$개의 줄에 걸쳐 Bob의 카드 배치가 주어진다. $(i+N+1)$번째 줄에는 Bob의 $i$행에 놓인 카드들의 배치가 주어진다.

각 행에 놓인 카드들의 배치는 길이 $M$의 A와 B로만 구성된 문자열이며, $i$행 $j$열의 문자는 각 플레이어의 $i$행 $j$열의 카드에 쓰여 있는 알파벳을 의미한다.

입력으로 주어지는 문자열은 총 $NM$개의 A와 $NM$개의 B로 구성되어 있으며, 각 플레이어의 카드 배치의 1ドル$행은 각 열에서 가장 위쪽의 카드이다.

$(2N+2)$째 줄에는 카드가 교환되는 시행의 횟수를 나타내는 양의 정수 $Q$가 주어진다. (1ドル\leq Q\leq 200,円 000$)

$(2N+3)$째 줄부터 $Q$개의 줄에 걸쳐 카드 위치를 바꾸는 시행의 정보가 주어진다. $(i+2N+2)$째 줄에는 $i$째 시행을 나타내는 4ドル$개의 정수 $r_1,ドル $c_1,ドル $r_2,ドル $c_2$가 공백을 사이에 두고 주어진다. (1ドル\leq r_{1},r_{2}\leq N$; 1ドル\leq c_{1},c_{2}\leq M$) $(r_1,c_1)$은 교환할 Alice의 카드 위치이며, $(r_2,c_2)$는 교환할 Bob의 카드 위치이다.

출력

첫째 줄에 주어진 카드의 초기 배치에서 승리하는 플레이어의 이름을 Alice 혹은 Bob으로 출력한다.

둘째 줄부터 $Q$개의 줄에 걸쳐 카드 위치를 바꾸었을 때 승리하는 플레이어의 이름을 같은 형식으로 출력한다. $(i+1)$째 줄에는 초기 상태에서 첫째 시행부터 $i$째 시행까지 적용된 카드 배치에서 승리하는 플레이어의 이름을 출력한다.

제한

힌트