KK学五子棋

Tags:

Description

有一天KK一个人在研究残局，现在他得到了一个五子棋的残局，当前轮到黑色方下子，他在思考：

• 他能否在这一步内胜利?如果能，那么他需要把棋子下在哪儿？
• 他若在这一步内不能胜利，那么他把棋子下在哪儿，使得对方不能在下一步获胜？

此处我们约定，五子棋获胜条件为：
当某一方落子后，这一方有大于等于五颗相同颜色的棋子在一条线上(可以为横连、纵连、斜连)，那么该方获胜。

Input

多组数据评测。
第一行包含一个正整数$T(1 \leq T \leq 10^2)$，表示有$T$组数据。
对于每一组数据：
第一行包含两个正整数$n, m(5 \leq n, m \leq 10^3)$，表示棋盘的大小。
接下来$n$行，每行$m$个整数$a_i(0 \leq a_i \leq 2)$，表示该位置的棋子状态。

• $0$表示该位置为空
• $1$表示该位置为白棋
• $2$表示该位置为黑棋

数据保证$\sum n \cdot m \leq 10^6$。
数据保证当前局面下白棋和黑棋的数量一样多。
数据保证棋盘中$0$的个数大于等于$2$。
数据保证当前局面是非胜利局面，即没有五个白棋连子，也没有五个黑棋连子。

Output

如果KK能够在这一步内胜利(输出包含两行)：
第一行输出'Win'(没有引号)。
第二行输出包含两个以空格分割的正整数$x \; y(1 \leq x \leq n, 1 \leq y \leq m)$，表示KK在这一步要下的棋子的位置。
如果有多个解，那么输出$x$最小的解，如果还有多解，输出$y$最小的解。

如果KK不能够在这一步内胜利，但是可以使得对方不能在下一步内胜利(输出包含两行)：
第一行输出'Defense'(没有引号)。
第二行输出包含两个以空格分割的正整数$x \; y(1 \leq x \leq n, 1 \leq y \leq m)$，表示KK在这一步要下的棋子的位置。
如果有多个解，那么输出$x$最小的解，如果还有多解，输出$y$最小的解。

否则， KK在这一步不管怎么下，对方都可以在下一步胜利(输出包含一行)：
第一行输出'Defeated'(没有引号)。

Samples

Author