题目描述

给定长度为 $n$ 的序列 $a_i$，你需要处理 $m$ 次操作：

• 给出 $x, y$，将 $a_x$ 修改为 $y$；
• 给出 $v$，求出存在多少二元组 $(l, r)$ 满足 $1 \leq l \leq r \leq n$ 且 $v = \operatorname{lcm}(a_l, a_{l+1}, \cdots, a_r)$。

输入格式

第一行三个正整数 $T, n, m$，其中 $T$ 代表测试点编号。特别地，对于所有样例，$T = 0$。

第二行 $n$ 个正整数 $a_1, a_2, \cdots, a_n$ 表示序列 $a_i$。

接下来 $m$ 行，每行先输入一个整数 $op$。

如果 $op = 1$，再输入两个整数 $x, y$，代表一次修改。

如果 $op = 2$，再输入一个整数 $v$，代表一次查询。

输出格式

对于每个查询输出一行，包含一个整数，为合法区间数量。

0 12 9
1 1 4 5 1 4 1 9 1 9 8 10
2 20
1 11 4
2 20
1 5 14
2 20
1 9 19
2 9
1 8 10
2 20

14
15
4
3
5

样例 2

见选手目录下的 lcm/lcm2.in 和 lcm/lcm2.ans。

该样例数据范围满足测试点 $17 \sim 21$。

样例 3

见选手目录下的 lcm/lcm3.in 和 lcm/lcm3.ans。

该样例数据范围满足测试点 $17 \sim 21$。

数据范围

本题共 $25$ 个测试点，全部测试点满足 $2 \leq n, m \leq 10^5$，$op \in \{1, 2\}$，$1 \leq a_i, v, y\leq 10^9$，$1 \leq x \leq n$。

对于所有编号为偶数的测试点，保证 $a_i, y \leq 20$。

特殊限制 A：$op = 2$。

特殊限制 B：$a_i, y$ 在所有可能的值中均匀随机生成。