← 返回题目列表

Codeforces · 1151/B

B. Dima 和糟糕的异或

中文机器翻译题面 查看原题

来自 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$$$多,所以找到答案。