Bob has a permutation of integers from 1 to n. Denote this permutation as p. The i-th element of p will be denoted as p_{i}. For all pairs of distinct integers i, j between 1 and n, he wrote the number a_{i}, j = min(p_{i}, p_{j}). He writes a_{i}, i = 0 for all integer i from 1 to n.

Bob gave you all the values of a_{i}, j that he wrote down. Your job is to reconstruct any permutation that could have generated these values. The input will be formed so that it is guaranteed that there is at least one solution that is consistent with the information given.


-----Input-----

The first line of the input will contain a single integer n (2 ≤ n ≤ 50).

The next n lines will contain the values of a_{i}, j. The j-th number on the i-th line will represent a_{i}, j. The i-th number on the i-th line will be 0. It's guaranteed that a_{i}, j = a_{j}, i and there is at least one solution consistent with the information given.


-----Output-----

Print n space separated integers, which represents a permutation that could have generated these values. If there are multiple possible solutions, print any of them.


-----Examples-----
Input
2
0 1
1 0

Output
2 1

Input
5
0 2 2 1 2
2 0 4 1 3
2 4 0 1 3
1 1 1 0 1
2 3 3 1 0

Output
2 5 4 1 3



-----Note-----

In the first case, the answer can be {1, 2} or {2, 1}.

In the second case, another possible answer is {2, 4, 5, 1, 3}.

Difficulty: competition

Starter code:

Solutions:
def main():
    n = int(input())
    a = [[int(i) for i in input().split()] for j in range(n)]
    
    result = [-1] * n
    for i in range(n - 1):
        for j in range(n):
            d = set(a[j][k] for k in range(n) if result[k] == -1 and j != k)
            if len(d) == 1:
                result[j] = d.pop()
    result[result.index(-1)] = n
    
    print(' '.join(str(i) for i in result))
    
main()

n = int(input())
arr = [list(map(int, input().split())) for i in range(n)]
ans = []
for i in arr:
	anf = max(i)
	while (anf in ans):
		anf+=1
	ans.append(anf)
print(*ans)

n = int(input())
for i in range(n):
    k = list(map(int, input().split()))
    if len(set(k)) == n:
        k[k.index(0)] = n
        print(*k)
        break

v = [max(map(int, input().split())) for i in range(int(input()))]
v[v.index(max(v))] += 1
print(' '.join(map(str, v)))

n = int(input())
perm = [0 for i in range(n)]
a = [[0 for i in range(n)] for i in range(n)]
b = [0 for i in range(n)]
for i in range(n):
    a[i] = list(map(int, input().split()))
    b[i] = max(a[i])

s = set()

for i in range(1, n + 1):
    for j in range(n):
        if b[j] <= i and j not in s:
            perm[j] = i
            s.add(j)
            break
print(*perm)


3

def remove(A, i, n):
    for j in range(n):
        A[i][j] = 0
        A[j][i] = 0


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

ans = [0 for i in range(n)]
for i in range(n - 1):
    t = -1
    for j in range(n):
        f = True
        g = False
        for k in range(n):
            if not (A[j][k] in (0, i + 1) and A[k][j] in (0, i + 1)):
                f = False
            if A[j][k] != 0:
                g = True
        if f and g:
            t = j


    ans[t] = i + 1
    remove(A, t, n)


for i in range(n):
    if ans[i] == 0:
        ans[i] = n

print(" ".join(map(str, ans)))
                


N = int(input())
mat = [[int(x) for x in input().split()] for _ in range(N)]
a = list(range(N))
for row in mat:
    if sorted(row) == a:
        row[row.index(0)] = N
        print(*row)
        break
else:
    assert(0)


n = int(input())
l = [list(map(int, input().split())) for i in range(n)]
p = [-1 for i in range(n)]
for i in range(n):
    for j in range(1, n+1):
        if l[i].count(j) == n-j:
            p[i] = j
            break
if p.count(n-1) == 2:
    p[p.index(n-1)] = n
print(" ".join(map(str, p)))


#!/usr/bin/env python3
N = int(input())

min_arr = [0 for _ in range(N)]

for i in range(N):
    arr_i = [n-1 for n in map(int, input().split())]
    for j in range(N):
        if i == j:
            continue
        min_arr[i] = max(arr_i[j], min_arr[i])
        min_arr[j] = max(arr_i[j], min_arr[j])

assign = [0 for _ in range(N)]
blah = [(min_arr[i], i) for i in range(N)]
blah.sort()
for i in range(N):
    assign[blah[i][1]] = i+1

print(' '.join(map(str, assign)))


n = int(input())

target = [x for x in range(n)]
for i in range(n):
    v = list(map(int, input().split()))

    if sorted(v) == target:
        print(' '.join([str(x) if x != 0 else str(n) for x in v]))
        return




n = int(input())
a = [list(map(int, input().split())) for x in range(n)]
result = [0] * n
for x in range(1, n):
    result[max(list(range(n)), key = lambda i: a[i].count(x))] = x
print(*[(x if x else n) for x in result])


n = int(input())
pole = []
for i in range(n):
    s = list(map(int, input().split()))
    pole.append(s)

ans = [0] * n
for number in range(1, n + 1):
    for i in range(n):
        s = set()
        for j in range(n):
            if pole[i][j] > number - 1:
                s.add(pole[i][j])
        if len(s) == 1:
            for k in s:
                ans[i] = k
for i in range(n):
    if ans[i] == n - 1:
        ans[i] = n
        break
print(*ans)


n = int(input())
M = [[int(x) for x in input().split()] for i in range(n)]
last = False
perm = [0 for i in range(n)]
for i in range(n):
    S = set()
    for x in M[i]:
        if x in S:
            perm[i] = x
            break
        else:
            S.add(x)
    else:
        if last:
            perm[i] = n-1
        else:
            perm[i] = n
            last = True
for x in perm:
    print(x, end = ' ')


n = int(input())
p = []
for i in range(n):
    p.append(list(map(int, input().split())))
    p[i].sort()
    p[i].append(i)
p.sort()
pos = [0] * n
for i in range(n):
    pos[p[i][-1]] = i + 1
print(*pos)

    
    
        


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

ans = [0 for i in range(n)]
for cur in range(1, n + 1):
    k = -1
    for i, row in enumerate(a):
        if all((x <= cur for x in row)):
            k = i
            break
    #assert(k != -1)
    for i in range(len(row)):
        row[i] = 999
    ans[k] = cur
print(' '.join(map(str, ans)))


n = int(input())
s = [0] * n
dp = [[0] for i in range(n)]
for i in range(n):
    dp[i] = list(map(int, input().split()))
for i in range(n):
    for j in range(n):
        s[i] = max(s[i], dp[i][j])
        s[j] = max(s[j], dp[i][j])
used = [False] * n
for i in range(n):
    if used[s[i] - 1]:
        s[i] *= -1
    else:
        used[s[i] - 1] = True
for i in range(n):
    if s[i] < 0:
        for j in range(1, n + 1):
            if abs(s[i]) < j and not used[j - 1]:
                s[i] = j
                break
print(*s)

#!/bin/python3
import sys
n = int(input())
matrix = []
for i in range(n):
    tlist = [int(a) for a in input().split(' ')]
    matrix.append(tlist)

for i in range(n):
    if set(range(n)) == set(matrix[i]):
        big = i
        break

for i in range(n):
    if i == big:
        sys.stdout.write("{} ".format(n))
    else:
        sys.stdout.write("{} ".format(matrix[big][i]))



#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2016 missingdays <missingdays@missingdays>
#
# Distributed under terms of the MIT license.

"""

"""

n = int(input())

a = []

for i in range(n):
    a.append([int(i) for i in input().split()])

b = [0 for i in range(n)]
c = {}

for i in range(n):
    for j in range(n):
        c[j] = 0

    for j in range(n):
        c[a[i][j]] += 1

    for j in range(n):
        if j in c and c[j] > 1:
            b[i] = j 

i1 = -1
m = 0

for i in range(n):
    if b[i] == 0:
        l = max(a[i])

        if l > m:
            m = l
            i1 = i

b[i1] = n-1

for i in range(n):
    if b[i] == 0 and i != i1:
        b[i] = n

for e in b:
    print(e, end=" ")
print()


# from pprint import pprint

n = int(input())
a = []
for i in range(n):
    row = [int(k) for k in input().split()]
    a.append(row)

result = [0] * n
for k in range(1, n):
    # print('k=', k)
    for i in range(n):
        countK = 0
        countNonK = 0
        for j in range(n):
            if a[i][j] == k:
                countK += 1
            elif a[i][j] != 0:
                countNonK += 1
        # print('@', countK, countNonK)
        if countK > 0 and countNonK == 0:
            # print('j', j)
            result[i] = k
            for j in range(n):
                a[i][j] = 0
                a[j][i] = 0
            continue

        countK = 0
        countNonK = 0
        for j in range(n):
            if a[j][i] == k:
                countK += 1
            elif a[j][i] != 0:
                countNonK += 1
        if countK > 0 and countNonK == 0:
            # print('j#', j)
            result[i] = k
            for j in range(n):
                a[j][i] = 0
                a[i][j] = 0
    # pprint(a)
result[result.index(0)] = n

print(' '.join(str(i) for i in result))



n = int(input())
numbers = [0] * n
used = set()
for i in range(n):
    for j in range(max(list(map(int, input().split()))), n + 1):
        if j not in used:
            used.add(j)
            numbers[i] = j
            break
print(' '.join(map(str, numbers)))


from itertools import chain
n = int(input())

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

for i in range(n):
    a[i][i] = i

ans = []

while n > 0:
    done = False
    for i in chain(range(1, n-1), [0, n-1]):
        if done:
            break
        b = True
        for dx in -1, 0, 1:
            for dy in -1, 0, 1:
                if dx != 0 and dy != 0:
                    continue
                if dx == 0 and dy == 0:
                    continue
                nx, ny = i+dx, i+dy
                if nx < 0 or nx >= n:
                    continue
                if ny < 0 or ny >= n:
                    continue
                b = b and a[nx][ny] == 1
        if b:
            ans.append(a[i][i])
#            print(ans)
            if i < n - 1:
                a = a[:i] + a[i+1:]
            else:
                a = a[:i]
            for j in range(len(a)):
                if i < n - 1:
                    a[j] = a[j][:i] + a[j][i+1:]
                else:
                    a[j] = a[j][:i]
            for x in range(len(a)):
                for y in range(len(a)):
                    if x == y:
                        continue
                    a[x][y] -= 1
            n -= 1
            done = True
    if not done:
        return
#    for x in a:
#        for y in x:
#            print(y, end = ' ')
#        print()


ret = [0] * len(ans)
for i in range(len(ans)):
    ret[ans[i]] = i + 1

for i in ret:
    print(i, end = ' ')


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

import time


n   = int(input())
a   = []

for i in range(n):
    a.append(max([int(i) for i in input().split()]))

start = time.time()

for i in range(n):
    if a[i] == n-1:
        a[i] += 1
        break

for i in a:
    print(i, end=' ')
print()

finish = time.time()
#print(finish - start)


n = int(input())
a = [list(map(int, input().split(' '))) for i in range(n)]
ans = [0]*n
for i in range(1, n+1):
    for j in range(n):
        if ans[j] == 0 and a[j].count(i) == n-i:
            ans[j] = str(i)
            break
print(' '.join(ans))


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

for i in range(n):
    is_dif = True
    for j in range(n):
        c = a[i].count(a[i][j])
        if c > 1:
            is_dif = False
            break
    if is_dif:
        for k in range(n):
            if a[i][k] == 0:
                a[i][k] = n
            print(a[i][k],end=' ')
        break

n = int(input())

a = [0]*n
for i in range(n):
	a[i] = list(map(int, input().split()))
unused = set(range(1,n+1))
used = {0}
bind = [-1]*(n)
for cur in range(1, n+1):
	for i in range(n):
		if (bind[i]==-1) and (max(a[i])<=cur):
			bind[i] = cur
			break
print(' '.join(map(str, bind)))