diverta 2019 Programming Contest 2 - Diverta City

Diverta City is a new city consisting of N towns numbered 1, 2, ..., N.

The mayor Ringo is planning to connect every pair of two different towns with a bidirectional road. The length of each road is undecided.

A Hamiltonian path is a path that starts at one of the towns and visits each of the other towns exactly once. The reversal of a Hamiltonian path is considered the same as the original Hamiltonian path.

There are N! / 2 Hamiltonian paths. Ringo wants all these paths to have distinct total lengths (the sum of the lengths of the roads on a path), to make the city diverse.

Find one such set of the lengths of the roads, under the following conditions:

* The length of each road must be a positive integer.
* The maximum total length of a Hamiltonian path must be at most 10^{11}.

Constraints

* N is a integer between 2 and 10 (inclusive).

Input

Input is given from Standard Input in the following format:


N


Output

Print a set of the lengths of the roads that meets the objective, in the following format:


w_{1, 1} \ w_{1, 2} \ w_{1, 3} \ ... \ w_{1, N}
w_{2, 1} \ w_{2, 2} \ w_{2, 3} \ ... \ w_{2, N}
:  :     :
w_{N, 1} \ w_{N, 2} \ w_{N, 3} \ ... \ w_{N, N}


where w_{i, j} is the length of the road connecting Town i and Town j, which must satisfy the following conditions:

* w_{i, i} = 0
* w_{i, j} = w_{j, i} \ (i \neq j)
* 1 \leq w_{i, j} \leq 10^{11} \ (i \neq j)



If there are multiple sets of lengths of the roads that meet the objective, any of them will be accepted.

Examples

Input

3


Output

0 6 15
6 0 21
15 21 0


Input

4


Output

0 111 157 193
111 0 224 239
157 224 0 258
193 239 258 0

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
from itertools import combinations, permutations
N = int(input())
s = [1, 2, 4, 7, 12, 20, 29, 38, 52, 73]
w = [[0] * 10 for _ in range(10)]
w[0][1] = w[1][0] = 1
for n in range(3, N + 1):
	M = 0
	for perm in permutations(range(n - 1), n - 1):
		tmp = 0
		for i in range(n - 2):
			tmp += w[perm[i]][perm[i + 1]]
		M = max(M, tmp)
	M += 1
	for i in range(n - 1):
		w[i][n - 1] = w[n - 1][i] = M * s[i]
for i in range(N):
	print(' '.join([str(j) for j in w[i][:N]]))


import sys
input = sys.stdin.readline
import itertools
N = int(input())
A = [1, 2, 4]
for _ in range(12):
	sum_2 = set((x + y for (x, y) in itertools.combinations(A, 2)))
	avoid = set((x - y for (x, y) in itertools.product(sum_2, A)))
	x = min(set(range(1, 1000)) - avoid - sum_2 - set(A))
	A.append(x)
L = [[0] * (N - 1 - i) for i in range(N)]
x = 1
for n in range(N):
	L[n] = [x * a for a in A[:N - 1 - n]]
	if n < N - 2:
		x = L[n][-1] + L[n][-2]
graph = [[0] * N for _ in range(N)]
for i in range(N):
	for (j, x) in enumerate(L[i]):
		graph[i][i + j + 1] = x
		graph[i + j + 1][i] = x
for row in graph:
	print(*row)


N = int(input())
s = []
t = []
i = 1
while len(s) < N:
	if i in t or any((i + s_ in t for s_ in s)):
		i += 1
		continue
	t.append(i)
	for s_ in s:
		t.append(i + s_)
	s.append(i)
	i += 1
w = [[0] * 10 for _ in range(10)]
w[0][1] = w[1][0] = 1
M = 1
for n in range(3, N + 1):
	M += 1
	for i in range(n - 1):
		w[i][n - 1] = w[n - 1][i] = M * s[i]
	M += w[n - 1][n - 2] + w[n - 1][n - 3] - w[n - 2][n - 3] - 1
for i in range(N):
	print(' '.join([str(j) for j in w[i][:N]]))


def solve(n):
	if n == 2:
		print('0 1\n1 0')
		return
	can = []
	ban = set()
	k = 1
	while len(can) < 9:
		if k in ban or any((k + l in ban for l in can)):
			k += 1
			continue
		ban.add(k)
		ban.update((k + l for l in can))
		can.append(k)
		k += 1
	ans = [[0] * n for _ in [0] * n]
	ans[0][1] = ans[1][0] = 1
	longest_path = 1
	for i in range(2, n):
		np = longest_path + 1
		for (j, c) in zip(range(i), can):
			ans[i][j] = ans[j][i] = np * c
		longest_path += ans[i][i - 1] + ans[i][i - 2] - ans[i - 1][i - 2]
	print('\n'.join((' '.join(map(str, row)) for row in ans)))
n = int(input())
solve(n)


from itertools import permutations
import sys
sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep='\n')

def II():
	return int(sys.stdin.readline())

def MI():
	return map(int, sys.stdin.readline().split())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LLI(rows_number):
	return [LI() for _ in range(rows_number)]

def SI():
	return sys.stdin.readline()[:-1]

def main():
	n = II()
	base = [1, 2, 4, 7, 12, 20, 29, 38, 52, 73]
	ans = [[0] * n for _ in range(n)]
	ans[1][0] = ans[0][1] = 1
	for vn in range(3, n + 1):
		mx = 0
		for path in permutations(range(vn - 1)):
			cur = sum((ans[v0][v1] for (v0, v1) in zip(path, path[1:])))
			if cur > mx:
				mx = cur
		ans[vn - 1][0] = ans[0][vn - 1] = base[vn - 2] * (mx + 1)
		ans[vn - 1][vn - 2] = ans[vn - 2][vn - 1] = base[vn - 3] * (mx + 1)
		for j in range(1, vn - 2):
			ans[vn - 1][j] = ans[j][vn - 1] = base[j - 1] * (mx + 1)
	for row in ans:
		print(*row)
main()