У лицеиста Димы из Кремляндии есть таблица \(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\).
Выходные данные
Если не существует способа выбрать в каждой строке таблицы одно число, чтобы их побитовое исключающее ИЛИ было строго больше нуля, выведите «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\).
Если существует более одного возможного ответа, вы можете вывести любой.
Примечание
В первом примере все числа в матрице равны \(0\), поэтому невозможно выбрать в каждой строке таблицы по одному числу так, чтобы их побитовое исключающее ИЛИ было строго больше нуля.
Во втором примере выбранные числа \(7\) (первое число в первой строке) и \(10\) (третье число во второй строке), \(7 \oplus 10 = 13\), \(13\) больше чем \(0\), поэтому ответ найден.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 2
0 0
0 0
0 0
|
NIE
|
|
2
|
2 3
7 7 7
7 7 10
|
TAK
1 3
|