Two Sequence Queries

时间限制：3 秒 / 内存限制：1024 MB

Description

给定两个长度为 $N$ 的序列 $A$ 和 $B$，现在需要维护 $Q$ 次以下三种操作：

• 1 l r x：将 $A_l, A_{l+1}, \cdots, A_r$ 全部加 $x$；
• 2 l r x：将 $B_l, B_{l+1}, \cdots, B_r$ 全部加 $x$；
• 3 l r：求 $\sum_{i=l}^r A_i \times B_i \mod 998244353$。

Input

第一行包含两个整数 $N$ 和 $Q$，分别表示数组的长度和操作次数（$1 \leq N, Q \leq 2 \times 10^5$）。

第二行包含 $N$ 个非负整数 $A_1, A_2, \dots, A_N$，表示数组 $A$ 的初始值。

第三行包含 $N$ 个非负整数 $B_1, B_2, \dots, B_N$，表示数组 $B$ 的初始值。

接下来 $Q$ 行，每行包含一个操作，操作的格式为：

• 1 l r x：将 $A_l, A_{l+1}, \cdots, A_r$ 全部加 $x$；
• 2 l r x：将 $B_l, B_{l+1}, \cdots, B_r$ 全部加 $x$；
• 3 l r：查询 $\sum_{i=l}^r A_i \times B_i \mod 998244353$。

每个操作中的 $1 \leq l \leq r \leq N$，且 $0 \leq A_i, B_i, x \leq 10^9$。

Output

对于每一个查询操作 3 l r，输出查询结果。

Example

Sample Input 1

5 6
1 3 5 6 8
3 1 2 1 2
3 1 3
1 2 5 3
3 1 3
1 1 3 1
2 5 5 2
3 1 5

Sample Output 1

16
25
84

Sample Input 2

2 3
1000000000 1000000000
1000000000 1000000000
3 1 1
1 2 2 1000000000
3 1 2

Sample Output 2

716070898
151723988