Gravity Grid

문제

Alice and Bob are playing a generalized version of Connect Four. In their game, the board consists of $ww$ columns of height $hh$ and the goal is to be the first player to complete a row of $kk$ tiles of equal colour, either vertically, horizontally or diagonally. The two players alternate dropping their tiles into one of the columns, with Alice using red tiles and going first and Bob using yellow tiles and going second. Once a tile is dropped, it falls down to the bottommost available position, making that position no longer available. Once a column has $hh$ tiles in it, it becomes full and the players can no longer drop their tiles there.

Figure G.1: Visualisation of the sample cases, showing the state of the game after 0, 3, 8 and 12 moves, respectively. Alice's tiles are shown in red, Bob's tiles in yellow.

As Alice and Bob found it quite challenging to keep track of the winning condition, they just kept playing until the board was completely filled with tiles. They recorded a log of the moves they made and asked you to tell them who won the game, and on what turn they did so. If neither player managed to complete a row, the game ends in a draw, so report that instead.

입력

The input consists of:

• One line with three integers $hh$, $ww$ and $kk$ ($h,w\ge 1,h\cdot w\le 250000,1\le k\le \max (h,w)h,\; w\; \backslash ge\; 1,\; h\; \backslash cdot\; w\; \backslash le\; 250\backslash ,000,\; 1\; \backslash le\; k\; \backslash le\; \backslash max(h,w)$). The columns are numbered from $11$ to $ww$.
• One line with $h\cdot wh\backslash cdot\; w$ integers $a_1,\dots ,a_{h\cdot w}a\_1,\backslash dots,a\_\{h\backslash cdot\; w\}$ ($1\le a_i\le w1\; \backslash le\; a\_i\; \backslash le\; w$ for each $ii$), where $a_{i}a\_i$ is the index of the column that the $ii$th tile was dropped in. Odd indices correspond to Alice's moves and even indices correspond to Bob's moves. Each column appears exactly $hh$ times in this list.

출력

Output the winner of the game (A for Alice or B for Bob), followed by the number of moves needed to decide the winner. If the game ends in a draw, output D instead.

4 3 2
1 1 2 3 3 2 2 1 1 2 3 3

A 3

4 3 3
1 1 2 3 3 2 2 1 1 2 3 3

B 8

4 3 4
1 1 2 3 3 2 2 1 1 2 3 3

D