2419 - 双区间
Description

给定两个长度为 n 的序列 A_N, B_N,现在需要维护 m 次以下三种操作:


- `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 \bmod 998244353


Input

第一行2个数字n,m

接下来两个数组a_i,b_i;

接下来m行询问,同上题目介绍

Output

针对3的循环,进行输出!

Examples

Input

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

Output

16
25
84

Input

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

Output

716070898
151723988
Hint

- 1\leq\ n,m\leq\ 2\times\ 10^5

- 0\leq\ A_i,B_i\leq\ 10^9

- 1\leq\ l\leq\ r\leq\ N

- 1\leq\ x\leq\ 10^9


题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 31
通过次数 8