Stepan had a favorite string s which consisted of the lowercase letters of the Latin alphabet. 

After graduation, he decided to remember it, but it was a long time ago, so he can't now remember it. But Stepan remembers some information about the string, namely the sequence of integers c_1, c_2, ..., c_{n}, where n equals the length of the string s, and c_{i} equals the number of substrings in the string s with the length i, consisting of the same letters. The substring is a sequence of consecutive characters in the string s.

For example, if the Stepan's favorite string is equal to "tttesst", the sequence c looks like: c = [7, 3, 1, 0, 0, 0, 0].

Stepan asks you to help to repair his favorite string s according to the given sequence c_1, c_2, ..., c_{n}. 


-----Input-----

The first line contains the integer n (1 ≤ n ≤ 2000) — the length of the Stepan's favorite string.

The second line contains the sequence of integers c_1, c_2, ..., c_{n} (0 ≤ c_{i} ≤ 2000), where c_{i} equals the number of substrings of the string s with the length i, consisting of the same letters.

It is guaranteed that the input data is such that the answer always exists.


-----Output-----

Print the repaired Stepan's favorite string. If there are several answers, it is allowed to print any of them. The string should contain only lowercase letters of the English alphabet. 


-----Examples-----
Input
6
6 3 1 0 0 0

Output
kkrrrq
Input
4
4 0 0 0

Output
abcd



-----Note-----

In the first test Stepan's favorite string, for example, can be the string "kkrrrq", because it contains 6 substrings with the length 1, consisting of identical letters (they begin in positions 1, 2, 3, 4, 5 and 6), 3 substrings with the length 2, consisting of identical letters (they begin in positions 1, 3 and 4), and 1 substring with the length 3, consisting of identical letters (it begins in the position 3).

Difficulty: HARD
Tags: Constructive algorithms

Starter code:

Solutions:
n = int(input())
a = [int(x) for x in input().split()]
cur = 'a'
s = ''
for i in reversed(range(n)):
	for j in range(0, a[i]):
		s += cur * (i + 1)
		cur = ('a', 'b')[cur == 'a']
	for j in reversed(range(i)):
		a[j] -= (i - j + 1) * a[i]
	a[i] = 0
print(s)


n = int(input())
c = [0] + list(map(int, input().split()))
ans = []
for i in reversed(range(1, n + 1)):
	for x in ans:
		c[i] -= x - i + 1
	ans += [i] * c[i]
a = True
for x in ans:
	print(end=('a' if a else 'b') * x)
	a = not a


n = int(input())
a = [0] + list(map(int, input().split()))
for i in range(n, 0, -1):
	for j in range(i + 1, n + 1):
		a[i] -= a[j] * (j - i + 1)
x = 'b'
for i in range(1, n + 1):
	for _ in range(a[i]):
		for __ in range(i):
			print(x, end='')
		x = chr(ord(x) ^ 1)


n = int(input())
c = list(map(int, input().strip().split()))
subStrings = []
alt = 0
for i in range(n - 1, -1, -1):
	while c[i] > 0:
		alt = (alt + 1) % 2
		if alt == 1:
			substr = 'a' * (i + 1)
			subStrings.append(substr)
		else:
			substr = 'b' * (i + 1)
			subStrings.append(substr)
		for j in range(i, -1, -1):
			c[j] -= i - j + 1
print(''.join(subStrings))


import sys
data = sys.stdin.read().split()
data.reverse()

def read():
	return int(data.pop())

def readStr():
	return data.pop()
n = read()
C = [0] + [read() for i in range(n)]
ans = ''
(ch, cht) = ('a', 'b')
for i in range(n, 0, -1):
	while C[i] > 0:
		for j in range(i):
			ans += ch
		(ch, cht) = (cht, ch)
		for j in range(1, i + 1):
			C[j] -= i - j + 1
print(ans)


import sys
n = int(input())
c = list(map(int, input().split()))
cc = ord('a')
ans = ''
cur = n - 1
if 1:
	cur = n - 1
	while cur >= 0:
		while c[cur] > 0:
			if chr(cc) > 'z':
				cc = ord('a')
			ans += chr(cc) * (cur + 1)
			c[cur] -= 1
			for i in range(cur):
				c[i] -= cur - i + 1
			cc += 1
		cur -= 1
	print(ans)


n = int(input())
arr = list(map(int, input().split()))
for i in range(n - 1, 0, -1):
	for j in range(i - 1, -1, -1):
		arr[j] -= arr[i] * (i - j + 1)
s = 'a'

def rev(c):
	if c == 'a':
		return 'b'
	else:
		return 'a'
for i in range(n):
	for j in range(arr[i]):
		s += rev(s[-1]) * (i + 1)
print(s[1:])


n = int(input())
a = list(map(int, input().split()))
cur = 0
k = 0
for i in range(n - 1, -1, -1):
	k += cur
	a[i] -= k
	k += a[i]
	cur += a[i]
b = [[0, 0]] * n
for i in range(n - 1, -1, -1):
	b[i] = [a[i], i + 1]
b.sort()
b.reverse()
pos = 0
cur = 'a'
ans = [' '] * n
while b[0][0] > 0:
	for i in range(pos, pos + b[0][1]):
		ans[i] = cur
	if cur == 'a':
		cur = 'b'
	else:
		cur = 'a'
	pos += b[0][1]
	b[0][0] -= 1
	for j in range(0, n - 1):
		if b[j][0] < b[j + 1][0]:
			temp = b[j]
			b[j] = b[j + 1]
			b[j + 1] = temp
for i in range(0, n):
	print(ans[i], end='')


n = int(input())
arr = list(map(int, input().split()))
c = 'a'
s = ''
for i in range(n - 1, -1, -1):
	for j in range(arr[i]):
		for k in range(0, i + 1):
			s += c
		if c == 'a':
			c = 'b'
		else:
			c = 'a'
	for l in range(i - 1, -1, -1):
		arr[l] -= (i - l + 1) * arr[i]
print(s)