Interesting Subarrays

Slavko is studying sequences of natural numbers and defines a sequence as interesting if the greatest common divisor (\(GCD\)) of all its elements is greater than 1. Recently, he discovered a sequence of \(N\) natural numbers and began to ask himself queries on the sequence. There are two types of queries:

1. Update Query: Change the value at position \(X\) in the sequence to \(V\).
2. Range Query: Determine the number of interesting contiguous subarrays within the interval \([L, R]\) of the sequence. A contiguous subarray of the sequence is interesting if its \(GCD\) is greater than 1.

Note: If a subarray consists of only one element and that element is greater than 1, it is considered interesting.

The task is to process \(Q\) queries and for each query of type 2, output the number of interesting contiguous subarrays within the given range.

The formula for an interesting subarray can be summarized as follows:

[ \text{A subarray } A[i..j] \text{ is interesting if } \gcd(A[i],A[i+1],\dots,A[j]) > 1. ]

inputFormat

The first line contains two integers \(N\) and \(Q\), where \(N\) is the number of elements in the sequence and \(Q\) is the number of queries.

The second line contains \(N\) natural numbers representing the sequence.

Each of the next \(Q\) lines contains a query, which can be one of the following types:

• For an update query: 1 X V, meaning change the value at position \(X\) to \(V\).
• For a range query: 2 L R, meaning count the number of interesting contiguous subarrays in the interval \([L, R]\).

All indices are 1-indexed.

outputFormat

For each query of type 2, output a single line with the number of interesting contiguous subarrays in the specified interval.

sample

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

3
6