#1053. nocriz与队列计算机

nocriz是一位来到了西安的同学。

他在参观兵马俑时，了解到在遥远的秦朝，为了进行复杂的计算，秦始皇发明了队列计算机。兵马俑就是秦始皇为了在地下进一步发展科技而制作的队列计算机模型。

在此题中，队列计算机被简化成长度为$n$的一个士兵的队列，其中计算元件（士兵）有两种，其中$a_i$为这个士兵的特征值

• 加法士兵负责从左边读入一个数字$x$，并将$(x+a_i) \mod 998244353$告诉下一个士兵
• 乘法士兵负责从左边读入一个数字$x$，并将$(x \times a_i) \mod 998244353$告诉下一个士兵

每一次，秦始皇有两个操作：

• 更换一个士兵，给出新士兵的类型和特征值
• 告诉第$l$个士兵一个数$x$，求第$r$个士兵说出的数字

秦始皇了解到nocriz学习了数据结构，要考考nocriz同学，但是他把锅丢给了你。

一行两个整数$n,q$; 接下来$n$行，每行两个整数$typ_i,a_i$

• $typ_i = 0$士兵为乘法士兵
• $typ_i = 1$士兵为加法士兵

接下来$q$行，每行开始一个整数$op$

• $op = 0$接下来输入$p,typ_p,a_p$，代表修改操作
• $op = 1$接下来输入$l,r,x$，代表询问操作

对于每次询问操作，输出一行一个数代表答案。

输入样例

5 5
0 8
1 5
1 7
1 1
0 8
1 5 5 3
0 2 0 6
0 1 1 2
0 5 1 6
1 1 5 6

输出样例

24
62

$n,q \le 5 \cdot 10^5$

所有出现过的数字在$[1,998244352]$区间中