时空限制

6S/512M

题目描述

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

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

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

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

也就是说，对于一次询问 2 l r k，你需要输出：

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

输入格式

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

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

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

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

输出格式

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

数据规模

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

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

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

0
7
11

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

14