该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

徐老师最近设计了一种新的运算表达式：$ 运算

这种运算是这样的，$a \$ c(b) = (a + c) \times b$，其中 $b$ 称为 运算系数

现在徐老师已经写了一个仅包含 $ 运算的数字表达式，例如 $(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$

但是这个式子显然很复杂，很难理解，计算难度也很高，于是为了降低难度，徐老师会提前把式子转换成 后缀表达式 给出，而每个 $ 运算的系数会单独给出

例如上式将会转换成 4 3 $ 5 6 $ $，运算系数分别为 $2,7,8$

但是由于降低了难度，题目过于简单了，于是徐老师提出他会进行 $m$ 次修改，每次会修改第 $x$ 个数字变成 $y$（每次修改都会保留到接下来的操作）

在每次修改后，请你计算当前表达式的结果

后缀表达式的定义如下：

1. 如果 $A$ 是一个数字，则 $A$ 的后缀表达式是它本身。
2. 如果 $A$ 是一个例如 $A1 \$ A2$ 形式的表达式，则它的后缀表达式是 $A1' A2' \$$，其中 $A1',A2'$ 是 $A1,A2$ 的后缀表达式

输入格式

输入第一行包含一个整数 $n$，$n$ 表示这个表达式中包含 $n$ 个数字

输入第二行包含 $n$ 个数字和 $n-1$ 个 $ 表示原表达式的后缀表达式

输入第三行包含 $n-1$ 个数字，依次表示后缀表达式中每个 $ 运算的运算系数

接下来一行包含一个整数 $m$ 表示操作次数

接下来 $m$ 行，每行包含两个整数 $x,y$ 表示将 后缀表达式 中的第 $x$ 个数字修改为 $y$

输出格式

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

数据范围

对于所有数据保证：$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