보드게임

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

게임의 첫 턴은 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$열 카드에 적힌 알파벳이다. 입력 문자열에는 A가 총 $NM$개, B가 총 $NM$개 들어 있으며, 각 플레이어 배치의 1행은 각 열에서 가장 위쪽 카드이다.

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

$(2N+3)$번째 줄부터 $Q$개의 줄에 걸쳐 교환 정보가 주어진다. $(i+2N+2)$번째 줄에는 $i$번째 교환을 나타내는 정수 $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$번째 교환까지 적용된 카드 배치에서 승리하는 플레이어의 이름을 같은 형식으로 출력한다. $(i+1)$번째 줄에 $i$번째 교환 결과를 출력한다.