题目描述

小泽设计了一把使用混合进制的密码锁，并把一组长度为 $m$ 的密钥 $a_1,a_2,\ldots,a_m$ 交给小婷。密码锁中的数字都使用这组密钥表示。

一个混合进制数写作

其中最右侧的 $k_1$ 是最低位，第 $i$ 个低位的进制为 $a_i$。它所表示的十进制数为

例如密钥为 $7,6,5$ 时，混合进制数 $(2,3,1)$ 表示

为了打开密码锁，小泽给小婷留下一道由混合进制数、加号 +、乘号 * 和括号组成的算式。小婷需要按照通常的运算优先级计算算式，并把结果重新写成混合进制数。

请你帮助小婷得到最终密码。

输入格式

第一行输入一个整数 $m$，表示密钥长度。

第二行输入 $m$ 个整数 $a_1,a_2,\ldots,a_m$。

第三行输入一个不含空格的字符串 $S$，表示混合进制算式。

输出格式

输出一个字符串，表示计算结果的混合进制表示。不要输出多余的前导零；当结果为 $0$ 时输出 (0)。

样例

5
10 10 7 10 8
((1,2,3)+(3,2,1))*(2,0)

(1,2,4,8,0)

样例解释

$(1,2,3)+(3,2,1)=(4,4,4)$，再计算

考点说明

本题主要考查表达式解析与进制转换。需要正确处理括号以及乘法、加法的优先级，并完成混合进制数与十进制数之间的双向转换。

输入样例 #2

1
10
(3)+(4)

输出样例 #2

(7)

输入样例 #3

1
20
(2)*(3)+(4)

输出样例 #3

(10)

数据范围

• 对于 $30\%$ 的数据，$S$ 中只包含一次加法；
• 对于另外 $30\%$ 的数据，$m=1$；
• 对于 $100\%$ 的数据，$1\le m\le 10$，$1\le a_i\le 20$，$|S|\le 100$；算式只包含加法、乘法和括号，并保证计算结果可以用不超过 $m$ 位混合进制数表示。