Magical Stones and the Magic Circle

Mr. waht is a powerful mage who seeks to enhance his magical prowess by harnessing the energy stored in a line of magical stones. There are n stones arranged from left to right, where the i-th stone initially has a magic value of \(a_i\). Each stone is labeled with its position, from 1 to \(n\).

When Mr. waht collects power, he must follow a specific process. He starts from a chosen stone with index \(x\). Then, if he is at stone \(x\) with current magic value \(a_x\), he computes \(d=\gcd(x, a_x)\) and moves to the stone at index \(x+d\). The process continues until \(x+\gcd(x,a_x)>n\), at which point the collection stops. The total power collected is the sum of the magic values of all stones visited during this process.

In addition, Mr. waht will perform \(q\) operations on these stones. There are two types of operations:

• Update operation: Given three integers \(l, r, c\) with \(1 \le l \le r \le n\), multiply the magic values of all stones in the interval \([l, r]\) by \(c\).
• Query operation: Given an integer \(x\), simulate the process described above starting from the \(x\)-th stone and output the total power collected modulo \(998244353\).

Please note that all formulas are given in \(\LaTeX\) format (e.g., \(\gcd(x,a_x)\)).

inputFormat

The first line contains two integers \(n\) and \(q\) — the number of stones and the number of operations, respectively. The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the initial magic values of the stones.

The following \(q\) lines each describe an operation. Each operation is in one of the following two formats:

• 1 l r c — multiply every stone in the interval \([l, r]\) by \(c\).
• 2 x — simulate the stone collection process starting from stone \(x\) and output the result modulo \(998244353\).

outputFormat

For each query operation (the operations of the second type), output the total power collected modulo \(998244353\) on a new line.

sample

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

7
8