차고

슬라브코는 요즘 자연수 수열을 공부한다. 수열의 모든 원소의 최대공약수가 1보다 크면, 슬라브코는 그 수열을 흥미로운 수열이라고 부른다.

어제 슬라브코는 차고에서 자연수 $N$개로 이루어진 수열을 찾았다. 너무 심심했던 슬라브코는 간단한 질의를 던지며 시간을 보내기로 했다. 질의는 다음 두 종류 중 하나다.

1. 수열의 $X$번째 값을 $V$로 바꾼다.
2. 수열의 구간 $[L, R]$ 안에 들어 있는 흥미로운 연속 부분수열이 몇 개인지 구한다.

첫째 줄에 수열의 원소 개수 $N$과 질의 개수 $Q$가 주어진다 ($1 \le N, Q \le 10^5$).

둘째 줄에 처음 수열을 이루는 자연수 $A_i$가 $N$개 주어진다 ($1 \le A_i \le 10^9$).

다음 $Q$개의 줄에 질의가 한 줄에 하나씩 다음 형식으로 주어진다.

• 줄의 첫 수는 1 또는 2이고, 질의의 종류를 나타낸다.
• 종류가 1이면 두 수 $X$와 $V$가 이어서 주어진다 ($1 \le X \le N$, $1 \le V \le 10^9$).
• 종류가 2이면 구간의 왼쪽 끝 $L$과 오른쪽 끝 $R$이 이어서 주어진다 ($1 \le L \le R \le N$).

종류가 2인 질의마다 흥미로운 연속 부분수열의 개수를 한 줄에 하나씩 출력한다.

첫 번째 예제에서 2번째 위치부터 5번째 위치까지의 구간은 (4, 3, 9, 1)이다. 이 구간 안의 흥미로운 연속 부분수열을 대괄호로 표시하면 [4] 3 9 1, 4 [3] 9 1, 4 3 [9] 1, 4 [3 9] 1 네 개다.