중력 격자

앨리스와 밥은 Connect Four를 일반화한 게임을 하고 있다. 이 게임의 보드는 높이가 $h$인 열이 $w$개 있고, 같은 색 타일 $k$개를 세로, 가로, 또는 대각선으로 먼저 한 줄로 완성하는 플레이어가 이긴다. 두 플레이어는 번갈아 가며 열 하나를 골라 타일을 떨어뜨린다. 앨리스는 빨간 타일을 쓰고 먼저 두며, 밥은 노란 타일을 쓰고 나중에 둔다. 타일이 떨어지면 그 열에서 비어 있는 가장 아래 칸까지 내려가고, 그 칸은 더 이상 사용할 수 없다. 열에 타일이 $h$개 쌓이면 그 열은 가득 차서 더 이상 타일을 떨어뜨릴 수 없다.

그림 G.1: 예시 케이스를 시각화한 그림이다. 각각 0수, 3수, 8수, 12수를 둔 뒤의 게임 상태를 보여 준다. 앨리스의 타일은 빨간색, 밥의 타일은 노란색이다.

앨리스와 밥은 승리 조건을 추적하기가 꽤 어려워서, 보드가 타일로 완전히 찰 때까지 그냥 계속 두었다. 두 사람은 둔 수의 기록을 남겼고, 누가 게임에서 이겼는지, 그리고 몇 번째 차례에 이겼는지 알려 달라고 부탁했다. 어느 플레이어도 한 줄을 완성하지 못했다면 무승부이므로 그 사실을 보고하라.

입력은 다음과 같다.

• 첫 줄에 정수 $h$, $w$, $k$가 주어진다 ($h, w \ge 1, h \cdot w \le 250\,000, 1 \le k \le \max(h,w)$). 열은 1번부터 $w$번까지 번호가 매겨져 있다.
• 둘째 줄에 $h\cdot w$개의 정수 $a\_1,\dots,a\_{h\cdot w}$ ($1 \le a\_i \le w$ for each $i$)가 주어진다. $a\_i$는 $i$번째 타일을 떨어뜨린 열의 번호다. 홀수 번째 값은 앨리스의 수, 짝수 번째 값은 밥의 수에 해당한다. 각 열은 이 목록에 정확히 $h$번 나타난다.

게임의 승자를 A(앨리스) 또는 B(밥)로 출력하고, 이어서 승자를 결정하는 데 필요한 수의 개수를 출력하라. 게임이 무승부로 끝나면 대신 D를 출력하라.