来自 Kremland 的学生 Dima 有一个大小为 $$$n \times m$$$ 的矩阵 $$$a$$$,其中填充有非负整数。
他想从矩阵的每一行中恰好选择一个整数,以便所选整数的按位异或严格大于零。帮助他!
正式地,他想要选择一个整数序列 $$$c_1, c_2, \ldots, c_n$$$ ($$$1 \leq c_j \leq m$$$) 使得不等式 $$$a_{1, c_1} \oplus a_{2, c_2} \oplus \ldots \oplus a_{n, c_n} > 0$$$成立,其中 $$$a_{i, j}$$$ 是第 $$$i$$$ 行和第 $$$j$$$ 列的矩阵元素。
这里 $$$x \oplus y$$$ 表示整数 $$$x$$$ 和 $$$y$$$ 的按位异或运算。
输入
第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$1 \leq n, m \leq 500$$$) - 矩阵 $$$a$$$ 中的行数和列数。
接下来的 $$$n$$$ 行包含 $$$m$$$ 整数:第 $$$i$$$ 行中的第 $$$j$$$ 整数是矩阵 $$$a$$$ 第 $$$i$$$ 行的第 $$$j$$$ 元素,即 $$$a_{i, j}$$$ ($$$0 \leq a_{i, j} \leq 1023$$$)。
输出
如果无法从每一行中选择一个整数,使其按位异或严格大于零,则打印“NIE”。
否则在第一行打印“TAK”,在下一行打印 $$$n$$$ 整数 $$$c_1, c_2, \ldots c_n$$$ ($$$1 \leq c_j \leq m$$$),这样不等式 $$$a_{1, c_1} \oplus a_{2, c_2} \oplus \ldots \oplus a_{n, c_n} > 0$$$ 成立。
如果有多个可能的答案,您可以输出任何一个。
示例
输入 #1
3 2 0 0 0 0 0 0
输出 #1
NIE
输入 #2
2 3 7 7 7 7 7 10
输出 #2
TAK 1 3
注意
在第一个示例中,矩阵中的所有数字都是 $$$0$$$,因此不可能在表的每一行中选择一个数字,使其按位异或严格大于零。
第二个例子中,选择的数字是$$$7$$$(第一行第一个数字)和$$$10$$$(第二行第三个数字),$$$7 \oplus 10 = 13$$$,$$$13$$$比$$$0$$$多,所以找到答案。