加乘运算(addmul)

题目描述

小 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}$。

样例一

输入

5 5
4 9 * 1 6 2 * * * 
4 1 3 2
1 9
5 10
4 10
4 4
4 7

输出

198
246
270
234
252

样例解释

第一次修改后的表达式为 $(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$ 。

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