小 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 给的表达式为为随机生成。