题目描述

小 A 有两个长度均为 $n$ 的整数序列 $a_{1},a_{2},\ldots,a_{n}$ 和 $b_{1},b_{2},\ldots,b_{n}$。

定义这两个序列的能量值为

$$E=\sum_{i=1}^{n-1}\left(\sum_{j=1}^{i}b_{j}\right) (a_{i}-a_{i+1}).$$

接下来将发生 $q$ 次事件，每次事件属于以下三种类型之一：

1. 给定下标 $x$ 和整数 $v$，将 $a_{x}$ 增加 $v$。

2. 给定下标 $x$ 和整数 $v$，将 $b_{x}$ 增加 $v$。

3. 给定整数 $v$，查询当前 $(E+v)\bmod 998244353$ 的值。

请按照给定顺序处理所有事件，并回答每次查询。

输入格式

第一行包含一个整数 $n$（$1 \le n \le 10^{6}$），表示两个序列的长度。

第二行包含 $n$ 个整数 $a_{1},a_{2},\ldots,a_{n}$（$|a_{i}| \le 10^{9}$），表示序列 $a$ 的初始值。

第三行包含 $n$ 个整数 $b_{1},b_{2},\ldots,b_{n}$（$|b_{i}| \le 10^{9}$），表示序列 $b$ 的初始值。

第四行包含一个整数 $q$（$1 \le q \le 10^{6}$），表示事件的数量。

接下来 $q$ 行，每行描述一个事件，格式为以下三种之一：

• 1 x v：将 $a_{x}$ 增加 $v$。

• 2 x v：将 $b_{x}$ 增加 $v$。

• 3 v：查询当前 $(E+v)\bmod 998244353$ 的值。

对于所有修改事件，保证 $1 \le x \le n$。对于所有事件，保证 $|v| \le 10^{9}$。

输出格式

对于每个类型为 $3$ 的事件，输出一行，包含一个整数，表示当前 $(E+v)\bmod 998244353$ 的值。

答案应表示为非负余数，即输出的整数必须位于 $[0,998244352]$ 内。

3
3 1 2
2 -1 5
8
3 0
1 2 4
3 1
2 1 -3
3 0
2 3 100
1 3 -1
3 -2

3
0
998244349
998244345

样例解释

• 当 $n=1$ 时，能量值的求和范围为空，规定 $E=0$。

• 修改操作会永久生效，并影响之后的事件。修改后的元素值不要求仍满足初始值的范围限制。

• 查询事件中的 $v$ 仅用于计算本次输出，不会修改序列 $a$ 或序列 $b$。