A sequence is interesting if the greatest common divisor of all the elements from the sequence is greater than 1. Each query can be of two types: 1. Change the value at position X in the sequence to V. 2. Determine the number of interesting contiguous subarrays contained in the interval [L, R] sequence. The first line of input contains the numbers N and Q (1 <= N, Q <= 100000), representing the number of elements in the sequence and number of queries, respectively. The following line contains N natural numbers, A[i] (1 <= A[i] <= 1000000000) that represent the numbers in the initial sequence. Each of the following Q queries contains a query in the following form: 1. The first number in line can be 1 or 2 denoting the type of query. 2. If the query is of type 1, two numbers follow, X (1 <= X <= N) and V (1 <= V <= 1000000000). 3. If the query is of type 2, two numbers follow, L and R (1 <= L, R <= N), that represents the left and right interval boundary.