#D. 迪马和错误的异或

    远端评测题 1000ms 256MiB

迪马和错误的异或

该比赛已结束,您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

来自克雷姆兰德的学生迪马有一个大小为 n×mn \times m 的矩阵,其中只包含非负整数。

他希望从矩阵的每一行中选出一个整数,使得所选整数的按位异或严格大于零。

也就是说,他想选择一个整数序列 c1,c2,,cnc_1,c_2,\dots,c_n (1cjm)(1\leq c_j \leq m) 使得不等式 $a_{1,c_1}\oplus a_{2,c_2}\dots \oplus a_{n,c_n} > 0$成立,其中 ai,ja_{i,j} 是第 ii 行和第 jj 列的矩阵元素。

xyx\oplus y 表示 xxyy [按位异或运算]。

输入格式

第一行包含两个整数 nnmm (1n,m500)( 1 \leq n, m \leq 500 ) ,分别代表矩阵的行数和列数。

接下来的 nn 行中的每一行包含 mm 个整数:第 ii 行中的第 jj 个整数是矩阵 aa 的第 ii 行的第 jj 个元素 ai,j (0ai,j1023)a_{i,j}\ (0\leq a_{i,j}\leq 1023)

输出格式

如果无法从每一行中选择一个整数,使其按位异或严格大于零,则输出“NIE”。

否则在第一行输出“TAK”,接下来的 nn 行里,输出 nn 个整数 c1,c2,,cnc_1,c_2,\dots,c_n (1cjm)(1\leq c_j \leq m) ,使得不等式 $a_{1,c_1}\oplus a_{2,c_2}\dots \oplus a_{n,c_n} > 0$成立。

如果有多个可能的答案,您可以输出任何答案。

说明

在第一个例子中,矩阵中的所有数字都是0,因此不可能在表的每一行中选择一个数字,以使它们的按位异或严格大于零。

在第二个例子中,所选数字是 77(第一行中的第一个数字)和1010(第二行中的第三个数字),710=137 \oplus 10 = 13 , 1313 大于 00 ,因此找到了答案。

样例 #1

样例输入 #1

3 2
0 0
0 0
0 0

样例输出 #1

NIE

样例 #2

样例输入 #2

2 3
7 7 7
7 7 10

样例输出 #2

TAK
1 3

说明

在第一个例子中,矩阵中的所有数字都是 0 0 ,所以不可能在表格的每一行中选择一个数字,使得它们的位异或严格大于零。

在第二个例子中,选择的数字是 7 7 (第一行的第一个数)和 10 10 (第二行的第三个数),710=13 7 \oplus 10 = 13 13 13 大于 0 0 ,所以找到了答案。

周日下午1点半升班测试补题场(阎乐成 栾子睿)

未参加
状态
已结束
规则
IOI
题目
4
开始于
2023-10-29 15:30
结束于
2023-11-11 3:30
持续时间
300 小时
主持人
参赛人数
3