← 返回题目列表

Codeforces · 1461/F

F. 数学表达式

中文机器翻译题面 查看原题

芭芭拉数学课迟到了,作为惩罚,老师让她在一张纸上解决任务。芭芭拉看着那张纸,只看到了$$$n$$$数字$$$a_1,a_2,\ldots,a_n$$$,没有任何数学符号。老师向芭芭拉解释说,她必须将可用符号放置在数字之间,以使所得表达式的值尽可能大。为了找出哪些符号可用,老师给了芭芭拉一个包含该信息的字符串 $$$s$$$。

很容易注意到,Barbara 总共必须在数字之间放置 $$$n - 1$$$ 符号。表达式必须以数字开头,并且必须允许所有符号(即包含在 $$$s$$$ 中)。请注意,乘法优先于加法或减法,加法和减法具有相同的优先级,并且从左到右执行。 Help Barbara and create the required expression!

输入

输入的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$) — 纸上的数字数量。

输入的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 9$$$),其中 $$$a_i$$$ 是 $$$a$$$ 的第 $$$i$$$ 个元素。

输入的第三行包含字符串 $$$s$$$ ($$$1 \le |s| \le 3$$$) — 表达式中允许使用的符号。保证字符串只能由符号“-”、“+”和“*”组成。还保证字符串中的所有符号都是不同的。

输出

打印由 $$$n - 1$$$ 符号分隔的 $$$n$$$ 数字 - 具有最大结果的数学表达式。如果有多个同样有效的结果 - 输出其中任何一个。

示例

输入 #1

3
2 2 0
+-*

输出 #1

2*2-0

输入 #2

4
2 1 1 2
+*

输出 #2

2+1+1+2

注意

以下答案也适合第一个示例:“2+2+0”、“2+2-0”、“2*2+0”。