Board Game

Alice and Bob play a board game together. For some positive integers $N$ and $M$, the game uses $2NM$ cards in total. Exactly $NM$ of these cards have the letter A written on them, and the other $NM$ cards have B. Before the game starts, Alice and Bob each take $NM$ cards and lay them out in an $N\times M$ grid in front of themselves. Each player knows the other's layout.

Alice takes the first turn. On her turn, a player chooses one of the $M$ columns in front of them and removes the topmost card in that column. If the removed card has A on it, Alice takes the next turn. If it has B, Bob takes the next turn. A player must remove a card on every turn, so a column with no cards left cannot be chosen. If a player's removal empties all the cards in front of them, that player wins immediately.

Alice and Bob each try their best to win. Given a starting layout, they want to know who wins. They also want to know how the winner changes each time Alice and Bob each pick one card in front of themselves and swap the two chosen cards. Swaps are cumulative, so each swap applies to the layout left by the previous swaps.

The first line contains two positive integers $N$ and $M$, separated by a space. ($1\leq N\leq 10$; $1\leq M\leq 1\,000\,000$; $NM\leq 1\,000\,000$)

From the second line onward, $N$ lines give Alice's layout. Line $(i+1)$ gives the cards in row $i$ of Alice's grid.

From line $(N+2)$ onward, $N$ lines give Bob's layout. Line $(i+N+1)$ gives the cards in row $i$ of Bob's grid.

Each row is a string of length $M$ made only of A and B. The character in row $i$, column $j$ is the letter on that player's card at row $i$, column $j$. The input strings contain $NM$ A characters and $NM$ B characters in total. Row 1 of each player's layout is the topmost card in each column.

Line $(2N+2)$ contains a positive integer $Q$, the number of swaps. ($1\leq Q\leq 200\,000$)

From line $(2N+3)$ onward, $Q$ lines describe the swaps. Line $(i+2N+2)$ contains four integers $r_1$, $c_1$, $r_2$, $c_2$, separated by spaces. ($1\leq r_1,r_2\leq N$; $1\leq c_1,c_2\leq M$) The pair $(r_1,c_1)$ is the position of the card in Alice's grid to swap, and $(r_2,c_2)$ is the position of the card in Bob's grid to swap.

On the first line, print the winner of the starting layout, either Alice or Bob.

On each of the next $Q$ lines, print the winner in the same format after applying the first $i$ swaps, for $i=1,\dots,Q$. Line $(i+1)$ gives the result after swap $i$.