最近，Slavko 一直在研究自然数序列。如果一个序列中所有元素的最大公约数大于 $1$，他就认为这个序列是有趣的。

昨天，他在车库里发现了一个由 $N$ 个自然数组成的序列。因为实在太无聊了，他决定通过提出一些简单的询问来消磨时间。每次询问可以是以下两种类型之一：

1. 将序列中位置 $X$ 处的值修改为 $V$。
2. 确定序列中包含在区间 $[L, R]$ 内的有趣的连续子数组的数量。

输入格式

输入的第一行包含两个整数 $N$ 和 $Q$（$1 \le N, Q \le 10^5$），分别表示序列中的元素个数和询问次数。

下一行包含 $N$ 个自然数 $A_i$（$1 \le A_i \le 10^9$），表示初始序列中的数。

接下来的 $Q$ 行，每行包含一个如下格式的询问：

• 每行的第一个数可以是 $1$ 或 $2$，表示询问的类型。
• 如果询问类型为 $1$，则后面跟着两个数 $X$（$1 \le X \le N$）和 $V$（$1 \le V \le 10^9$）。
• 如果询问类型为 $2$，则后面跟着两个数 $L$ 和 $R$（$1 \le L \le R \le N$），表示区间的左右边界。

输出格式

对于每个类型为 $2$ 的询问，输出满足条件的有趣的连续子数组的数量。

样例

输入样例 1

5 1
8 4 3 9 1
2 2 5

输出样例 1

4

输入样例 2

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

输出样例 2

6
1

输入样例 3

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

输出样例 3

10
5

说明

第一个样例解释：

从第 $2$ 个位置到第 $5$ 个位置的区间由数字 $(4, 3, 9, 1)$ 组成。其中，以下是符合要求的有趣的连续子数组（用方括号表示）：

• [4] 3 9 1
• 4 [3] 9 1
• 4 3 [9] 1
• 4 [3 9] 1