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 of integers $x$ and $y$.


-----Input-----

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$). 


-----Output-----

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.


-----Examples-----
Input
3 2
0 0
0 0
0 0

Output
NIE

Input
2 3
7 7 7
7 7 10

Output
TAK
1 3 



-----Note-----

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.

Difficulty: interview

Starter code:

Solutions:
n, m = [int(i) for i in input().split()]
A = []
C = []
for i in range(n):
    B = [int(j) for j in input().split()]
    A.append(B)
    C.append(sorted(list(set(B))))

xor = 0
ans = []

for i in range(n):
    xor ^= A[i][0]
    ans.append(1)

if xor==0:
    found = 0
    for trial in range(n-1, -1, -1):
        newxor = xor^A[trial][0]
        if found==1:
            break
        for j in range(m):
            if A[trial][j]^newxor!=0:
                ans[trial] = j+1
                found = 1
                break
        if found==1:
            break
    if found:
        print('TAK')
        print(*ans)
    else:
        print('NIE')
else:
    print('TAK')
    print(*ans)


N, M = list(map(int, input().split()))
X = [[int(a) for a in input().split()] for i in range(N)]
i0, j0 = -1, -1
for i in range(N):
    for j in range(M-1):
        if X[i][j] != X[i][j+1]:
            i0, j0 = i, j+1
            break
    if i0 >= 0:
        break

s = 0
for i in range(N):
    s ^= X[i][0]
if s > 0:
    print("TAK")
    print(*([1]*N))
elif i0 >= 0:
    print("TAK")
    print(*([1]*i0+[j0+1]+[1]*(N-i0-1)))
else:
    print("NIE")


import sys
n,m = list(map(int,input().split()))

def xor(A):
    x = 0
    for a in A: x ^= a
    return x

A = [[int(x) for x in input().split()] for _ in range(n)]

I = [0]*n

ref = A[0][0]
if xor(A[i][0] for i in range(n)):
    print('TAK')
    print(*[i+1 for i in I])
    return
else:
    for i in range(n):
        for j in range(m):
            if A[i][0] != A[i][j]:
                I[i] = j
                print('TAK')
                print(*[i+1 for i in I])
                return
print('NIE')
    


def groupxor(l):
	result = 0
	for item in l:
		result = result ^ item
	return result

r,c = [int(x) for x in input().split()]
rows = []
for _ in range(r):
	rows.append([int(x) for x in input().split()])
starts = [rows[j][0] for j in range(r)]
result = [1] * r
if groupxor(starts) == 0:
	notfixed = True
	for j in range(r):
		for k in range(1,c):
			if notfixed:
				if rows[j][0] != rows[j][k]:
					notfixed = False
					result[j] = k+1
	if notfixed == True:
		print('NIE')
	else:
		print('TAK')
		print(' '.join([str(x) for x in result]))
else:
	print('TAK')
	print(' '.join([str(x) for x in result]))

import sys

n, m = map(int, input().split())

M = []

for i in range(n):
	M.append(list(map(int, input().split())))

result = 0
for i in range(n):
	result = result ^ M[i][0]

if result > 0:
	print('TAK')
	print(*[1 for _ in range(n)])
	return

is_solution_exist = False
row = None
col = None

for i in range(n):

	for j in range(m):

		if M[i][j] != M[i][0]:
			is_solution_exist = True
			row = i
			col = j
			break

	if is_solution_exist:
		break

if is_solution_exist:
	print('TAK')
	result = [1 for _ in range(n)]
	result[row] = col + 1
	print(*result)
else:
	print('NIE')

from collections import defaultdict as dd
import math
def nn():
	return int(input())

def li():
	return list(input())

def mi():
	return list(map(int, input().split()))

def lm():
	return list(map(int, input().split()))


n,m=mi()

matrix=[]

for i in range(n):
	matrix.append(lm())
done=0
good=-1
for i in range(n):
	val=matrix[i][0]
	for j in range(m):
		if not matrix[i][j]==val:
			good=(i,j)
			done=1
			break
	if done==1:
		break
start=0
if good==-1:
	for i in range(n):
		start=start^matrix[i][0]

	if start==0:
		print('NIE')

	else:
		print("TAK")
		out=['1']*n
		print(*out)


else:
	answers=[]
	for i in range(n):
		start=start^matrix[i][0]

	
	if not start==0:
		print("TAK")
		out=['1']*n
		print(*out)


	else:

		
		extra=0

		for i in range(n):
			if not i==good[0]:
				extra=extra^matrix[i][0]
				answers.append('1')
			else:
				extra=extra^matrix[i][good[1]]
				answers.append(str(good[1]+1))



		print('TAK')
		print(*answers)
	
				


def in_int():
    return int(input())
def in_list():
    return [int(x) for x in input().split()]

n,m=in_list()
mat=[]
first=-1
for i in range(n):
    mat.append(in_list())
    if first==-1:
        for j in range(m-1):
            if mat[-1][j]!=mat[-1][j+1]:
                first=(i,j)
                break
if first==-1:
    ans=0
    for i in range(n):
        ans=ans^mat[i][0]
    if ans>0:
        print('TAK')
        print(' '.join(['1']*n))
    else:
        print('NIE')
else:
    r,c=first
    print('TAK')
    ans=0
    for i in range(n):
        if i !=r:
            ans=ans^mat[i][0]
        else:
            ans=ans^mat[i][c]
    if ans>0:
        for i in range(n):
            if i !=r:
                print(0+1,end=' ')
            else:
                print(c+1,end=' ')
    else:
        for i in range(n):
            if i !=r:
                print(0+1,end=' ')
            else:
                print(c+2,end=' ')





import sys
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
n,m = map(int,input().split())
a = [list(map(int,input().split())) for i in range(n)]
ans = [1]*n
res = 0
for i in range(n):
    res ^= a[i][0]
if res != 0:
    print("TAK")
    print(*ans)
    return

for i in range(n):
    res ^=a[i][0]
    for j in range(m):
        res ^=a[i][j]
        if res != 0:
            ans[i] = j+1
            print("TAK")
            print(*ans)
            return
        res ^=a[i][j]
    res ^= a[i][0]
print("NIE")

n, m = [int(i) for i in input().split()]
a = [[int(i) for i in input().split()] for _ in range(n)]


def test(a, n ,m):
    for i in range(n):
        _or, _and = a[i][0], a[i][0]
        for j in range(m):
            _or |= a[i][j]
            _and &= a[i][j]
        if _or != _and:
            return i
    return -1

t = test(a, n, m)
if t == -1:
    _xor = 0
    for i in range(n):
        _xor ^= a[i][0]
    if _xor > 0:
        print('TAK')
        print(' '.join('1' for _ in range(n)))
        return
else:
    _xor = 0
    for i in range(n):
        if i == t:
            continue
        _xor ^= a[i][0]
    for j in range(m):
        if _xor ^ a[t][j] > 0:
            print('TAK')
            print(' '.join(['1' if k != t else str(j + 1) for k in range(n)]))
            return
print('NIE')


import sys
input = sys.stdin.readline

n,m=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(n)]

for b in range(10):
    RB=[0]*n
    for j in range(n):
        SCORE=[]
        for k in range(m):
            if A[j][k] & (1<<b)==0:
                SCORE.append(0)
            else:
                SCORE.append(1)

        SCORE=sorted(set(SCORE))

        if len(SCORE)==2:
            print("TAK")
            ANS=[1]*n
            XOR=0
            for k in range(n):
                if j==k:
                    continue
                XOR^=(A[k][0] & (1<<b))

            if XOR==0:
                for k in range(m):
                    if A[j][k] & (1<<b)!=0:
                        ANS[j]=k+1
                        print(*ANS)
                        return

            else:
                for k in range(m):
                    if A[j][k] & (1<<b)==0:
                        ANS[j]=k+1
                        print(*ANS)
                        return

        elif len(SCORE)==1:
            RB[j]=SCORE[0]

    XOR=0
    for i in range(n):
        XOR^=RB[i]

    if XOR==0:
        continue
    else:
        print("TAK")
        print(*[1]*n)
        return

else:
    print("NIE")
                
            
            


n,m = list(map(int,input().split()))
mat = [list(map(int,input().split())) for _ in range(n)]

# xr = 0
# for l in mat:
#     for i in l:
#         xr ^= i
#
# if xr == 0:
#     print('NIE')
#     return

res = []

for i in range(n):
    prev = -1
    for j in range(m):
        if prev == -1:
            prev = mat[i][j]
        elif prev != mat[i][j]:
            # mat[i][j - 1] と mat[i][j]
            xr = 0
            for k in range(n):
                if k != i:
                    xr ^= mat[k][0]
            if xr ^ mat[i][j - 1] != 0:
                res = [1] * (i) + [j] + [1] * (n - i - 1)
            else:
                res = [1] * (i) + [j + 1] + [1] * (n - i - 1)
            print('TAK')#, mat[i][j - 1], mat[i][j], xr)
            print(*res)
            return

xr = 0
for i in range(n):
    xr ^= mat[i][0]

if xr == 0:
    print('NIE')
else:
    print('TAK')
    res = [1] * n
    print(*res)


n, m = [int(t) for t in input().split()]

def xor(arr):
    t = 0
    for a in arr:
        t = t^a
    return t

a = []
win = False
j = 0
for i in range(n):
    tmp = [int(t) for t in input().split()]
    if len(set(tmp)) > 1:
        win = True
        j = i
    a.append(tmp)
if not win:
    if xor([t[0] for t in a]) == 0:
        print('NIE')
    else:
        print('TAK')
        print(' '.join(['1']*n))
else:
    print('TAK')
    if xor([t[0] for t in a]) != 0:
        print(' '.join(['1']*n))
    else:
        ans = ['1']*n
        k = 1
        while a[j][k] == a[j][0]:
            k += 1
        ans[j] = str(k + 1)
        print(' '.join(ans))

n,m=tuple(map(int,input().strip().split()))
mat=[]
for i in range(n):
    mmm=list(map(int,input().strip().split()))
    mat.append(mmm)
st=0
rnum=-1
cnum=-1
for i in range(n):
    for ii in range(m-1):
        if(mat[i][ii]!=mat[i][ii+1]):
            st=1
            rnum=i
            cnum=ii
            break
    if(st==1):
        break
if((not st) or m==1):
    hh=0
    sr=""
    for i in range(n):
        hh=hh^mat[i][0]
        sr=sr+str(1)+" "
    if(hh==0):
        print("NIE")
    else:
        print("TAK")
        print(sr)
else:
    print("TAK")
    sr=""
    hh=0
    for i in range(0,n):
        if(i!=rnum):
            hh = hh ^ mat[i][0]
    if(hh^mat[rnum][cnum]==0):
        for i in range(0, n):
            if (i != rnum):
                sr=sr+str(1)+" "
            else:
                sr=sr+str(cnum+2)+" "
    else:
        for i in range(0, n):
            if (i != rnum):
                sr=sr+str(1)+" "
            else:
                sr=sr+str(cnum+1)+" "
    print(sr)

m, n = list(map(int,input().split()))
matrix = [list(map(int,input().split())) for i in range(m)]
c = 0
x, y = 0, 0
dupa  = 1
for i in range(m):
	if dupa == 0:
		break
	cur = matrix[i][0]
	for j in range(n):
		if matrix[i][j] != cur:
			x = i
			y = j
			print("TAK")
			c = 1
			dupa = 0
			break
import sys
if c == 0:
	zor = 0
	for i in range(m):
		zor = (zor^matrix[i][0])
	if zor == 0:
		print("NIE")
		return
	else:
		print("TAK")
		for k in range(m):
			print(1, end = " ")
		return
else:
	for i in range(m):
		if i != x:
			print(1, end = " ")
		else:
			a = matrix[x][y]
			b = matrix[x][0]
			sor = 0
			for g in range(m):
				sor = (sor^matrix[g][0])
			if sor > 0:
				print(0+1, end = " ")
			else:
				print(y + 1, end =  " ")