C.加乘运算

题目描述

小C在中秋节期间发明了一种新的月饼制作配方计算方式，他称之为“加乘运算”！

他定义 $a *^bc=(a+c)\times b$ 。 这个运算用于计算月饼制作中某种成分的总用量，其中 $a$ 是原始用量，$b$ 是放大系数，而 $c$ 是额外添加的用量。

现在小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$ 。