数学表达式

• 时间限制：1 秒
• 内存限制：256 MiB

题目描述

给定 $n$ 个数字 $a_1,a_2,\ldots,a_n$，你需要在每对相邻数字之间插入一个允许使用的运算符，使最终表达式的值最大。

允许的运算符由字符串 $s$ 给出。乘法的优先级高于加法与减法；加法和减法优先级相同，并从左到右计算。

输入格式

第一行一个整数 $n$（$1\le n\le10^5$）。

第二行 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0\le a_i\le9$）。

第三行一个字符串 $s$（$1\le |s|\le3$）。字符串只包含 -、+、*，且字符互不相同。

输出格式

输出由原来的 $n$ 个数字和 $n-1$ 个允许运算符组成的表达式，使其值最大。若有多个最优答案，输出任意一个。

样例输入 1

3
2 2 0
+-*

样例输出 1

2*2-0

样例输入 2

4
2 1 1 2
+*

样例输出 2

2+1+1+2

数据范围

$1\le n\le10^5$，$0\le a_i\le9$，$s$ 是 -、+、* 的非空无重复子集。