Migrated from Lutece 2743 啊哈哈哈，这收集糖果多是一件美事啊

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

身为成电最会收集糖果的猫，菜猫他拥有 $n$ 个排成一列的很大的罐子，里面装满了美味的糖果，对于第 $i$ 个罐子里面初始有 $a_i$ 颗糖。

虽然已经有了很多的糖，菜猫还是希望能有更多糖。他每天晚上睡觉前都会视天气 $opt$ 往某些罐子里面加糖。

天晴的时候（$opt=1$），他会往第 $L$ 个罐子到第 $R$ 个罐子里不停放糖果，直到每个罐子里面的糖果数量是原先的 $k$ 倍。 阴天的时候（$opt=2$），他会往第 $L$ 个罐子到第 $R$ 个的每个罐子里都放入 $k$ 个糖果。 下雨的时候（$opt=3$），他会数一数第 $L$ 个罐子到第 $R$ 个罐子里糖果的数量来高兴一下。

收集糖果多是一件美差啊！菜猫决定把这件美差和身为朋友的你分享 $m$ 天 ！

Input

第一行是两个整数 $n$ 和 $m$，表示有 $n$ 个罐子，和你分享 $m$ 天糖果收集。 第二行是 $n$ 个整数，第 $i$ 个整数 $a_i$ 表示第 $i$ 个罐子里的糖果数量。 接下来是 $m$ 行，每行包含若干个整数，第一个整数 $opt$ 代表当天的天气情况。 当 $opt$ 值为 $1$ 时，该行接下来还有 $3$ 个整数 $L$, $R$, $k$。 当 $opt$ 值为 $2$ 时，该行接下来还有 $3$ 个整数 $L$, $R$, $k$。 当 $opt$ 值为 $3$ 时，该行接下来只会有 $2$ 个整数 $L$, $R$。

Output

对于每个下雨天，你需要告诉菜猫第 $L$ 到 $R$ 这些罐子里面一共有多少糖果了。糖果数目或许会很大，所以你只要告诉菜猫糖果数目对 $998244353$ 取模后的值。

Samples

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

17
40

Note

$1\le n,m,k \leq 10^5,0\le a_i \leq 32767$

Resources

2022 UESTC ICPC Training for Data Structures