。

题号：NC287349
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 对于给定的由 $n$ 个整数构成的序列 $\{a_1,a_2,\dots,a_n\}$ 和 $\{b_1,b_2,\dots,b_n\}$ ， $b$ 序列初始全为 $0$ 。你需要进行 $m$ 次操作，每次操作有以下两种类型：
${\hspace{20pt}}_\texttt{1.}\,$ 对于所有 $i \left(l\le i\le r\right)$ ， $a_i \gets a_i+x$ ；
${\hspace{20pt}}_\texttt{2.}\,$ 对于所有 $i \left(l\le i\le r\right)$ ， $a_i \gets a_i\times x$ 。

$\hspace{15pt}$ 每次操作完成后，对于 $i(1\le i\le n)$ ，让 $b_i \gets b_i+a_i^1+a_i^2+a_i^3+a_i^4+a_i^5$ 。求解最终的 $b$ 数组中的每一个元素对 $998\,244\,353$ 取模后的结果。

输入描述:

第一行输入两个整数  代表序列中的元素数量、操作次数。 
第二行输入  个整数  代表序列中的元素。

此后  行，每行先输入一个整数  代表操作类型，随后输入三个整数  代表一次操作，操作编号同题干。

输出描述:

在一行上连续的输出  个整数，代表最终的  数组中的每一个元素对  取模后的结果。

示例1

输入

复制

5 1
1 1 1 1 1
1 1 2 1

输出

复制

62 62 5 5 5

示例2

输入

复制

10 10
8 7 5 1 1 1 2 9 3 8
2 3 7 8
2 6 7 10
1 8 9 8
2 7 9 9
1 9 10 3
2 10 10 1
1 4 10 4
1 7 9 8
2 10 10 3
1 2 9 7

输出

复制

374480 755657 181317174 3652703 3652703 660055060 987386120 996360882 612833897 379575222