John Doe started thinking about graphs. After some thought he decided that he wants to paint an undirected graph, containing exactly k cycles of length 3. 

A cycle of length 3 is an unordered group of three distinct graph vertices a, b and c, such that each pair of them is connected by a graph edge. 

John has been painting for long, but he has not been a success. Help him find such graph. Note that the number of vertices there shouldn't exceed 100, or else John will have problems painting it.


-----Input-----

A single line contains an integer k (1 ≤ k ≤ 10^5) — the number of cycles of length 3 in the required graph.


-----Output-----

In the first line print integer n (3 ≤ n ≤ 100) — the number of vertices in the found graph. In each of next n lines print n characters "0" and "1": the i-th character of the j-th line should equal "0", if vertices i and j do not have an edge between them, otherwise it should equal "1". Note that as the required graph is undirected, the i-th character of the j-th line must equal the j-th character of the i-th line. The graph shouldn't contain self-loops, so the i-th character of the i-th line must equal "0" for all i.


-----Examples-----
Input
1

Output
3
011
101
110

Input
10

Output
5
01111
10111
11011
11101
11110

Difficulty: MEDIUM_HARD
Tags: Sorting

Constructive algorithms

Graph algorithms

Greedy algorithms
Skill types: Sorting

Greedy algorithms

Starter code:

Solutions:
(n, k) = (0, int(input()))
p = [['0'] * 100 for i in range(100)]
while k:
	for i in range(n):
		if i > k:
			break
		p[n][i] = p[i][n] = '1'
		k -= i
	n += 1
print(n)
for i in range(n):
	print(''.join(p[i][:n]))


k = int(input())
i = 3
while (i - 2) * (i - 1) * i // 6 < k:
	i += 1
a = [[1 for j in range(i)] for k in range(i)]
b = (i - 2) * (i - 1) * i // 6
j = 0
while b > k:
	b -= i - 2
	a[j * 2][j * 2 + 1] = 0
	a[j * 2 + 1][j * 2] = 0
	j += 1
while k - b > 0:
	l = 3
	while (l - 2) * (l - 1) * l // 6 <= k - b:
		l += 1
	l -= 1
	b += (l - 2) * (l - 1) * l // 6
	for m in range(i):
		a[m] += [0] * (l - 2)
	for m in range(l - 2):
		a.append([0] * (i + l - 2))
	for m in range(i - 2, i - 2 + l):
		for n in range(i - 2, i - 2 + l):
			a[m][n] = 1
	i += l - 2
for j in range(i):
	a[j][j] = 0
print(i)
for j in a:
	print(''.join([str(l) for l in j]))


n = int(input())
a = []
MAXN = 100
for i in range(MAXN):
	a.append([0] * MAXN)
for i in range(3):
	for j in range(3):
		if i != j:
			a[i][j] = 1
cycles = 1
if cycles != n:
	for i in range(3, MAXN):
		if cycles == n:
			break
		a[i][0] = a[0][i] = 1
		a[i][1] = a[1][i] = 1
		cycles += 1
		if cycles == n:
			break
		how = 2
		for j in range(2, i):
			if j != i:
				if cycles + how <= n:
					a[i][j] = a[j][i] = 1
					cycles += how
					how += 1
					if cycles == n:
						break
print(MAXN)
for i in range(len(a)):
	for j in a[i]:
		print(j, end='')
	print()


def f_3(n):
	return n * (n - 1) * (n - 2) // 6

def f_2(n):
	return n * (n - 1) // 2
a_3 = [f_3(i) for i in range(100)]
a_2 = [f_2(i) for i in range(100)]

def find_2(x, a):
	arr = []
	cur = len(a) - 1
	while x > 0:
		while x < a[cur]:
			cur -= 1
		arr.append(cur)
		x -= a[cur]
	return arr

def find_3(x, a):
	cur = len(a) - 1
	while x < a[cur]:
		cur -= 1
	x -= a[cur]
	return (cur, x)

def build(x):
	(base, remain) = find_3(x, a_3)
	arr = find_2(remain, a_2)
	n = base
	if len(arr) > 0:
		n += len(arr)
	m = [[0] * n for _ in range(n)]
	for i in range(base):
		for j in range(base):
			if i == j:
				continue
			m[i][j] = 1
			m[j][i] = 1
	for (i, x) in enumerate(arr):
		for j in range(x):
			m[base + i][j] = 1
			m[j][base + i] = 1
	return m

def pr(m):
	for i in range(len(m)):
		print(''.join([str(x) for x in m[i]]))
k = int(input())
m = build(k)
print(len(m))
pr(m)


n = 100
g = [set() for i in range(n)]
k = int(input())
ans = 0
flag = False
for l in range(n):
	for r in range(l + 1):
		if l == r or l in g[r]:
			continue
		count = 0
		for u in range(n):
			if u == l or u == r:
				continue
			if l in g[u] and r in g[u]:
				count += 1
		if count + ans <= k:
			ans += count
			g[l].add(r)
			g[r].add(l)
		if ans == k:
			flag = True
			break
	if flag:
		break
ans = [[0 for i in range(n)] for j in range(n)]
print(100)
for i in range(n):
	for j in range(n):
		if j in g[i]:
			ans[i][j] = 1
	print(*ans[i], sep='')


k = int(input())
p = [['0'] * 100 for j in range(100)]
g = lambda n: n * (n * n - 1) // 6
i = n = 0
while g(n + 1) <= k:
	n += 1
while i < n + 1:
	for j in range(i):
		p[i][j] = p[j][i] = '1'
	i += 1
k -= g(n)
g = lambda n: n * n - n >> 1
while k:
	n = 0
	while g(n + 1) <= k:
		n += 1
	for j in range(n):
		p[i][j] = p[j][i] = '1'
	k -= g(n)
	i += 1
print(i)
for j in range(i):
	print(''.join(p[j][:i]))


import sys
import math
c = int(input())
Ans = []
F = [1]
for i in range(1, 101):
	F.append(F[-1] * i)
for i in range(100):
	Ans.append([0] * 100)
print(100)
cycles = 1
Ans[0][1] = 1
Ans[1][0] = 1
Ans[1][2] = 1
Ans[2][1] = 1
Ans[0][2] = 1
Ans[2][0] = 1
m = 3
while cycles < c:
	Ans[0][m] = 1
	Ans[m][0] = 1
	inc = 1
	for j in range(1, m):
		Ans[j][m] = 1
		Ans[m][j] = 1
		cycles += inc
		inc += 1
		if cycles + inc > c:
			break
	m += 1
A = ''
for i in range(100):
	for j in range(100):
		A += str(Ans[i][j])
	A += '\n'
sys.stdout.write(A)


import os
import sys
from io import BytesIO, IOBase

def main():
	k = int(input())
	l = 3
	r = 100
	while l <= r:
		n = l + (r - l >> 1)
		if n * (n - 1) * (n - 2) // 6 <= k:
			l = n + 1
		else:
			r = n - 1
	n = l - 1
	ans = [[0 for _ in range(100)] for _ in range(100)]
	for i in range(n):
		for j in range(i + 1, n):
			ans[i][j] = ans[j][i] = 1
	k -= n * (n - 1) * (n - 2) // 6
	while k > 0:
		z = 2
		while (z + 1) * z >> 1 <= k:
			z += 1
		k -= z * (z - 1) >> 1
		n += 1
		for i in range(z):
			ans[i][n] = ans[n][i] = 1
	print(n + 1)
	for i in range(n + 1):
		print(*ans[i][:n + 1], sep='')
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()