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: MEDIUM_HARD
Tags: Implementation

Starter code:

Solutions:
(n, m, k) = 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])


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) = 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) = 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)


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)


(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) = 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)


__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) = map(int, input().split())
x = [list(map(lambda a: int(a) - 1, 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())
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) = 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)


(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')


(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)


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)]
A = [[int(i) for i in input().split()] for j in range(n)]
A = [[0] + [row[i] for row in A] for i in range(len(A[0]))]
for t in range(m):
	cell_visited = defaultdict(set)
	for i in range(1, n + 1):
		if A[t][i] > 0 and core[i] == 0:
			if cell[A[t][i]] > 0:
				core[i] = t + 1
			elif cell[A[t][i]] == 0:
				cell_visited[A[t][i]].add(i)
	for i in cell_visited:
		if len(cell_visited[i]) > 1:
			cell[i] = 1
			for j in cell_visited[i]:
				core[j] = t + 1
for i in range(1, n + 1):
	print(core[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)


(n, m, k) = 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)


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')


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])


import sys
(n, m, k) = [int(i) for i in sys.stdin.readline().split(' ')]
mem = set()
cpu = {}
x = [0] * n
for i in range(n):
	x[i] = [int(j) for j in sys.stdin.readline().split(' ')]
for i in range(m):
	dead = set([i for i in range(n)])
	dead -= cpu.keys()
	dead = [j for j in dead if x[j][i] > 0 and any((k != j and x[j][i] == x[k][i] for k in dead))]
	for j in dead:
		if not j in cpu.keys():
			cpu[j] = i
			mem.add(x[j][i])
	add = [j for j in range(n) if x[j][i] in mem]
	for j in add:
		if not j in cpu.keys():
			cpu[j] = i
for i in range(n):
	if i in cpu.keys():
		print(cpu[i] + 1)
	else:
		print(0)


(n, m, k) = map(int, input().split())
k += 1
dead = [0] * n
block = [False] * k
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)))


(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])


def pretty_print_list(a):
	for aa in a:
		print(*aa)
(n, m, k) = map(int, input().split())
x = [[-1 for _ in range(m)] for _ in range(n)]
for i in range(n):
	z = [y for y in map(int, input().split(' '))]
	for j in range(m):
		x[i][j] = z[j]
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
for i in range(n):
	if i in locked_cores:
		print(locked_cores[i])
	else:
		print(0)