题目描述

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

昨天，他在车库里找到了一个由 N 个自然数组成的序列。由于他感到非常无聊，他决定通过提出简单的查询来打发时间。每个查询可以是以下两种类型之一：

1. 将序列中位置 X 的值更改为 V。

2. 确定序列中区间 [L, R] 内包含的有趣连续子数组的数量。

输入格式

输入的第一行包含数字 N 和 Q (1 ≤ N, Q ≤ $10^5$)，分别表示序列中的元素数量和查询的数量。

接下来的行包含 N 个自然数 $A_i$ (1 ≤ $A_i$ ≤ $10^9$)，表示初始序列中的数字。

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

• 行中的第一个数字可以是 1 或 2，表示查询的类型。
• 如果查询是类型 1，后面跟着两个数字 X (1 ≤ X ≤ N) 和 V (1 ≤ V ≤ $10^9$)。
• 如果查询是类型 2，后面跟着两个数字 L 和 R (1 ≤ L ≤ R ≤ N)，表示左边界和右边界。

输出格式

对于每个类型 2 的查询，输出任务中有趣的连续子数组的数量。

输入输出样例 #1

输入 #1

5 1
8 4 3 9 1
2 2 5

输出 #1

4

输入输出样例 #2

输入 #2

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

输出 #2

6
1

输入输出样例 #3

输入 #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。