双序列区间查询

题目描述

给定长度为 $N$ 的序列 $A=(A_1,A_2,\ldots,A_N)$ 和 $B=(B_1,B_2,\ldots,B_N)$。

还会按顺序处理 $Q$ 个查询。

查询有三种类型：

• 1 l r x：给 $A_l, A_{l+1}, \ldots, A_r$ 中的每个数加上 $x$。
• 2 l r x：给 $B_l, B_{l+1}, \ldots, B_r$ 中的每个数加上 $x$。
• 3 l r：输出 $\displaystyle\sum_{i=l}^r (A_i\times B_i)$ 除以 $998244353$ 的余数。

输入格式

输入按以下格式从标准输入给出。这里，$\mathrm{query}_i$（$1\leq i\leq Q$）表示第 $i$ 个要处理的查询。

$N$ $Q$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_N$
$\mathrm{query}_1$
$\mathrm{query}_2$
$\vdots$
$\mathrm{query}_Q$

各查询按以下三种格式之一给出：

$1$ $l$ $r$ $x$

$2$ $l$ $r$ $x$

$3$ $l$ $r$

输出格式

如果第三种类型的查询有 $K$ 个，则输出 $K$ 行。

第 $i$ 行（$1\leq i\leq K$）输出第 $i$ 个第三种类型查询的答案。

样例

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

16
25
84

初始时 $A=(1,3,5,6,8)$，$B=(3,1,2,1,2)$。查询按以下顺序处理：

第 1 个查询，输出 $(1\times 3)+(3\times 1)+(5\times 2)=16$ 除以 $998244353$ 的余数，即 $16$。

第 2 个查询，给 $A_2,A_3,A_4,A_5$ 加上 $3$。现在 $A=(1,6,8,9,11)$。

第 3 个查询，输出 $(1\times 3)+(6\times 1)+(8\times 2)=25$ 除以 $998244353$ 的余数，即 $25$。

第 4 个查询，给 $A_1,A_2,A_3$ 加上 $1$。现在 $A=(2,7,9,9,11)$。

第 5 个查询，给 $B_5$ 加上 $2$。现在 $B=(3,1,2,1,4)$。

第 6 个查询，输出 $(2\times 3)+(7\times 1)+(9\times 2)+(9\times 1)+(11\times 4)=84$ 除以 $998244353$ 的余数，即 $84$。

因此，第 1、2、3 行应分别输出 $16$、$25$、$84$。

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

716070898
151723988

对于第三种类型的查询，要输出除以 $998244353$ 的余数。

数据范围

• $1 \leq N,Q \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$
• 输入均为整数
• 至少有一个第三种类型的查询