B. Дима и плохой XOR
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У лицеиста Димы из Кремляндии есть таблица $$$a$$$ размера $$$n \times m$$$, заполненная целыми неотрицательными числами.

Он хочет в каждой строке выбрать ровно одно число так, чтобы побитовое исключающее ИЛИ выбранных чисел было строго больше нуля. Помогите ему!

Формально, он хочет выбрать последовательность чисел $$$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$$$ целых чисел, разделенных пробелом: $$$j$$$-е число в $$$i$$$-й из этих строк обозначает $$$j$$$-й элемент $$$i$$$-й строки матрицы $$$a$$$, то есть $$$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$$$.

Если существует более одного возможного ответа, вы можете вывести любой.

Примеры
Входные данные
3 2
0 0
0 0
0 0
Выходные данные
NIE
Входные данные
2 3
7 7 7
7 7 10
Выходные данные
TAK
1 3
Примечание

В первом примере все числа в матрице равны $$$0$$$, поэтому невозможно выбрать в каждой строке таблицы по одному числу так, чтобы их побитовое исключающее ИЛИ было строго больше нуля.

Во втором примере выбранные числа $$$7$$$ (первое число в первой строке) и $$$10$$$ (третье число во второй строке), $$$7 \oplus 10 = 13$$$, $$$13$$$ больше чем $$$0$$$, поэтому ответ найден.