Problem: 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".

Solution (in CPP):

Solution:
//#pragma GCC optimize(4)
#include<bits/stdc++.h>
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define REP(u) for(int i=p[u];i!=-1;i=e[i].nxt)
#define ll long long
#define pb push_back
#define PII pair<int,int>
#define PLL pair<ll,ll>
#define fi first 
#define se second
#define sz(x) (int)(x.size())
#define rd (rand()<<16^rand())
#define gc getchar()//(_p1==_p2&&(_p2=(_p1=_buf)+fread(_buf,1,100000,stdin),_p1==_p2)?EOF:*_p1++)
using namespace std;
char _buf[100000],*_p1=_buf,*_p2=_buf;
inline int gi()
{
	int x=0,f=1;
	char ch=gc;
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=gc;
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+(ch^48);
		ch=gc;
	}
	return (f==1)?x:-x;
}
inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}
const ll maxv=1e8;
const int maxn=1e5+5;
int n,a[maxn];
string s;
bool fmul,fadd,fdel;
ll dp[maxn],pre[maxn];
char b[maxn];
inline ll mul(ll a,ll b)
{
	return min(a*b,maxv);
}
inline void init()
{

}
inline void input()
{
	n=gi();
	FOR(i,1,n)a[i]=gi(),b[i]='+';///b is the sign in front of it
	cin>>s;
}
inline void solve()
{
	if(sz(s)==1)
	{
		printf("%d",a[1]);
		FOR(i,2,n)printf("%c%d",s[0],a[i]);
		printf("\n");
		return ;
	}
	for(auto i:s)
	{
		if(i=='+')fadd=1;
		if(i=='-')fdel=1;
		if(i=='*')fmul=1;
	}
	if(!fmul)
	{
		printf("%d",a[1]);
		FOR(i,2,n)printf("%c%d",'+',a[i]);
		printf("\n");
		return ;
	}
	if(!fadd)
	{
		printf("%d",a[1]);
		FOR(i,2,n)
		{
			if(a[i]==0)printf("-");
			else printf("*");
			printf("%d",a[i]);
		}
		printf("\n");
		return ;
	}
	int pos=1;
	while(pos<=n)
	{
		while(pos<=n&&a[pos]==0)pos++;///meaningless,+
		if(pos==n+1)break;
		int lef=pos;
		while(pos<=n&&a[pos])pos++;
		int rig=pos-1;///the left and right ends of the array
		while(a[lef]==1&&lef<=rig)lef++;///if it is 1 then we move forward(+)
		while(a[rig]==1&&lef<=rig)rig--;
		if(lef>rig)continue;
		ll nowm=1;
		FOR(i,lef,rig)nowm=mul(nowm,a[i]);
		if(nowm==maxv)
		{
			FOR(i,lef+1,rig)b[i]='*';
			continue;
		}
		vector<pair<ll,PLL> >st;///breaks(without 1)
		///only the odd position is not 1
		int j=lef;
		while(j<=rig)
		{
			int l=j;
			ll t=1;
			if(a[l]==1)
			{
				while(a[j]==1&&j<=rig)j++;
				t=j-l;///the sum
			}
			else
			{
				while(j<=rig&&a[j]>1)
				{
					if(j!=l)b[j]='*';
					t=mul(t,a[j]);j++;
				}
			}
			st.pb({t,{l,j-1}});///from l to j-1 and the sum is t;
		}
		int len=sz(st);
		FOR(i,1,len)dp[i]=-1e18;
		FOR(i,1,len)
		{///dp might be go with the pres
			if(dp[i]<dp[i-1]+st[i-1].first)///use +
			{
				dp[i]=dp[i-1]+st[i-1].first;
				pre[i]=i-1;
			}
			///dp means the next will choose +(no forever)
			if(i%2==1)///if it is not 1
			{
				ll t=1;
				FOR(j,i,len)///to the new posiytions
				{
					///if j-i%2!=0 it is not excellent
					if((j-i)%2==0)t*=st[j-1].first;
					if((j-i)%2==0&&dp[i-1]+t>dp[j])///after 1 we will use *s
					{
						dp[j]=dp[i-1]+t;
						pre[j]=i-1;
					}
				}
			} 
		}
		int x=len;
		while(x)
		{
			int l=pre[x]+1,r=x;
			x=pre[x];
			if(l>=r)continue;///useless
			FOR(i,st[l-1].second.first+1,st[r-1].second.second)b[i]='*';
		}
	}
	printf("%d",a[1]);
	FOR(i,2,n)printf("%c%d",b[i],a[i]);
	printf("\n");
}
int main()
{
	init();
	input();
	solve();
	return 0;
}///