Dima and a Bad XOR

题意翻译

## 题目描述 来自克雷姆兰德的学生迪马有一个大小为 $n \times m$ 的矩阵，其中只包含非负整数。 他希望从矩阵的每一行中选出一个整数，使得所选整数的按位异或严格大于零。 也就是说，他想选择一个整数序列 $c_1,c_2,\dots,c_n$ $(1\leq c_j \leq m)$ 使得不等式 $a_{1,c_1}\oplus a_{2,c_2}\dots \oplus a_{n,c_n} > 0$成立，其中 $a_{i,j}$ 是第 $i$ 行和第 $j$ 列的矩阵元素。 $x\oplus y$ 表示 $x$ 和 $y$ [按位异或运算](https://en.wikipedia.org/wiki/Bitwise_operation#XOR)，这里是他的定义。 ## 输入输出格式 ### 输入格式： 第一行包含两个整数 $n$ 和 $m$ $( 1 \leq n, m \leq 500 ) $ ，分别代表矩阵的行数和列数。 接下来的 $n$ 行中的每一行包含 $m$ 个整数：第 $i$ 行中的第 $j$ 个整数是矩阵 $a$ 的第 $i$ 行的第 $j$ 个元素 $a_{i,j}\ (0\leq a_{i,j}\leq 1023)$ ### 输出格式： 如果无法从每一行中选择一个整数，使其按位异或严格大于零，则输出“NIE”。 否则在第一行输出“TAK”，接下来的 $n$ 行里，输出 $n$ 个整数 $c_1,c_2,\dots,c_n$ $(1\leq c_j \leq m)$ ，使得不等式 $a_{1,c_1}\oplus a_{2,c_2}\dots \oplus a_{n,c_n} > 0$成立。 如果有多个可能的答案，您可以输出任何答案。 ## 说明 在第一个例子中，矩阵中的所有数字都是0，因此不可能在表的每一行中选择一个数字，以使它们的按位异或严格大于零。 在第二个例子中，所选数字是 $7$（第一行中的第一个数字）和$10$（第二行中的第三个数字），$7 \oplus 10 = 13$ , $13$ 大于 $0$ ，因此找到了答案。

题目描述

Student Dima from Kremland has a matrix $ a $ of size $ n \times m $ filled with non-negative integers. He wants to select exactly one integer from each row of the matrix so that the bitwise exclusive OR of the selected integers is strictly greater than zero. Help him! Formally, he wants to choose an integers sequence $ c_1, c_2, \ldots, c_n $ ( $ 1 \leq c_j \leq m $ ) so that the inequality $ a_{1, c_1} \oplus a_{2, c_2} \oplus \ldots \oplus a_{n, c_n} > 0 $ holds, where $ a_{i, j} $ is the matrix element from the $ i $ -th row and the $ j $ -th column. Here $ x \oplus y $ denotes the [bitwise XOR operation](https://en.wikipedia.org/wiki/Bitwise_operation#XOR) of integers $ x $ and $ y $ .

输入输出格式

输入格式

The first line contains two integers $ n $ and $ m $ ( $ 1 \leq n, m \leq 500 $ ) — the number of rows and the number of columns in the matrix $ a $ . Each of the next $ n $ lines contains $ m $ integers: the $ j $ -th integer in the $ i $ -th line is the $ j $ -th element of the $ i $ -th row of the matrix $ a $ , i.e. $ a_{i, j} $ ( $ 0 \leq a_{i, j} \leq 1023 $ ).

输出格式

If there is no way to choose one integer from each row so that their bitwise exclusive OR is strictly greater than zero, print "NIE". Otherwise print "TAK" in the first line, in the next line print $ n $ integers $ c_1, c_2, \ldots c_n $ ( $ 1 \leq c_j \leq m $ ), so that the inequality $ a_{1, c_1} \oplus a_{2, c_2} \oplus \ldots \oplus a_{n, c_n} > 0 $ holds. If there is more than one possible answer, you may output any.

输入输出样例

输入样例 #1

3 2
0 0
0 0
0 0

输出样例 #1

NIE

输入样例 #2

2 3
7 7 7
7 7 10

输出样例 #2

TAK
1 3 

说明

In the first example, all the numbers in the matrix are $ 0 $ , so it is impossible to select one number in each row of the table so that their bitwise exclusive OR is strictly greater than zero. In the second example, the selected numbers are $ 7 $ (the first number in the first line) and $ 10 $ (the third number in the second line), $ 7 \oplus 10 = 13 $ , $ 13 $ is more than $ 0 $ , so the answer is found.