E. LCM Queries
time limit per test
4 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

To test Tama's intelligence, Megumi prepares an array $$$a$$$ of length $$$n$$$ and $$$q$$$ queries for her. Each query is either of the following two types:

  1. Set $$$a_i=x$$$.
  2. Find $$$d\left(\text{lcm}(a_l,a_{l+1},\dots,a_r)\right)\bmod{998244353}$$$. In other words, let $$$L=\text{lcm}(a_l,a_{l+1},\dots,a_r)$$$. Tama should count the number of positive divisors of $$$L$$$, and then give this count modulo $$$998244353$$$.

To Megumi's surprise, Tama answers her queries in $$$4$$$ seconds. Given that she earns $$$0$$$ points in the math test, Megumi asks you to help her verify Tama's answers. To present herself as a talented savior, she also wants you to calculate the answers as fast as Tama does.

Input

The first line of each test contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 2 \cdot 10^5$$$).

The second line of each test contains $$$n$$$ integers $$$a_i$$$ ($$$1\le a_i\le 10^5$$$).

The next $$$q$$$ lines of each test describe the queries. Each of the lines is in either of the following two formats:

  • $$$1$$$ $$$i$$$ $$$x$$$. ($$$1\le i\le n$$$, $$$1\le x\le 10^5$$$)
  • $$$2$$$ $$$l$$$ $$$r$$$. ($$$1\le l\le r\le n$$$)

It is guaranteed that there is at least one query of the second type.

Output

For each query of the second type, output an integer — the answer to that query.

Example
Input
4 3
6 9 12 16
2 1 3
1 2 15
2 2 4
Output
9
20
Note

In the first query, the $$$9$$$ divisors of $$$\lcm(6,9,12)=36$$$ are $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$6$$$, $$$9$$$, $$$12$$$, $$$18$$$, and $$$36$$$.

In the second query, the $$$20$$$ divisors of $$$\lcm(15, 12, 16) = 240$$$ are $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$, $$$5$$$, $$$6$$$, $$$8$$$, $$$10$$$, $$$12$$$, $$$15$$$, $$$16$$$, $$$20$$$, $$$24$$$, $$$30$$$, $$$40$$$, $$$48$$$, $$$60$$$, $$$80$$$, $$$120$$$, and $$$240$$$.