Barbara was late for her math class so as a punishment the teacher made her solve the task on a sheet of paper. Barbara looked at the sheet of paper and only saw n numbers a_1, a_2, …, a_n without any mathematical symbols. The teacher explained to Barbara that she has to place the available symbols between the numbers in a way that would make the resulting expression's value as large as possible. To find out which symbols were available the teacher has given Barbara a string s which contained that information.

<image>

It's easy to notice that Barbara has to place n - 1 symbols between numbers in total. The expression must start with a number and all symbols must be allowed (i.e. included in s). Note that multiplication takes precedence over addition or subtraction, addition and subtraction have the same priority and performed from left to right. Help Barbara and create the required expression!

Input

The first line of the input contains a single integer n (1 ≤ n ≤ 10^5) — the amount of numbers on the paper.

The second line of the input contains n integers a_1, a_2, …, a_n (0 ≤ a_i ≤ 9), where a_i is the i-th element of a.

The third line of the input contains the string s (1 ≤ |s| ≤ 3) — symbols allowed in the expression. It is guaranteed that the string may only consist of symbols "-", "+" and "*". It is also guaranteed that all symbols in the string are distinct.

Output

Print n numbers separated by n - 1 symbols — a mathematical expression with the greatest result. If there are multiple equally valid results — output any one of them.

Examples

Input


3
2 2 0
+-*


Output


2*2-0


Input


4
2 1 1 2
+*


Output


2+1+1+2

Note

The following answers also fit the first example: "2+2+0", "2+2-0", "2*2+0".

Difficulty: VERY_HARD
Tags: Greedy algorithms

Dynamic programming

Constructive algorithms
Skill types: Dynamic programming

Greedy algorithms

Starter code:

Solutions:
import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ops = input().strip()
if len(ops) == 1:
	print(ops.join(map(str, a)))
elif '+' in ops and '*' in ops:
	seqs = [[a[0]]]
	output = []
	for i in range(1, n):
		if a[i] == 0:
			if seqs[-1][-1] == 0:
				seqs[-1].append(a[i])
			else:
				seqs.append([a[i]])
		elif seqs[-1][-1] == 0:
			seqs.append([a[i]])
		else:
			seqs[-1].append(a[i])
	for seq in seqs:
		if seq[0] == 0:
			output.append('+'.join(map(str, seq)))
		else:
			prod = 1
			for i in seq:
				prod *= i
				if prod >= 2 * n:
					break
			if prod >= 2 * n:
				new_seq = ''
				l = 0
				r = len(seq) - 1
				for i in range(len(seq)):
					if seq[i] != 1:
						l = i
						break
				for i in range(len(seq) - 1, -1, -1):
					if seq[i] != 1:
						r = i
						break
				if l != 0:
					new_seq += '+'.join('1' * l) + '+'
				new_seq += '*'.join(map(str, seq[l:r + 1]))
				if r != len(seq) - 1:
					new_seq += '+' + '+'.join('1' * (len(seq) - 1 - r))
				output.append(new_seq)
				continue
			b = []
			lst = -1
			for i in seq:
				if i == 1:
					if lst != 1:
						b.append([-1, 1])
					else:
						b[-1][-1] += 1
				else:
					b.append([0, i])
				lst = i
			last_state = [[None] * 2 for i in range(len(b) + 1)]
			dp = [[-10 ** 9] * 2 for i in range(len(b) + 1)]
			dp[0][0] = 0
			dp[0][1] = 0
			for i in range(len(b)):
				mx = None
				state = None
				if dp[i][0] > dp[i][1]:
					mx = dp[i][0]
					state = [i, 0]
				else:
					mx = dp[i][1]
					state = [i, 1]
				if mx + b[i][1] > dp[i + 1][0]:
					dp[i + 1][0] = mx + b[i][1]
					last_state[i + 1][0] = ['+', state]
				prod = 1
				for j in range(i, len(b)):
					if b[j][0] == 0:
						prod *= b[j][1]
					if mx + prod > dp[j + 1][1]:
						dp[j + 1][1] = mx + prod
						last_state[j + 1][1] = ['*', state]
			solved_seq = []
			state = None
			if dp[len(b)][1] > dp[len(b)][0]:
				state = [len(b), 1]
			else:
				state = [len(b), 0]
			while state[0] != 0:
				next_state = last_state[state[0]][state[1]][1]
				operation = last_state[state[0]][state[1]][0]
				for i in range(state[0] - 1, next_state[0] - 1, -1):
					if b[i][0] == -1:
						solved_seq.append(operation.join('1' * b[i][1]) + operation)
					else:
						solved_seq.append(str(b[i][1]) + operation)
				if operation == '*':
					solved_seq[-1] = solved_seq[-1][:-1] + '+'
				state = next_state
			output.append(''.join(solved_seq)[-2::-1])
	print('+'.join(output))
elif '+' in ops:
	print('+'.join(map(str, a)))
elif '*' in ops:
	if 0 in a:
		output = []
		all_mult = 0
		for i in range(n - 1):
			if a[i + 1] == 0 and (not all_mult):
				output.extend([a[i], '-'])
				all_mult = 0
			else:
				output.extend([a[i], '*'])
		output.append(a[-1])
		print(*output, sep='')
	else:
		print('*'.join(map(str, a)))


n = int(input())
A = list(map(int, input().split()))
symbols = list(input())

def solve1(array):
	j = 0
	solution = []
	first = True
	while j < len(array):
		i = j
		if not first:
			solution.append('+')
		first = False
		if array[j] == 0:
			j += 1
			while j < len(array) and array[j] == 0:
				j += 1
			j -= 1
			solution.extend(list('+'.join(['0'] * (j - i + 1))))
		else:
			j += 1
			while j < len(array) and array[j] != 0:
				j += 1
			j -= 1
			sol = solve11(array[i:j + 1])
			solution.extend(sol)
		j += 1
	return ''.join(list(map(str, solution)))

def solve11(array):
	count = 0
	first_different_from_one_prefix = 0
	for i in range(len(array)):
		if array[i] != 1:
			break
		else:
			first_different_from_one_prefix = i + 1
	array = array[first_different_from_one_prefix:]
	first_part = '+'.join(['1'] * first_different_from_one_prefix)
	first_different_from_one_suffix = len(array) - 1
	for i in range(len(array) - 1, -1, -1):
		if array[i] != 1:
			break
		else:
			first_different_from_one_suffix = i - 1
	second_part = '+'.join(['1'] * (len(array) - 1 - first_different_from_one_suffix))
	array = array[:first_different_from_one_suffix + 1]
	SOLUTION = []
	if len(array) > 0:
		for i in range(0, len(array)):
			if array[i] > 2:
				count += 1
		if count >= 20:
			SOLUTION.extend(list('*'.join(list(map(str, array)))))
			SOLUTION = SOLUTION[::-1]
		else:
			DP = [0 for i in range(len(array))]
			DP_PARENTS = [-1 for i in range(len(array))]
			DP[0] = array[0]
			for i in range(0, len(array)):
				if array[i] == 1:
					DP[i] = DP[i - 1] + 1
					DP_PARENTS[i] = i - 1
					continue
				else:
					PROD = 1
					for k in range(i - 1, -2, -1):
						PROD *= array[k + 1]
						if k == -1:
							if DP[i] < PROD:
								DP[i] = PROD
								DP_PARENTS[i] = k
						elif DP[i] < DP[k] + PROD:
							DP[i] = DP[k] + PROD
							DP_PARENTS[i] = k
			current = len(array) - 1
			while current != -1:
				k = DP_PARENTS[current]
				for i in range(current, k, -1):
					SOLUTION.append(array[i])
					SOLUTION.append('*')
				SOLUTION.pop()
				SOLUTION.append('+')
				current = k
			SOLUTION.pop()
	RESULT = ''
	SOLUTION = list(map(str, SOLUTION[::-1]))
	parts = [first_part, ''.join(SOLUTION), second_part]
	parts = [part for part in parts if part != '']
	return '+'.join(parts)

def solve2(array):
	current = 0
	solution = []
	first_zero = None
	array = list(map(str, array))
	while current < len(array) and array[current] != '0':
		current += 1
	if current == len(array):
		if array[-1] == '0':
			return '*'.join(array[:-1]) + '-0'
		else:
			return '*'.join(array)
	elif current != 0:
		return '*'.join(array[0:current]) + '-' + '*'.join(array[current:])
	else:
		return '*'.join(array[current:])
MY_SOLUTION = None
if len(symbols) == 1:
	MY_SOLUTION = symbols[0].join(list(map(str, A)))
if len(symbols) == 2:
	if '+' in symbols and '-' in symbols:
		MY_SOLUTION = '+'.join(list(map(str, A)))
	if '+' in symbols and '*' in symbols:
		MY_SOLUTION = solve1(A)
	if '*' in symbols and '-' in symbols:
		MY_SOLUTION = solve2(A)
if len(symbols) == 3:
	MY_SOLUTION = solve1(A)
print(MY_SOLUTION)


from itertools import groupby, product

def main():
	n = int(input())
	ar = [int(t) for t in input().split()]
	ops = set(input())
	if len(ops) == 1:
		ans = [ops.pop()] * (n - 1)
	elif ops == {'+', '-'}:
		ans = ['+'] * (n - 1)
	elif ops == {'*', '-'}:
		ans = ['*'] * (n - 1)
		if 0 in ar:
			idx = ar.index(0)
			if idx > 0:
				ans[idx - 1] = '-'
	else:
		ans = ['?'] * (n - 1)

		def solve(l, r):
			while l < r:
				if ar[l] == 1:
					ans[l] = '+'
				else:
					break
				l += 1
			while l < r:
				if ar[r] == 1:
					ans[r - 1] = '+'
				else:
					break
				r -= 1
			if l == r:
				return
			A = ar[l:r + 1]
			S = max(sum(A), 2 * (r + 1 - l))
			P = 1
			for x in A:
				P *= x
				if P >= S:
					for j in range(l, r):
						ans[j] = '*'
					return
			nums = []
			conns = []
			cl = []
			i = l
			for (ones, it) in groupby(A, key=lambda x: x == 1):
				if ones:
					L = len(list(it))
					conns.append(L)
					cl.append(i)
					i += L
				else:
					p = 1
					for x in it:
						p *= x
						if i < r:
							ans[i] = '*'
						i += 1
					nums.append(p)
			best_seq = 0
			best_val = sum(A)
			for seq in range(2 ** len(conns)):
				i = 0
				cur = 0
				prod = nums[i]
				for h in range(len(conns)):
					op = seq & 1 << h
					if op:
						prod *= nums[i + 1]
					else:
						cur += prod + conns[i]
						prod = nums[i + 1]
					i += 1
				cur += prod
				if cur > best_val:
					best_val = cur
					best_seq = seq
			for h in range(len(conns)):
				op = best_seq & 1 << h
				ch = '*' if op else '+'
				for i in range(cl[h] - 1, cl[h] + conns[h]):
					ans[i] = ch
		l = 0
		for i in range(n):
			if ar[i] == 0:
				if i > 0:
					ans[i - 1] = '+'
				if i < n - 1:
					ans[i] = '+'
				if l < i - 1:
					solve(l, i - 1)
				l = i + 1
		if l < n - 1:
			solve(l, n - 1)
	res = [None] * (2 * n - 1)
	res[::2] = ar
	res[1::2] = ans
	print(*res, sep='')
main()


from itertools import accumulate, groupby
from functools import reduce

def prod(a):
	return reduce(lambda x, y: min(x * y, 10 ** 6), a, 1)

def solve_positive(a):
	if a == '':
		return '+'
	b = [''.join(v) for (_, v) in groupby(a, key=lambda x: x == '1')]
	if b[0][0] == '1':
		return '+' * len(b[0]) + solve_positive(a[len(b[0]):])
	if b[-1][0] == '1':
		return solve_positive(a[:-len(b[-1])]) + '+' * len(b[-1])
	p = [prod(map(int, x)) for x in b[::2]]
	q = [len(x) for x in b[1::2]]
	k = len(p)
	if prod(p) >= 10 ** 6:
		return '+' + '*' * (len(a) - 1) + '+'
	dp = [0] * k
	go = [k] * k
	for i in range(k)[::-1]:
		dp[i] = prod(p[i:])
		for j in range(i + 1, k):
			ndp = prod(p[i:j]) + q[j - 1] + dp[j]
			if ndp > dp[i]:
				(dp[i], go[i]) = (ndp, j)
	offset = [0] + list(accumulate(map(len, b)))
	res = ['*'] * (len(a) - 1)
	i = go[0]
	while i < k:
		a = offset[2 * i - 1] - 1
		b = offset[2 * i]
		res[a:b] = '+' * (b - a)
		i = go[i]
	return '+' + ''.join(res) + '+'

def solve(a, ops):
	n = len(a)
	if len(ops) == 1:
		return ops * (n - 1)
	if sorted(ops) == list('+-'):
		return '+' * (n - 1)
	if sorted(ops) == list('*-'):
		k = a.index('0') if '0' in a else n
		if k == 0 or k == n:
			return '*' * (n - 1)
		return '*' * (k - 1) + '-' + '*' * (n - k - 1)
	return ''.join(map(solve_positive, a.split('0')))[1:-1]
n = int(input())
a = ''.join(input().split())
ops = input()
b = solve(a, ops) + '\n'
for i in range(n):
	print(a[i], end='')
	print(b[i], end='')


n = int(input())
a = list(map(int, input().split()))
s = input()
usable = []
if '+' in s:
	usable.append(0)
if '*' in s:
	usable.append(1)
if '-' in s:
	usable.append(2)
usable = tuple(usable)
if len(usable) == 1:
	ans = [s] * (n - 1)
	ansPr = []
	for i in range(n - 1):
		ansPr.append(str(a[i]))
		ansPr.append(ans[i])
	ansPr.append(str(a[n - 1]))
	print(''.join(ansPr))
elif usable == (0, 1) or usable == (0, 1, 2):
	ans = ['+'] * (n - 1)
	curIndex = 0
	while curIndex < n:
		curCpy = curIndex
		while curIndex < n and a[curIndex] != 0:
			curIndex += 1
		left = curCpy
		right = curIndex
		while left < right and a[left] == 1:
			left += 1
		while right > left and a[right - 1] == 1:
			right -= 1
		curCur = left
		nonOneProd = []
		oneLength = []
		while curCur < right:
			curProd = 1
			while curCur < right and a[curCur] != 1:
				if curProd < 2 * (right - left):
					curProd *= a[curCur]
				curCur += 1
			nonOneProd.append(curProd)
			if curCur == right:
				break
			curOneLength = 0
			while curCur < right and a[curCur] == 1:
				curOneLength += a[curCur]
				curCur += 1
			oneLength.append(curOneLength)
		curAllProd = 1
		index = 0
		while curAllProd < 2 * (right - left) and index < len(nonOneProd):
			curAllProd *= nonOneProd[index]
			index += 1
		if curAllProd >= 2 * (right - left) or len(nonOneProd) == 1:
			for i in range(left, right - 1):
				ans[i] = '*'
		else:
			maskLen = len(oneLength)
			bestMask = 0
			bestAns = 0
			for i in range(1 << maskLen):
				curAns = 0
				curProd = nonOneProd[0]
				for j in range(maskLen):
					if i & 1 << j:
						curProd *= nonOneProd[j + 1]
					else:
						curAns += curProd
						curAns += oneLength[j]
						curProd = nonOneProd[j + 1]
				curAns += curProd
				if curAns > bestAns:
					bestAns = curAns
					bestMask = i
			curOneCount = 0
			for i in range(left, right - 1):
				if a[i] != 1 and a[i + 1] == 1:
					curOneCount += 1
				if a[i] != 1 and a[i + 1] != 1:
					ans[i] = '*'
				elif bestMask & 1 << curOneCount - 1:
					ans[i] = '*'
		while curIndex < n and a[curIndex] == 0:
			curIndex += 1
	ansPr = []
	for i in range(n - 1):
		ansPr.append(str(a[i]))
		ansPr.append(ans[i])
	ansPr.append(str(a[n - 1]))
	print(''.join(ansPr))
elif usable == (1, 2):
	ans = ['-'] * (n - 1)
	firstZero = True
	for i in range(n - 1):
		ans[i] = '*'
		if a[i + 1] == 0 and firstZero:
			ans[i] = '-'
			firstZero = False
	ansPr = []
	for i in range(n - 1):
		ansPr.append(str(a[i]))
		ansPr.append(ans[i])
	ansPr.append(str(a[n - 1]))
	print(''.join(ansPr))
elif usable == (0, 2):
	ans = ['+'] * (n - 1)
	ansPr = []
	for i in range(n - 1):
		ansPr.append(str(a[i]))
		ansPr.append(ans[i])
	ansPr.append(str(a[n - 1]))
	print(''.join(ansPr))