Mr. waht is a powerful mage.

To enhance his magical power, Mr. waht has set up a magic array. This array consists of $n$ magic stones arranged in a row from left to right. The $i$-th magic stone from the left is numbered $i$ and has an initial magic value of $a_i$.

Mr. waht can extract magic from some of these stones. Due to the special nature of the array, when extracting magic, Mr. waht must first choose a magic stone. Once the $x$-th magic stone is chosen, he must then choose the $(x + \gcd(x, a_x))$-th magic stone (where $\gcd(x, y)$ denotes the greatest common divisor of $x$ and $y$), and continue this process until $x + \gcd(x, a_x) > n$, at which point the extraction process stops immediately. The total magic power obtained by Mr. waht is the sum of the magic values of all the stones selected during this process.

Mr. waht performs $q$ operations on this array. Specifically, there are two types of operations:

• Mr. waht chooses two numbers $l, r$ ($1 \leq l \leq r \leq n$) and casts a spell on all magic stones in the range $[l, r]$, multiplying their magic values by $c$. Specifically, for all $i$ such that $l \leq i \leq r$, the value of $a_i$ is updated to $c \cdot a_i$.
• Mr. waht chooses the $x$-th magic stone and extracts magic according to the rules described above.

Whenever Mr. waht chooses a magic stone to extract magic, you need to help him calculate the total magic power he obtains. Since the answer can be very large, you only need to output the result modulo $998244353$.

Input

The input is read from standard input.

The first line contains two positive integers $n, q$ ($1 \leq n, q \leq 2.5 \times 10^5$), representing the number of magic stones in the array and the number of operations.

The next line contains $n$ positive integers, where the $i$-th integer is $a_i$ ($1 \leq a_i < 998244353$), representing the initial magic value of the magic stones.

The next $q$ lines each start with an integer $op$, representing the type of operation:

If $op = 1$, three positive integers $l, r, c$ ($1 \leq l \leq r \leq n, 2 \leq c \leq 2.5 \times 10^5$) follow, representing that the magic values of all stones in the range $[l, r]$ are multiplied by $c$.

If $op = 2$, one positive integer $x$ ($1 \leq x \leq n$) follows, representing the starting position for magic extraction.

Output

The output is written to standard output.

For each operation of type $2$, output a single positive integer on a new line, representing the calculated answer modulo $998244353$.

Examples

Input 1

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

Output 1

7
22
36
42

Note 1

In the first operation, the magic values of stones in the range $[2, 6]$ are multiplied by $2$, changing the sequence to $1, 2, 2, 2, 2, 2, 1$.

In the second operation, Mr. waht chooses the $1$-st magic stone. The stones with indices $1, 2, 4, 6$ are selected in sequence, and the sum of their magic values is $7$.

In the third operation, the magic values of stones in the range $[3, 5]$ are multiplied by $5$, changing the sequence to $1, 2, 10, 10, 10, 2, 1$.

In the fourth operation, Mr. waht chooses the $3$-rd magic stone. The stones with indices $3, 4, 6$ are selected in sequence, and the sum of their magic values is $22$.

In the fifth operation, the magic values of stones in the range $[2, 7]$ are multiplied by $3$, changing the sequence to $1, 6, 30, 30, 30, 6, 3$.

In the sixth operation, Mr. waht chooses the $3$-rd magic stone. The stones with indices $3, 6$ are selected in sequence, and the sum of their magic values is $36$.

In the seventh operation, Mr. waht chooses the $2$-nd magic stone. The stones with indices $2, 4, 6$ are selected in sequence, and the sum of their magic values is $42$.