Alice 和 Bob 正在玩一个广义版本的“四子棋”（Connect Four）。在这个游戏中，棋盘由 $w$ 列、高度为 $h$ 的网格组成。游戏的目标是成为第一个在垂直、水平或对角线方向上连成 $k$ 个同色棋子的玩家。两名玩家轮流将棋子放入其中一列，Alice 使用红色棋子并先行，Bob 使用黄色棋子并后行。棋子放入后会落到该列最底部的空位，使得该位置不再可用。一旦某列已有 $h$ 个棋子，该列即为已满，玩家将无法再向其中放入棋子。

图 G.1：样例情况的可视化，展示了游戏分别在 0、3、8 和 12 步之后的状态。Alice 的棋子显示为红色，Bob 的棋子显示为黄色。

由于 Alice 和 Bob 发现追踪获胜条件非常困难，他们只是继续游戏直到棋盘被完全填满。他们记录了所下棋子的移动日志，并要求你告诉他们谁赢得了比赛，以及是在第几步获胜的。如果没有任何玩家成功连成一行，则游戏以平局结束，此时请输出平局结果。

输入格式

输入包含： 一行，包含三个整数 $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$，对于每个 $i$)，其中 $a_i$ 是第 $i$ 个棋子放入的列索引。奇数索引对应 Alice 的移动，偶数索引对应 Bob 的移动。每一列在此列表中恰好出现 $h$ 次。

输出格式

输出获胜者（Alice 为 A，Bob 为 B），后跟决定胜负所需的步数。如果游戏以平局结束，则输出 D。

样例

样例输入 1

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

样例输出 1

A 3

样例输入 2

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

样例输出 2

B 8

样例输入 3

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

样例输出 3

D