题目背景

这很自由，包括有序对

题目描述

若一个正整数不被任何大于 $1$ 的平方数整除，则称其为自由的。例如，$1$、$2$、$3$、$5$、$6$、$7$ 是自由的，而 $4$、$8$、$9$、$12$ 不是。

给定一个长度为 $n$ 的正整数序列 $a_1, a_2, \dots, a_n$，你需要处理 $m$ 次操作。操作有两种类型：

• 修改：给定下标 $i$ 和值 $x$，将 $a_i$ 修改为 $x$。

• 查询：给定区间 $[l, r]$，求满足 $l \le i \le j \le r$ 且 $\gcd(a_i, a_j)$ 是自由的有序对 $(i, j)$ 的个数。

请注意，有序对 $(i, j)$ 包括 $i = j$ 的情况。

输入格式

第一行包含两个整数 $n, m$，表示序列长度和操作次数。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$，表示初始序列。

接下来 $m$ 行，每行描述一个操作：

• 修改操作以字符 U 开头，后接两个整数 $i$ 和 $x$，表示将 $a_i$ 修改为 $x$。

• 查询操作以字符 Q 开头，后接两个整数 $l$ 和 $r$，表示查询区间 $[l, r]$。

输出格式

对于每个查询操作，输出一行一个整数，表示满足条件的有序对个数。

3 3
1 2 4
Q 1 3
U 3 2
Q 1 3

5
6

见 ex_free2.in/ans
这个样例满足 sub3 的约束条件

见 ex_free3.in/ans
这个样例满足 sub4 的约束条件

见 ex_free4.in/ans
这个样例满足 sub8 的约束条件

提示

样例解释

初始序列为 $[1, 2, 4]$。

第一个查询：区间 $[1, 3]$ 内有序对如下：

$(1,1)$：$\gcd(1,1)=1$，无平方因子，满足。

$(1,2)$：$\gcd(1,2)=1$，满足。

$(1,3)$：$\gcd(1,4)=1$，满足。

$(2,2)$：$\gcd(2,2)=2$，无平方因子，满足。

$(2,3)$：$\gcd(2,4)=2$，满足。

$(3,3)$：$\gcd(4,4)=4$，有平方因子 $4$，不满足。

因此满足条件的有序对共有 $5$ 个。

修改后序列为 $[1, 2, 2]$。

第二个查询：区间 $[1, 3]$ 内所有有序对均满足条件，有序对共 $6$ 个，故输出 $6$。

数据范围

本题采用捆绑测试。

$\text{sid}$	$pts$	$n$	$V$	$m$	特殊性质
$1$	$10$	$\leq 10$	$\leq 10^4$	$=2$	无
$2$		$\leq100$	$\leq10^4$	$\leq 100$
$3$		$\leq 750$	$\leq 10^4$	$\leq 500$
$4$		$\leq 5\times 10^3$		$\leq 5\times 10^3$	$A$
$5$		$\leq6\times10^4$		$\leq6\times 10^4$
$6$					$B$
$7$	$20$	$\leq1\times 10^5$	$\leq 10^3$	$\leq1\times 10^5$	$C$
$8$		$\leq 3\times10^5$	$\leq 10^4$	$\leq 3\times10^5$	无

其中 $V=\max\{x,a_i\}$。

特殊性质 $A$：对于所有 $a_i,x$，保证数据在一定范围内随机生成。

特殊性质 $B$：对于所有查询操作 $l,r$，都有 $l=1,r=n$。

特殊性质 $C$：没有修改操作。

对于所有测试数据，$1 \le n, m \le 3\times 10^5$，$1 \le a_i,x \le 10^4$。