AtCoder Grand Contest 030 - Coloring Torus

For an n \times n grid, let (r, c) denote the square at the (r+1)-th row from the top and the (c+1)-th column from the left. A good coloring of this grid using K colors is a coloring that satisfies the following:

* Each square is painted in one of the K colors.
* Each of the K colors is used for some squares.
* Let us number the K colors 1, 2, ..., K. For any colors i and j (1 \leq i \leq K, 1 \leq j \leq K), every square in Color i has the same number of adjacent squares in Color j. Here, the squares adjacent to square (r, c) are ((r-1)\; mod\; n, c), ((r+1)\; mod\; n, c), (r, (c-1)\; mod\; n) and (r, (c+1)\; mod\; n) (if the same square appears multiple times among these four, the square is counted that number of times).



Given K, choose n between 1 and 500 (inclusive) freely and construct a good coloring of an n \times n grid using K colors. It can be proved that this is always possible under the constraints of this problem,

Constraints

* 1 \leq K \leq 1000

Input

Input is given from Standard Input in the following format:


K


Output

Output should be in the following format:


n
c_{0,0} c_{0,1} ... c_{0,n-1}
c_{1,0} c_{1,1} ... c_{1,n-1}
:
c_{n-1,0} c_{n-1,1} ... c_{n-1,n-1}


n should represent the size of the grid, and 1 \leq n \leq 500 must hold. c_{r,c} should be an integer such that 1 \leq c_{r,c} \leq K and represent the color for the square (r, c).

Examples

Input

2


Output

3
1 1 1
1 1 1
2 2 2


Input

9


Output

3
1 2 3
4 5 6
7 8 9

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
def solve(k):
	if k == 1:
		print(1)
		print(1)
		return
	n = ((k - 1) // 4 + 1) * 2
	ans = [[0] * n for _ in [0] * n]
	dub = 2 * (k - n)
	for m in range(n * 2):
		l = m + 1 if m < dub else dub + (m - dub) // 2 + 1
		i = m % 2
		j = (m // 2 + m % 2) % n
		for _ in range(n // 2):
			ans[i][j] = l
			i = (i + 2) % n
			j = (j + 2) % n
	print(n)
	print('\n'.join((' '.join(map(str, row)) for row in ans)))
k = int(input())
solve(k)


from math import sqrt, ceil
K = int(input())
if K <= 500:
	print(K)
	for i in range(K):
		Cout = [i + 1 for n in range(K)]
		print(' '.join(map(str, Cout)))
else:
	lim = int(sqrt(K))
	for i in range(2, lim + 1):
		if K % i ** 2 == 0:
			print(K // i)
			for n in range(K // i):
				Cout = [i * n + mod % i + 1 for mod in range(K // i)]
				print(' '.join(map(str, Cout)))
			break
	else:
		n = 2 * ceil(K / 4)
		print(n)
		for raw in range(n):
			if raw % 2 == 0:
				Cout = [(raw + c) % n + 1 for c in range(n)]
			else:
				Cout = [n + 1 + (raw + c) % n for c in range(n)]
				for i in range(n):
					if Cout[i] > K:
						Cout[i] -= n
			print(' '.join(map(str, Cout)))


K = int(input())
if K == 1:
	print(1)
	print(1)
	exit()
m = -(-K // 4)
n = 2 * m
a = [[0 for i in range(n)] for i in range(n)]
for r in range(n):
	for c in range(n):
		p = -1
		if r % 2 == 0:
			p = (r + c) % n
		else:
			p = n + (r + c) % n
		if p >= K:
			p -= n
		a[r][c] = p
s = [[str(a[i][j] + 1) for i in range(n)] for j in range(n)]
print(n)
for line in s:
	print(' '.join(line))


import math
k = int(input())
if k == 1:
	print(1)
	print(1)
	exit()
n = math.ceil(k / 4) * 2
ans = []
for i in range(n):
	tmp = []
	for j in range(n):
		if i % 2 == 0:
			tmp.append((i + j) % n + 1)
		else:
			tmp.append(n + (i + j) % n + 1)
	ans.append(tmp)
kazu = n * 2
while kazu != k:
	for i in range(n):
		for j in range(n):
			if ans[i][j] == kazu:
				ans[i][j] -= n
	kazu -= 1
print(n)
for i in range(n):
	print(*ans[i])


k = int(input())
if k == 1:
	print(1)
	print(1)
	exit()
n = (k + 3) // 4 * 2
l = 2 * n - k
print(n)
for i in range(n):
	for j in range(n):
		if j % 2 == 0 or (i + j) % n >= n - l:
			print((i + j) % n + 1, end=' ')
		else:
			print(n + (i + j) % n + 1, end=' ')
	print('')


def run(K):
	n_max = 500
	n = 0
	trouts = []
	if K <= n_max:
		n = K
		for i in range(K):
			trouts.append([i + 1] * K)
	else:
		n = n_max
		change = n_max * 2 - K
		c1 = [i for i in range(1, n_max + 1)]
		c2 = [i for i in range(2, change + 1)] + [i for i in range(n_max + 1, n_max * 2 + 1 - change)]
		if change > 0:
			c2 += [1]
		for i in range(n_max):
			shift = i // 2 * 2
			if i % 2 == 0:
				trouts.append(c1[shift:] + c1[:shift])
			else:
				trouts.append(c2[shift:] + c2[:shift])
	return (n, trouts)

def main():
	K = int(input())
	(n, trouts) = run(K)
	print(n)
	for i in range(len(trouts)):
		print(' '.join(map(str, trouts[i])))
main()


K = int(input())
M = 1000

def a(i, j):
	tmp = (i - j) % (M // 2) + 1
	if j % 2 == 0 or M + 1 - tmp > K:
		return tmp
	else:
		return M + 1 - tmp
if K <= M // 2:
	print(K)
	for i in range(K):
		print(*[i + 1] * K)
else:
	print(M // 2)
	for j in range(M // 2):
		print(*[a(i, j) for i in range(M // 2)])


k = int(input())
if k <= 500:
	n = k
	print(n)
	for i in range(n):
		print(*list(range(1, 1 + n)))
else:
	n = 2 * ((k + 3) // 4)
	ans = [[0] * n for i in range(n)]
	for i in range(n):
		for j in range(n):
			ans[i][j] = (i + j) % n + 1
			if i % 2 and ans[i][j] + n <= k:
				ans[i][j] += n
	print(n)
	for i in ans:
		print(*i)


n = int(input())
if n <= 500:
	print(n)
	for i in range(n):
		print(' '.join([str(i + 1)] * n))
	exit()
m = (n + 4 - 1) // 4 * 2
print(m)
for i in range(m):
	if i % 2 == 0:
		print(' '.join([str((i + j) % m % n + 1) for j in range(m)]))
	else:
		print(' '.join([str(m + (i + j) % m + 1 if m + (i + j) % m < n else (i + j) % m + 1) for j in range(m)]))


k = int(input())
if k == 1:
	print(1)
	print(1)
else:
	n = (k + 3) // 4 * 2
	ans = [[0 for _ in range(n)] for _ in range(n)]
	for i in range(n):
		for j in range(n):
			if i % 2 == 0:
				ans[i][j] = (i + j) % n + 1
			elif (i + j) % n + n + 1 > k:
				ans[i][j] = (i + j) % n + 1
			else:
				ans[i][j] = (i + j) % n + n + 1
	print(n)
	for i in range(n):
		print(*ans[i])


K = int(input())
if K == 1:
	print(1)
	print(1)
	exit()
N = 2 * ((K + 3) // 4)
ans = [[0] * N for i in range(N)]
for i in range(N):
	for j in range(N):
		ans[i][j] = (i + j) % N + 1
		if i % 2 and ans[i][j] + N <= K:
			ans[i][j] += N
print(N)
for row in ans:
	print(*row)


K = int(input())
if K <= 500:
	print(K)
	for i in range(1, K + 1):
		print((str(i) + ' ') * K)
else:
	KUP = ((K + 1) // 2 + 3) // 4 * 4
	print(KUP)
	ANS = [[0] * KUP for i in range(KUP)]
	begin = 0
	for i in range(KUP):
		for j in range(KUP):
			if i % 2 == 0:
				ANS[i][(j + begin) % KUP] = j + 1
			else:
				ANS[i][(j + begin) % KUP] = j + 1 + KUP
		begin += 1
	for i in range(KUP * 2 - K):
		for j in range(KUP):
			for l in range(KUP):
				if ANS[j][l] == KUP * 2 - i:
					ANS[j][l] = KUP * 2 - i - KUP
	for ans in ANS:
		print(*ans)


k = int(input())
n = 500
if k <= n:
	print(k)
	l = list(range(1, k + 1)) + list(range(1, k + 1))
	for i in range(k):
		a = [str(x) for x in l[i:i + k]]
		print(' '.join(a))
else:
	print(n)
	for i in range(n):
		a = [str(1 + (i + j) % n + n * (i % 2 == 0 and 1 + (i + j) % n + n <= k)) for j in range(n)]
		print(' '.join(a))


K = int(input())
n = 0
n1 = 0
n2 = 0
n3 = 0
n4 = 0
n5 = 0
if K <= 499:
	n = K
	mat = [[0 for n1 in range(K)] for n2 in range(K)]
	for n1 in range(K):
		for n2 in range(K - n1):
			mat[n1][n1 + n2] = n2 + 1
	for n1 in range(K):
		for n2 in range(n1):
			mat[n1][n2] = K + n2 - n1 + 1
else:
	n = 500
	mat = [[0 for n1 in range(500)] for n2 in range(500)]
	for n1 in range(500):
		for n2 in range(500 - n1):
			mat[n1][n1 + n2] = n2 + 1
	for n1 in range(500):
		for n2 in range(n1):
			mat[n1][n2] = 500 + n2 - n1 + 1
	for n2 in range(K - 500):
		for n1 in range(250):
			kari = n1 * 2 + n2
			if kari >= 500:
				kari = kari - 500
			mat[n1 * 2][kari] = n2 + 501
print(n)
if K <= 500:
	out = ''
	for n1 in range(K):
		out = ''
		for n2 in range(K):
			out = out + ' ' + str(mat[n1][n2])
		print(out)
else:
	out = ''
	for n1 in range(500):
		out = ''
		for n2 in range(500):
			out = out + ' ' + str(mat[n1][n2])
		print(out)


k = int(input())
mx = 500
if k <= mx:
	print(k)
	for i in range(1, k + 1):
		print(*[i] * k, sep=' ')
else:
	cv = [[0 for i in range(mx)] for j in range(mx)]
	for i in range(mx):
		for j in range(mx):
			cv[i][(i + j) % mx] = j + 1
			if i % 2 == 1 and j + 1 + mx <= k:
				cv[i][(i + j) % mx] += mx
	print(mx)
	for i in range(mx):
		print(*cv[i], sep=' ')


import collections

def solve(k):
	if k == 1:
		return (1, [[1]])
	n = (k + 3) // 4 * 2
	f = [[None] * n for _ in range(n)]
	for y in range(n):
		for x in range(n):
			f[y][x] = (y * n + (x - y) % n) % (2 * n) + 1
			if f[y][x] > n:
				if f[y][x] - n <= 2 * n - k:
					f[y][x] -= n
				else:
					f[y][x] -= 2 * n - k
	return (n, f)
k = int(input())
(n, f) = solve(k)
print(n)
for y in range(n):
	print(*f[y])


K = int(input())
if K == 1:
	print(1)
	print(1)
else:
	n = (K + 3) // 4 * 2
	print(n)
	for r in range(n):
		line = []
		for c in range(n):
			if r % 2 == 0:
				t = (r + c) % n + 1
			else:
				t = n + (r + c) % n + 1
			if t > K:
				t -= n
			line.append(t)
		print(*line)