Нещодавно Славко вивчав послідовності натуральних чисел. Він вважає послідовність цікавою, якщо найбільший спільний дільник усіх елементів послідовності більший за 1.

Вчора він знайшов у своєму гаражі послідовність із ~N~ натуральних чисел. Оскільки йому було дуже нудно, він вирішив зайняти себе простими запитами. Кожен запит може бути одного з двох типів:

1. Змінити значення на позиції ~X~ в послідовності на ~V~.

2. Визначити кількість цікавих неперервних підмасивів, що містяться в інтервалі ~[L, R]~ послідовності.

Input

Перший рядок вхідних даних містить числа ~N~ та ~Q(1 \leq N, Q \leq 10^{5})~, що представляють кількість елементів у послідовності та кількість запитів відповідно. Наступний рядок містить ~N~ натуральних чисел ~A_{i}(1 \leq A_{i} \leq 10^{9})~, які представляють числа в початковій послідовності.

Кожен з наступних ~Q~ рядків містить запит наступної форми:

* Перше число в рядку може бути 1 або 2 і представляє тип запиту.

* Якщо запит типу 1, слідують два числа, ~X(1 \leq X \leq N)~ та ~V(1 \leq V \leq 10^{9})~ із задачі.

* Якщо запит типу 2, слідують два числа, ~L~ та ~R(1 \leq L \leq R \leq N)~, що представляють ліву та праву межу інтервалу.

Output

Для кожного запиту типу 2 виведіть кількість цікавих неперервних підмасивів із задачі.

Sample Input 1

5 1
8 4 3 9 1
2 2 5

Sample Output 1

4

Sample Input 2

5 3
2 3 6 4 1
2 1 4
1 3 1
2 3 5

Sample Output 2

6
1

Sample Input 3

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

Sample Output 3

10
5