题目描述

给定长度为$n$的序列$a_i$，以及$m$个操作。

操作一：1 k x，将$a_k$修改为$x$。 操作二：2 l r，记$A=\prod_{i=l}^{r}a_i$，求$\varphi(A)$。其中，$\varphi(A)$指的是$A$的欧拉函数值。 操作三：3 l r，记$A=\prod_{i=l}^{r}a_i$，求$\sigma(A)$。其中，$\sigma(A)$指的是$A$所有的因数之和。

特别的，善良的小码哥决定，不让$a_i$过大，所以所有的$a_i$与$x$均不大于$100$。

由于答案可能很大，你只需要输出在模$998244353$下的结果即可。

输入格式

第一行输入两个整数$n,m$。 第二行输入$n$个整数$a_i$。 接下来$m$行，每行输入一个操作，格式如题面所示。

输出格式

对于每个询问操作，输出一行一个整数，表示你的答案。

样例输入 #1

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

样例输出 #1

8
60
16
124

说明/提示

有$1\leq n,m\leq 10^5,1\leq a_i,x\leq 100$。