4272. [THUPC 2025 pre] waht 先生的法阵

【输入格式】

waht 先生是一名法力强大的魔法师。

waht 先生为了增强自己的法力，设置了一个法阵。这个法阵中共有 $n$ 块魔法石，它们从左到右依次排成一列；并且从左数第 $i$ 块魔法石的编号为 $i$，其法力值初始为 $a_i$。

waht 先生可以获取一些魔法石的法力。然而由于这个法阵的特殊性质，在获取法力时，waht 先生必须先选择一块魔法石；并且一旦第 $x$ 块魔法石被选，接下来必须再选第 $x+\gcd(x,a_x)$ 块魔法石（这里 $\gcd(x,y)$ 表示 $x,y$ 的最大公约数），直到 $x+\gcd (x,a_x)>n$ 时 waht 先生会立即停止本次法力获取的过程。waht 先生获取的法力将会是过程中所选的所有魔法石的法力值之和。

waht 先生会对这个法阵进行 $q$ 次操作。具体的，有以下两类操作：

• waht 先生选择两个数 $l,r\;(1\leq l\leq r\leq n)$，对区间 $[l,r]$ 中的所有魔法石施加法术，使得它们的法力值全部乘以 $c$。具体的，对于所有满足 $l\leq i\leq r$ 的 $i$，将 $a_i$ 的值修改为 $c\cdot a_i$。
• waht 先生选择第 $x$ 块魔法石，并按照上述的规则获取法力。

每当 waht 先生选择某一块魔法石来获取法力时，你都需要帮他计算出他到底获得了多少法力。由于答案可能很大，你只需要求出答案对 $998244353$ 取模的结果。

【输出格式】

第一行输入两个正整数 $n,q\;(1\leq n,q\leq 2.5\times 10^5)$，表示法阵中魔法石的数量和操作次数。

接下来一行，输入 $n$ 个正整数，其中第 $i$ 个为 $a_i\;(1\leq a_i<998244353)$，表示魔法石初始的法力值。

接下来 $q$ 行，先输入一个 $op$，表示操作种类；

若 $op=1$，则再输入三个正整数 $l,r,c\;(1\leq l\leq r\leq n,2\leq c\leq 2.5\times 10^5)$，表示将区间 $[l,r]$ 中的所有魔法石的法力值乘以 $c$；

若 $op=2$，则再输入一个正整数 $x\;(1\leq x\leq n)$，表示获取法力的开始位置。

【输出格式】

每当进行一次操作 $2$ 时，输出一行一个正整数，表示所要查询的答案对 $998244353$ 取模的值。

【样例输入】

7 7
1 1 1 1 1 1 1
1 2 6 2
2 1
1 3 5 5
2 3
1 2 7 3
2 3
2 2

【样例输出】

7
22
36
42

【样例解释】

第一次操作，将区间 $[2,6]$ 中的魔法石的法力值乘以 $2$，法力值序列变为 $1,2,2,2,2,2,1$；

第二次操作，waht 先生选择第 $1$ 块魔法石，则编号为 $1,2,4,6$ 的魔法石会依次被选中，这些魔法石的法力值之和为 $7$；

第三次操作，将区间 $[3,5]$ 中的魔法石的法力值乘以 $5$，法力值序列变为 $1,2,10,10,10,2,1$；

第四次操作，waht 先生选择第 $3$ 块魔法石，则编号为 $3,4,6$ 的魔法石会依次被选中，这些魔法石的法力值之和为 $22$；

第五次操作，将区间 $[2,7]$ 中的魔法石的法力值乘以 $3$，法力值序列变为 $1,6,30,30,30,6,3$；

第六次操作，waht 先生选择第 $3$ 块魔法石，则编号为 $3,6$ 的魔法石会依次被选中，这些魔法石的法力值之和为 $36$；

第七次操作，waht 先生选择第 $2$ 块魔法石，则编号为 $2,4,6$ 的魔法石会依次被选中，这些魔法石的法力值之和为 $42$。

【来源】

清华大学学生算法协会 GitLink 仓库