时空限制

6S/512M

题目描述

在 jiangly 的眼中，算法竞赛分为 $n$ 个专题，每一个专题 jiangly 都有一些题目，一开始第 $i$ 个专题有 $a_i$ 个题目。

现在 jiangly 要举办若干次集训，每一次集训需要 jiangly 从某一个专题中挑选出 $k$ 个题。

由于学生的实力有限，所以每一次集训都会指定一个专题区间 $[l_i, r_i]$，jiangly 只能选择第 $l_i$ 个到第 $r_i$ 个专题之间的题目。

但是 jiangly 在集训中间，也会时不时增加某些专题的题目数量。jiangly 想知道每一次集训的方案数。

jiangly 作为算法大师，很快就解出了这个问题。但是因为你是他的学生，他想考考你。

由于答案可能很大，所以需要你输出答案对 $998244353$ 取模后的结果。

格式

输入格式

第一行包含两个整数，分别是 $n$ 和 $q$，表示专题的数量和操作的个数。

第二行包含 $n$ 个整数 $a_1 ,a_2 \cdots a_n$，表示 jiangly 一开始每一个专题的题目数量。

接下来 $q$ 行表示 $q$ 次操作，操作有以下两种形式：

• 1 l r y：表示 jiangly 的从第 $l$ 个专题到第 $r$ 个专题的数量各增加 $y$。
• 2 l r k：表示 jiangly 进行一次用 $l$ 到 $r$ 专题需要找 $k$ 个题的集训，需要你回答方案数。

输出格式

对于每一个 $2$ 号操作，输出一行，表示方案数对 $998244353$ 取模后的结果。

样例

样例输入 #1

3 5
2 1 2
2 1 2 3
1 2 2 2
2 1 3 1
1 1 1 3
2 1 3 3

样例输出 #1

0
7
11

样例输入 #2

3 2
2 1 2
1 1 2 3
2 1 2 3

样例输出 #2

14

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n, q\le$	$k\le$	其他限制
$1$	$15$	$2000$	$8$	无
$2$	$30$	$1.5\times 10^5$		$1$ 号操作满足 $l = r$
$3$	$30$	$1.5\times 10^5$	$1$	无
$4$	$25$	$1.5\times 10^5$	$8$

对于 $100\%$ 的数据，满足 $1 \le n, q \le 1.5 \times 10^5$，$1 \le k \le 8$，操作 $1$ 中 $1 \le y \le 10^9$，$1 \leq a_i \leq 10^9$，$1 \le l \le r \le n$。