You are given an integer array a_1, a_2, ..., a_n, where a_i represents the number of blocks at the i-th position. It is guaranteed that 1 ≤ a_i ≤ n. 

In one operation you can choose a subset of indices of the given array and remove one block in each of these indices. You can't remove a block from a position without blocks.

All subsets that you choose should be different (unique).

You need to remove all blocks in the array using at most n+1 operations. It can be proved that the answer always exists.

Input

The first line contains a single integer n (1 ≤ n ≤ 10^3) — length of the given array.

The second line contains n integers a_1, a_2, ..., a_n (1 ≤ a_i ≤ n) — numbers of blocks at positions 1, 2, ..., n.

Output

In the first line print an integer op (0 ≤ op ≤ n+1).

In each of the following op lines, print a binary string s of length n. If s_i='0', it means that the position i is not in the chosen subset. Otherwise, s_i should be equal to '1' and the position i is in the chosen subset.

All binary strings should be distinct (unique) and a_i should be equal to the sum of s_i among all chosen binary strings.

If there are multiple possible answers, you can print any.

It can be proved that an answer always exists.

Examples

Input


5
5 5 5 5 5


Output


6
11111
01111
10111
11011
11101
11110


Input


5
5 1 1 1 1


Output


5
11000
10000
10100
10010
10001


Input


5
4 1 5 3 4


Output


5
11111
10111
10101
00111
10100

Note

In the first example, the number of blocks decrease like that:

{ 5,5,5,5,5 } → { 4,4,4,4,4 } → { 4,3,3,3,3 } → { 3,3,2,2,2 } → { 2,2,2,1,1 } → { 1,1,1,1,0 } → { 0,0,0,0,0 }. And we can note that each operation differs from others.

Difficulty: VERY_HARD
Tags: Constructive algorithms

Starter code:

Solutions:
n = int(input())
(v, c) = (list([[0, 0]]), list())
z = ['0' for i in range(n)]
for (i, x) in enumerate(input().split()):
	v.append([int(x), i])
v.sort(reverse=True)

def S_N_U_F_F(z, v, c):
	(y, k, x, count) = (-1, 0, len(v) - 1, len(v) - 1)
	while v[0][0] != 0:
		if k > 0 and k < len(v) - 1:
			z[v[y + k][1]] = '0'
		elif v[y + k][0] > 1 or v[y + k + 1][0] == 0:
			(v[y + k][0], z[v[y + k][1]], x) = (v[y + k][0] - 1, '1', i)
		else:
			z[v[y + k][1]] = '0'
		for i in range(0, y + k):
			(v[i][0], z[v[i][1]]) = (v[i][0] - 1, '1')
		for i in range(y + k + 1, len(v) - 1):
			if v[i][0] > 1 or (v[i][0] != 0 and v[i + 1][0] == 0):
				(v[i][0], z[v[i][1]], x) = (v[i][0] - 1, '1', i)
			else:
				z[v[i][1]] = '0'
		while v[y + 1][0] == count and count != 0:
			(y, k) = (y + 1, k - 1)
		if v[x - 1][0] == 1 or v[x][0] == 0:
			k = -1
		k += 1
		count -= 1
		c.append(''.join(z))
	return len(c)
print(S_N_U_F_F(z, v, c))
print('\n'.join(c))


n = int(input())
v = []
q = 0
z = ['0' for i in range(n)]
for i in input().split():
	v.append([int(i), q])
	q += 1
v.sort(reverse=True)
c = []

def predictor(v, z, index_off, index_on, n):
	global c
	if n == 0:
		for i in range(len(v)):
			if v[i][0] > 0:
				v[i][0] -= 1
				z[v[i][1]] = '1'
			else:
				z[v[i][1]] = '0'
		c.append(''.join(z))
		return v
	for i in range(len(v)):
		if index_off != i and (v[i][0] > 1 or (i == index_on and v[i][0] == 1)):
			v[i][0] -= 1
			z[v[i][1]] = '1'
		else:
			z[v[i][1]] = '0'
	c.append(''.join(z))
	return v

def generator(v, z, n):
	(y, x) = (-1, n - 1)
	q = 0
	while v[0][0] != 0:
		if v[x - 1][0] == 1 or v[x][0] == 0:
			y = -2
		while v[x][0] == 0:
			x -= 1
		if y >= 0:
			while v[y][0] - 1 == n:
				y += 1
				q += 1
		predictor(v, z, y, x, n)
		if y == -2:
			y = q
		else:
			y += 1
		n -= 1
	return n
generator(v, z, n)
print(len(c))
for i in c:
	print(i)


n = int(input())
(v, c) = (list([[0, 0]]), list())
z = ['0' for i in range(n)]
for (i, x) in enumerate(input().split()):
	v.append([int(x), i])
v.sort(reverse=True, key=lambda x: [x[0], -x[1]])

def S_N_U_F_F(z, v, c):
	(y, k, x, count) = (-1, 0, len(v) - 1, len(v) - 1)
	while v[0][0] != 0:
		if k > 0 and k < len(v) - 1:
			z[v[y + k][1]] = '0'
		elif v[y + k][0] > 1 or v[y + k + 1][0] == 0:
			(v[y + k][0], z[v[y + k][1]], x) = (v[y + k][0] - 1, '1', i)
		else:
			z[v[y + k][1]] = '0'
		for i in range(0, y + k):
			(v[i][0], z[v[i][1]]) = (v[i][0] - 1, '1')
		for i in range(y + k + 1, len(v) - 1):
			if v[i][0] > 1 or (v[i][0] != 0 and v[i + 1][0] == 0):
				(v[i][0], z[v[i][1]], x) = (v[i][0] - 1, '1', i)
			else:
				z[v[i][1]] = '0'
		while v[y + 1][0] == count and count != 0:
			(y, k) = (y + 1, k - 1)
		if v[x - 1][0] == 1 or v[x][0] == 0:
			k = -1
		k += 1
		count -= 1
		c.append(''.join(z))
	return len(c)

def S_N_U_F_F_(z, v, c):
	(x, count) = (len(v) - 1, len(v))
	while v[len(v) - 2][0] > 0:
		(count, k, s) = (count - 1, 0, 0)
		print('x =', x)
		for i in range(1, len(v) - 1):
			value = v[i][0]
			if value == count + 1 or (v[i - 1][0] == -1 + s and value == 1) or (value > 1 and i != x):
				if value == count:
					k += 1
				(v[i][0], z[v[i][1]]) = (v[i][0] - 1, '1')
				if v[i - 1][0] == -1 + s and v[i][0] == 0:
					print('v[i] =', v[i])
					(v[i][0], x, s) = (-1, len(v) - 1 - k, -1)
					v[x][0] -= 1
					z[v[x][1]] = '1'
			else:
				z[v[i][1]] = '0'
		x -= 1
		print(v, 'x:', x, 'count', count, 's:', s, 'k:', k)
		c.append(''.join(z))
		print(''.join(z))
	return len(c)

def predictor(v, z, index_off, index_on, n):
	global c
	if n == 0:
		for i in range(len(v)):
			if v[i][0] > 0:
				v[i][0] -= 1
				z[v[i][1]] = '1'
			else:
				z[v[i][1]] = '0'
		c.append(''.join(z))
		return
	for i in range(len(v)):
		if index_off != i and (v[i][0] > 1 or (i == index_on and v[i][0] == 1)):
			v[i][0] -= 1
			z[v[i][1]] = '1'
		else:
			z[v[i][1]] = '0'
	c.append(''.join(z))

def generator(v, z, n):
	(y, x, q) = (-1, n - 1, 0)
	while v[0][0] != 0:
		if v[x - 1][0] == 1 or v[x][0] == 0:
			y = -2
		if v[x][0] == 0:
			x -= 1
		if y >= 0:
			while v[y][0] - 1 == n:
				y += 1
				q += 1
		predictor(v, z, y, x, n)
		if y == -2:
			y = q
		else:
			y += 1
		n -= 1
	return len(c)
print(S_N_U_F_F(z, v, c))
print('\n'.join(c))


N = int(input())
O = list(map(int, input().split()))
strings = [['0' for i in range(N)] for i in range(N + 1)]
scores = sorted([(O[i], i) for i in range(N)], reverse=True)
T = [None for i in range(N)]
for (i, (num, ind)) in enumerate(scores):
	T[ind] = i
for (i, x) in enumerate(O):
	for j in range(x):
		strings[(T[i] + j) % (N + 1)][i] = '1'
strings = [s for s in strings if '1' in s]
print(len(strings))
for s in strings:
	print(''.join(s))


import os, sys, math
import collections
if os.path.exists('testing'):
	name = os.path.basename(__file__)
	if name.endswith('.py'):
		name = name[:-3]
	src = open(name + '.in.txt', encoding='utf8')
	input = src.readline
n = int(input().strip())
counts = [int(q) for q in input().strip().split()]
sorted_counts_map = list(sorted(((int(q), e) for (e, q) in enumerate(counts)), reverse=True))
sorted_counts = [q for (q, _) in sorted_counts_map]

def solve():
	res = [[0] * n for _ in range(n + 1)]
	for e in range(n):
		c = sorted_counts[e]
		for r in range(c):
			index = (r + e) % (n + 1)
			res[index][e] = 1
	res2 = [0] * n
	for r in res:
		for (e, (_, pos)) in enumerate(sorted_counts_map):
			res2[pos] = r[e]
		r[:] = res2[:]
	for x in range(len(res)):
		res[x] = ''.join((str(q) for q in res[x]))
	zeroes = '0' * n
	while res[-1] == zeroes:
		res.pop()
	return res
res = solve()
print(len(res))
for r in res:
	print(''.join(map(str, r)))