Garage

Slavko has been studying sequences of natural numbers. He calls a sequence interesting if the greatest common divisor of all its elements is greater than 1.

Yesterday he found a sequence of $N$ natural numbers in his garage. He was bored, so he decided to keep himself busy with simple queries. Each query is one of two types.

1. Change the value at position $X$ of the sequence to $V$.
2. Count the interesting contiguous subarrays contained in the interval $[L, R]$ of the sequence.

The first line contains the number of elements $N$ and the number of queries $Q$ ($1 \le N, Q \le 10^5$).

The second line contains $N$ natural numbers $A_i$, the initial sequence ($1 \le A_i \le 10^9$).

Each of the next $Q$ lines contains one query in the following form.

• The first number on the line is 1 or 2 and gives the type of the query.
• For a query of type 1, two numbers $X$ and $V$ follow ($1 \le X \le N$, $1 \le V \le 10^9$).
• For a query of type 2, the left and right boundaries $L$ and $R$ follow ($1 \le L \le R \le N$).

For each query of type 2, print the number of interesting contiguous subarrays on its own line.

In the first example, the interval from position 2 to position 5 is (4, 3, 9, 1). The interesting contiguous subarrays inside it, marked with square brackets, are [4] 3 9 1, 4 [3] 9 1, 4 3 [9] 1, 4 [3 9] 1, so there are four of them.