表达式

文件读写

• 输入文件 operation.in
• 输出文件 operation.out

限制

• 1000ms
• 512MB

题目描述

小 Y 最近设计了一种新的运算表达式：$ 运算 这种运算是这样的，a c (b) = (a + c) \times b，其中 b$ 称为 运算系数 现在小 Y 已经写了一个仅包含 $ 运算的数字表达式，例如 (4 3 (2)) (5 6 (7))(8)$ 这个式子的运算过程即为

1. 先计算 (4 3 (2)) = (4+3) * 2 = 14，式子变为 14 (5 6 (7))(8)$
2. 再计算 (5 6 (7)) = (5+6) * 7 = 77，式子变为 14 77 (8)
3. 最后计算 14 77 (8) = (14+77) * 8=728$ 但是这个式子显然很复杂，很难理解，计算难度也很高，于是为了降低难度，小 Y 会提前把式子转换成 后缀表达式 给出，而每个 $运算的系数会单独给出 例如上式将会转换成4 3 5 6 $，运算系数分别为 2,7,8(但是由于降低了难度，题目过于简单了，于是小 Y 提出他会进行)m(次修改，每次会修改第)x(个数字变成)y（每次修改都会保留到接下来的操作） 在每次修改后，请你计算当前表达式的结果 后缀表达式的定义如下：
4. 如果 A 是一个数字，则 A 的后缀表达式是它本身。
5. 如果 A 是一个例如 A1 A2(形式的表达式，则它的后缀表达式是)A1' A2' $，其中 A1',A2'(是)A1,A2$ 的后缀表达式

数据范围

表格

对于所有数据保证：(1 \leq n,m \le 10^5)，且表达式中的所有数字、运算系数及修改操作中的 y 均为不超过 (10^9) 的正整数，保证中间过程及最终答案在 64 位有符号整数范围内。

样例输入 1

4
4 3  5 6  $
2 7 8
5
1 4
1 2
1 3
3 6
4 7

样例输出 1

728
696
712
768
824

样例输入 2

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

样例输出 2

198
246
270
234
252

输入格式

输入第一行包含一个整数 n，n 表示这个表达式中包含 n 个数字 输入第二行包含 n 个数字和 (n-1) 个 $ 表示原表达式的后缀表达式 输入第三行包含 (n-1) 个数字，依次表示后缀表达式中每个 $ 运算的运算系数 接下来一行包含一个整数 m 表示操作次数 接下来 m 行，每行包含两个整数 (x,y) 表示将 后缀表达式 中的第 x 个数字修改为 y

输出格式

输出 m 行，每行包含一个整数，表示这次修改后表达式的结果

国庆仿真模拟3