The research center Q has developed a new multi-core processor. The processor consists of n cores and has k cells of cache memory. Consider the work of this processor.

At each cycle each core of the processor gets one instruction: either do nothing, or the number of the memory cell (the core will write an information to the cell). After receiving the command, the core executes it immediately. Sometimes it happens that at one cycle, multiple cores try to write the information into a single cell. Unfortunately, the developers did not foresee the possibility of resolving conflicts between cores, so in this case there is a deadlock: all these cores and the corresponding memory cell are locked forever. Each of the locked cores ignores all further commands, and no core in the future will be able to record an information into the locked cell. If any of the cores tries to write an information into some locked cell, it is immediately locked.

The development team wants to explore the deadlock situation. Therefore, they need a program that will simulate the processor for a given set of instructions for each core within m cycles . You're lucky, this interesting work is entrusted to you. According to the instructions, during the m cycles define for each core the number of the cycle, during which it will become locked. It is believed that initially all cores and all memory cells are not locked.


-----Input-----

The first line contains three integers n, m, k (1 ≤ n, m, k ≤ 100). Then follow n lines describing instructions. The i-th line contains m integers: x_{i}1, x_{i}2, ..., x_{im} (0 ≤ x_{ij} ≤ k), where x_{ij} is the instruction that must be executed by the i-th core at the j-th cycle. If x_{ij} equals 0, then the corresponding instruction is «do nothing». But if x_{ij} is a number from 1 to k, then the corresponding instruction is «write information to the memory cell number x_{ij}».

We assume that the cores are numbered from 1 to n, the work cycles are numbered from 1 to m and the memory cells are numbered from 1 to k.


-----Output-----

Print n lines. In the i-th line print integer t_{i}. This number should be equal to 0 if the i-th core won't be locked, or it should be equal to the number of the cycle when this core will be locked.


-----Examples-----
Input
4 3 5
1 0 0
1 0 2
2 3 1
3 2 0

Output
1
1
3
0

Input
3 2 2
1 2
1 2
2 2

Output
1
1
0

Input
1 1 1
0

Output
0

Difficulty: interview

Starter code:

Solutions:
n, m, k = list(map(int, input().split()))
deadstep = [0] * (n+1)
badmem = [False] * (k+1)
a = [0] * (n+1)
for i in range(1, n+1):
    a[i] = [0] + list(map(int, input().split()))
for step in range(1, m+1):
    t = [0] * (k+1)
    for i in range(1, n+1):
        if deadstep[i] == 0 and a[i][step] != 0:
            t[a[i][step]] += 1
    for j in range(1, k+1):
        if t[j] > 1:
            badmem[j] = True
    for i in range(1, n+1):
        if deadstep[i] == 0 and badmem[a[i][step]]:
            deadstep[i] = step
for i in range(1, n+1):
    print(deadstep[i])


n,m,k=list(map(int,input().split()))
L=[]
for i in range(n):
    L.append(list(map(int,input().split())))

Locked=[-1]*n
Z={}
for i in range(m):
    K={}
    for j in range(n):
        if(Locked[j]!=-1):
            continue
        if(L[j][i] in K):
            K[L[j][i]].append(j)
        else:
            K[L[j][i]]=[j]
    for item in K:
        if(item==0):
            continue
        if(item in Z):
            for e in K[item]:
                if(Locked[e]==-1):
                    Locked[e]=i
        elif(len(K[item])>1):
            Z[item]=1
            for e in K[item]:
                if(Locked[e]==-1):
                    Locked[e]=i
for i in range(n):
    print(Locked[i]+1)


n, m, k = list(map(int, input().split()))
ans = [0 for i in range(n)]
lock = [False for i in range(k)]
deadlock = lock[:]
insset = [[0 for i in range(n)] for i in range(m)]
for i in range(n):
    ins = list(map(int, input().split()))
    for j in range(m):
        insset[j][i] = ins[j]
for r in range(m):
    ins = insset[r]
    for i, el in enumerate(ins):
        if el == 0 or ans[i]:
            continue
        if lock[el-1]:
            deadlock[el-1] = True
        else:
            lock[el-1] = True
    for i in range(n):
        if ins[i] == 0 or ans[i]:
            continue
        if deadlock[ins[i]-1]:
            ans[i] = r+1
    lock = [False for i in range(k)]
for el in ans:
    print(el)



n, m, k = list(map(int, input().split()))
x = [list([int(a) - 1 for a in input().split()]) for i in range(n)]
res = [-1] * n
locked = [False] * k
for t in range(m):
    w = [0] * k
    for i in range(n):
        if res[i] == -1 and x[i][t] != -1:
            w[x[i][t]] += 1

    for i in range(n):
        if res[i] == -1 and x[i][t] != -1 and (w[x[i][t]] >= 2 or locked[x[i][t]]):
            locked[x[i][t]] = True
            res[i] = t
res = [i + 1 for i in res]
for i in res:
    print(i)


n, m, k = map(int, input().split())
cores = [1 for i in range(n)]
cells = [1 for i in range(k)]
info = []
blockings = [0 for i in range(n)]
for i in range(n):
    k = list(map(int, input().split()))
    for j in range(len(k)):
        k[j] -= 1
    info.append(k)
for i in range(m):
    for j in range(n):
        if cores[j] == 0:
            continue
        cell = info[j][i]
        if cell == -1:
            continue
        if cells[cell] == 0:
            cores[j] = 0
            blockings[j] = i + 1
            continue
        for core in range(n):
            if core != j:
                cell_1 = info[core][i]
                if cell_1 == cell and blockings[core] == 0:
                    cells[cell] = 0
                    cores[j] = 0
                    blockings[j] = i + 1
                    break
for elem in blockings:
    print(elem)

b=input().split()
core=[]
kcore=int(b[0])
ktact=int(b[1])
for i in range(kcore):
    work=input().split()
    core.append([])
    for j in range(ktact):
        core[i].append(int(work[j]))
#...
zmemory=[]
for i in range(int(b[2])):
    zmemory.append(0)
zcore=[]
answer=[]
for i in range(kcore):
    zcore.append(0)
    answer.append(0)
#...
for i in range(ktact):
    freecore=[]
    for j in range(kcore):
        if zcore[j]==0:
            freecore.append(j)
    for j in freecore:
        if not(core[j][i]==0):
            if zmemory[core[j][i]-1]:
                zcore[j]=1
                answer[j]=i+1
            for k in freecore:
                if not(k==j):
                    if core[j][i]==core[k][i]:
                        zmemory[core[j][i]-1]=1
                        zcore[j]=1
                        answer[j]=i+1
                        zcore[k]=1
                        answer[k]=i+1
#...
for i in range(kcore):
    print(answer[i])


N,M,k = list(map(int,input().split()))
cash =[-1]*(k+1)
cash_lock = [False]*(k+1)
processers = [0]*(N)
process = []
for i in range(N):
    process.append(list(map(int,input().split())))
for j in range(M):
    for i in range(N):
        if processers[i]==0:
            if process[i][j] !=0:
                cash_num = process[i][j]
                if cash[cash_num] == -1 and not cash_lock[cash_num]:
                    cash[cash_num] = i
                elif cash_lock[cash_num]:
                    processers[i]=j+1
                elif cash[cash_num] != -1:
                    processers[i]=j+1
                    processers[cash[cash_num]] =j+1
                    cash_lock[cash_num] = True
    for i in range(1,k+1):
        cash[i] = -1
for i in range(N):
    print(processers[i])



n, m, k = map(int, input().split())
a = [[0 for i in range(m)] for j in range(n)]
inf = [0 for i in range(k + 1)]
stat = [True for i in range(n + 1)]
time = [0 for i in range(n + 1)]
for i in range(n):
    a[i] = list(map(int, input().split()))
for i in range(m):
    for j in range(1, n + 1):
        if stat[j]:
            current_core = inf[a[j - 1][i]]
            if current_core == 0 and a[j - 1][i]  != 0:
                inf[a[j - 1][i]] = j
            elif current_core == -1:
                stat[j], time[j] = False, i + 1
            elif a[j - 1][i] != 0:
                stat[current_core], time[current_core] = False, i + 1
                stat[j], time[j] = False, i + 1
                inf[a[j - 1][i]] = -1
    for p in range(len(inf)):
        if inf[p] != -1:
            inf[p] = 0
for i in range(1, n + 1):
    print(time[i])

n,m,k=list(map(int,input('').split()))
x={}
out=[]
memory=[]
for i in range(n):
    x[i]=list(map(int, input('').split()))
    out+=[(0)]
for j in range(m):
    for i in range(n):
        k=x[i][j]
        if k!=0:
            for q in range(n):
                if i!=q and out[i]==0:
                    for p in memory:
                        if p==k: 
                            out[i]=j+1
                            break
                    if k==x[q][j] and out[q]==0:
                        out[i]=j+1
                        out[q]=j+1
                        memory+=[(k)]
        
for i in range(n):
    print(out[i])

            
        
        



n,m,k=list(map(int,input('').split()))
x={}
out=[]
memory=[]
for i in range(n):
    x[i]=list(map(int, input('').split()))
    out+=[(0)]
for j in range(m):
    for i in range(n):
        k=x[i][j]
        if k!=0 and out[i]==0:
            for q in range(n):
                if i!=q:
                    for p in memory:
                        if p==k: 
                            out[i]=j+1
                            break
                    if k==x[q][j] and out[q]==0:
                        out[i]=j+1
                        out[q]=j+1
                        memory+=[(k)]
        
for i in range(n):
    print(out[i])

            
        
        



import sys
read = lambda: list(map(int, sys.stdin.readline().split()))
n, m, k = read()

table = []
for _ in range(n):
    table.append(read())
table = list(zip(*table))

locked_cells = set()
locked_procs = set()
lock_time = [0]*n
for t, ys in enumerate(table):
    cnt = [0]*(k+1)
    for i, c in enumerate(ys):
        if i not in locked_procs:
            cnt[c] += 1
    for c, cn in enumerate(cnt):
        if c > 0 and cn > 1:
            locked_cells.add(c)
    for i, c in enumerate(ys):
        if c in locked_cells and i not in locked_procs:
            locked_procs.add(i)
            lock_time[i] = t+1

for t in lock_time:
    print(t)


def main():
	n, m, k = map(int, input().split())
	M = [0] * n
	for i in range(n):
		M[i] = list(map(int, input().split()))
	bn = [0] * n
	bm = [0] * k
	for t in range(m):
		last = [-1] * k
		cnt = [0] * k
		for i in range(n):
			if bn[i] or not M[i][t]:
				continue
			if bm[M[i][t] - 1]:
				bn[i] = t + 1
			else:
				if last[M[i][t] - 1] != -1:
					bn[last[M[i][t] - 1]] = t + 1
				last[M[i][t] - 1] = i
				cnt[M[i][t] - 1] += 1
		for i in range(k):
			if cnt[i] > 1:
				bm[i] = t + 1
				bn[last[i]] = t + 1
	for i in range(n):
		print(bn[i])
	
main()

n,m,k=list(map(int,input().split()))
yadra=[0]*n
yach=[True]*(k+1)
yachzt=[[] for i in range(k+1)]
l2=[list(map(int,input().split())) for i in range(n)]
for i in range(m):
    for i2 in range(n):
        if l2[i2][i] and (not yadra[i2]):
            yachzt[l2[i2][i]].append(i2)
    for i2 in range(k+1):
        if (len(yachzt[i2])>=2) or (not yach[i2]) :
            yach[i2]=False
            for a in yachzt[i2]:
                yadra[a]=(i+1)
    yachzt=[[] for i2 in range(k+1)]
for fl in yadra:
    print(fl)
            


n, m, k = map(int, input().split())
cycles = [[] for x in range(m)]
for x in range(n):
    temp = list(map(int, input().split()))
    for i in range(m):
        cycles[i].append(temp[i])
active_cores, active_memory = [0] * n, [0] * (k + 1)
for i in range(m):
    temp = {}
    for j in range(n):
        if not active_cores[j]:
            temp[cycles[i][j]] = temp.get(cycles[i][j], []) + [j]
    for j in range(n):
        if (cycles[i][j]) and (not active_cores[j]) and (len(temp[cycles[i][j]]) > 1 or active_memory[cycles[i][j]]):
            active_cores[j] = active_memory[cycles[i][j]] = i + 1
print(*active_cores, sep = '\n')



def pretty_print_list(a):
    for aa in a:
        print(*aa)

n, m, k = map(int, input().split())
#print(n, m, k)

#x = [[-1] * m] * n
x = [[-1 for _ in range(m)] for _ in range(n)]
for i in range(n):
    z = [y for y in map(int, input().split(" "))]
#    print("i:n:", i, "z:", *z)
    for j in range(m):
        x[i][j] = z[j]
#       x[i] = [z for z in map(int, input().split(" "))]

#pretty_print_list(x)


d = {}
locked_cores = {}
locked_cells = {}

for i in range(m):
    d = {}
    for j in range(n):
        if x[j][i] != 0:
            if not j in locked_cores:
                c = d.get(x[j][i], [])
                c.append(j)        
                d[x[j][i]] = c
            
    for cell in d:
        if len(d[cell]) > 1:
            for core in d[cell]:
                if not core in locked_cores:
                    locked_cores[core] = i + 1
                if not cell in locked_cells:
                    locked_cells[cell] = i + 1
        for core in d[cell]:
            if cell in locked_cells:
                if not core in locked_cores:
                    locked_cores[core] = i + 1             
        
        
    #print(i, d); print("locked_cores:", locked_cores); print("locked_cells:", locked_cells)
    
    

for i in range(n):
    if i in locked_cores:
        print(locked_cores[i])
    else:
        print(0)

n, m, k = map(int, input().split())
k += 1
dead = [0] * n  # time of deadlock
block = [False] * k  # ceil is blocked
t = [tuple(map(int, input().split())) for i in range(n)]
for j, s in enumerate(zip(*t), 1):
    q = [[] for i in range(k)]
    for core, ceil in enumerate(s):
        if dead[core] == 0: q[ceil].append(core)
    for ceil in range(1, k):
        if not q[ceil]: continue
        if block[ceil] or len(q[ceil]) > 1:
            for core in q[ceil]: dead[core] = j
            block[ceil] = True
print('\n'.join(map(str, dead)))

__author__ = 'Lipen'

def main():
    n, m, k = map(int, input().split())
    data = []
    when = [0]*n
    blockedcells = set()
    blockedcores = set()

    for _ in range(n):
        data.append(list(map(int, input().split())))

    for j in range(m):
        operation = []
        for _ in range(k):
            operation.append([])

        for i in range(n):
            if i not in blockedcores:
                x = data[i][j] - 1
                if x>=0:
                    if x in blockedcells:
                        blockedcores.add(i)
                        when[i] = j+1
                    elif len(operation[x]) > 0:
                        blockedcells.add(x)
                        for core in operation[x]:
                            blockedcores.add(core)
                            when[core] = j+1
                        blockedcores.add(i)
                        when[i] = j+1
                    operation[x].append(i)

    for i in when:
        print(i)

main()

n, m, k = list(map(int, input().split()))
l = []

s = [0 for i in range(n)]
f = [False for i in range(k + 1)]

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

for j in range(m):
    b = [-1 for i in range(k + 1)]
    for i in range(n):
        if s[i] or not l[i][j]:
            continue
        if f[l[i][j]]:
            s[i] = j + 1
        if b[l[i][j]] == -1:
            b[l[i][j]] = i
        else:
            s[b[l[i][j]]] = j + 1
            s[i] = j + 1
            f[l[i][j]] = True

for i in s:
    print(i)

n, m, k = map(int,input().split())
ips = list()
for i in range(n):
    ips.append(list(map(int,input().split())))


locked = [-1] * (n)
lc = [-1] * (k)
for j in range(m):
    cells = [-1] * (k)
    for i in range(n):
        if locked[i] == -1:
            if ips[i][j]-1 > -1:
                if lc[ips[i][j]-1] == -1:
                   if cells[ips[i][j]-1] == -1:
                       cells[ips[i][j]-1] = i
                     
                   else:
                       lc[ips[i][j]-1] = 1
                       locked[i] = j
                       locked[cells[ips[i][j]-1]] = j
                      
                else:
                    locked[i] = j
                    
for i in range(n):
    print(locked[i]+1)

from collections import Counter
n, m, k = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
v, l = [0] * n, [False] * k
for j in range(m):
    c = Counter(a[i][j] for i in range(n))
    for i in range(n):
        if not v[i] and a[i][j] and (l[a[i][j] - 1] or c[a[i][j]] > 1):
            v[i] = j + 1
            l[a[i][j] - 1] = True
            a[i] = [0] * m
print(*v, sep='\n')


from collections import Counter
n, m, k = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
v, l = [0] * n, [False] * k
for j in range(m):
    c = Counter(a[i][j] for i in range(n))
    for i in range(n):
        if not v[i] and a[i][j] and (l[a[i][j] - 1] or c[a[i][j]] > 1):
            v[i] = j + 1
            l[a[i][j] - 1] = True
            a[i] = [0] * m
print(*v, sep='\n')


def adds(memtoproc,mem,proc):
    if mem in memtoproc:
        memtoproc[mem].append(proc)
    else:
        memtoproc[mem]=[proc]

def corr(arr,n,m):
    brokemems=set()
    stopprocs=[0]*n
    for c in range(m):
        memtoproc=dict()
        usemems=set()
        locmems=set()
        for d in range(n):
            if not arr[d][c] or stopprocs[d]:
                continue
            adds(memtoproc,arr[d][c],d)
            if arr[d][c] in usemems:
                locmems.add(arr[d][c])
            usemems.add(arr[d][c])
            if arr[d][c] in brokemems:
                if not stopprocs[d]:
                    stopprocs[d]=c+1
        for d in locmems:
            brokemems.add(d)
            procs=memtoproc[d]
            for x in procs:
                if not stopprocs[x]:
                    stopprocs[x]=c+1
    return stopprocs
            

n,m,k=list(map(int,input().split(' ')))
arr=[]
for c in range(n):
    arr.append(tuple(map(int,input().split(' '))))
procs=corr(arr,n,m)
for c in procs:
    print(c)



from collections import Counter

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

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

v, l = [0] * n, [False] * k

for j in range(m):

    c = Counter(a[i][j] for i in range(n))

    for i in range(n):

        if not v[i] and a[i][j] and (l[a[i][j] - 1] or c[a[i][j]] > 1):

            v[i] = j + 1

            l[a[i][j] - 1] = True

            a[i] = [0] * m

print(*v, sep='\n')





# Made By Mostafa_Khaled

from collections import defaultdict
n, m, k = [int(i) for i in input().split()]
cell = [0 for i in range(k+1)]
core = [0 for i in range(n+1)]

# if core is positive, it has been locked, same if a cell is positive
# core would access the cell

# n is the number of cores
# m is the number of cycle
# k is the number of cells

A = [[int(i) for i in input().split()] for j in range(n)] # reading in the n lines
A = [[0] + [row[i] for row in A] for i in range(len(A[0]))] # now i have tranpose it
# append 0 at the start

# now A is of size m+1 by n
# each row is a timestep

for t in range(m):
    cell_visited = defaultdict(set)
    for i in range(1, n+1): # go through each core
        if A[t][i] > 0 and core[i] == 0: # instruction to do something and the core is not locked
            if cell[A[t][i]] > 0: # the cell is locked, lock the core if it's not locked
                core[i] = t + 1
            elif cell[A[t][i]] == 0: # the cell is not locked
                cell_visited[A[t][i]].add(i)
    for i in cell_visited: #i is the index of the cell
        if len(cell_visited[i]) > 1:
            cell[i] = 1 # lock the cell
            for j in cell_visited[i]:
                core[j] = t + 1
for i in range(1, n+1):
    print(core[i])