小 C 最近脑洞打开，定义了一个新的运算：加乘运算！

他定义 $a *^bc=(a+c)\times b$ 。

现在小 C 写了一个只包含**数字**和**加乘运算**的表达式。之后他有 $m$ 次修改表达式的操作，每次操作他会修改某一个**数字**的值，并且想知道修改后的表达式的值为多少。

**注意每次修改会保留下来。**

为了化简对表达式的处理，我们有如下约定：

表达式将采用**后缀表达式**的方式输入。

后缀表达式的定义如下：

1. 如果 $E$ 是一个数字，则 $E$ 的后缀表达式是它本身。

2. 如果 $E$ 是 $E_1\ *\ E_2$ 形式的表达式，其中 $*$ 是加乘运算，则 $E$ 的后缀式为 $E'_1\ E'_2\ *$，其中 $E'_1$ 、$E'_2$ 分别为 $E_1$、$E_2$ 的后缀式。

3. $*^b$ 的系数 $b$ 会在表达式后面给出。

一共一行两个整数 $n,m$ ，分别表示表达式中变量的数量和

第二行为小 C 的加乘运算的后缀表达式 。

第三行一共 $n-1$ 个数，$b_1,b_2,...,b_{n-1}$ ，分别表示第 $i$ 个加乘运算的系数。

接下来一共 $m$ 行，每行两个整数 $x,y$，表示将表达式的第 $x$ 个数字改成 $y$ 。

一行 $m$ 行，每行一个整数，表示该询问下表达式的值。**保证答案不超过 $10^{18}$。**

样例解释

第一次修改后的表达式为 $(9*^4 9) *^2(1 *^3 (6 *^1 2))$，即$((9+9)\times 4+(1+(6+2)\times 1)\times 3)\times 2=198$ 。

数据范围

对于所有数据 $n,m\le 10^5$，题中出现的数字均小于 $10^9$ 。

| 测试点      | 数据范围                | 特殊性质   |

| ----------- | ----------------------- | ---------- |

| $1\sim 4$   | $b_1=b_2=...=b_{n-1}=1$ | 无         |

| $5\sim 10$  | $n,m\le 10^3$           | 无         |

| $11\sim 14$ | 无限制                  | $\text{A}$ |

| $15\sim 20$ | 无限制                  | 无         |

$\text{A}:$ 小 C 给的表达式为为随机生成。