给定一个正整数序列，以及一系列对该序列进行的更新和查询操作。更新和查询以任意顺序给出。

每次更新操作会将序列中的某一项替换为给定的值。更新是累积的：后续的所有指令均在执行了之前的替换操作后的序列上进行。

每次查询操作指定了（可能经过更新后的）序列的一个子序列，以及需要从该子序列中排除的项数。根据排除项的不同，会产生一个或多个整数集合。每个集合都有其成员的最大公约数（GCD）。查询的答案是所有这些集合的 GCD 的最小公倍数（LCM）。

图 H.1. 样例输入 1 中最后一个查询 “Q 2 5 2” 的解答过程

输入格式

输入包含单个测试用例，格式如下：

$n \ m$ $a_1 \dots a_n$ $c_1$ $\vdots$ $c_m$

第一行包含两个整数 $n$ 和 $m$。$n$ ($1 \le n \le 10^5$) 是整数序列的长度，$m$ ($1 \le m \le 10^5$) 是指令的数量。原始整数序列 $a_1, \dots, a_n$ 在第二行给出。对于 $i = 1, \dots, n$，满足 $1 \le a_i \le 10^6$。接下来的 $m$ 行，每行要么是一个以字母 U 开头的更新指令，要么是一个以字母 Q 开头的查询指令。

更新指令格式如下：

$U \ j \ x$

该指令表示将序列中第 $j$ 项替换为整数 $x$。满足 $1 \le j \le n$ 且 $1 \le x \le 10^6$。更新是累积的：该指令之后的所有指令均在执行了该更新后的序列上进行。

查询指令格式如下：

$Q \ l \ r \ k$

其中，$l$ 和 $r$ 指定了子序列的起始和结束位置，$k$ 是从该子序列 $b_l, \dots, b_r$ 中需要排除的项数，其中 $b_1, \dots, b_n$ 是在执行完该查询之前的所有更新操作后的序列。满足 $1 \le l$，$0 \le k \le 2$，且 $l + k \le r \le n$。

输出格式

更新指令无需输出。对于每个查询指令，输出一行，内容为通过从序列 $b_l, \dots, b_r$ 中排除 $k$ 项所构成的所有子序列的集合的 GCD 的最小公倍数（LCM）。

样例

样例输入 1

5 10
12 10 16 28 15
Q 1 3 1
Q 3 4 0
Q 2 2 0
Q 2 5 2
U 3 21
Q 1 3 1
Q 2 4 1
Q 3 5 1
Q 4 4 0
Q 2 5 2

样例输出 1

4
4
10
20
6
14
21
28
210

说明

对于本测试用例的第一个查询 “Q 1 3 1”，子序列为 12 10 16。排除其中一项会产生三个集合：$\{12, 10\}$，$\{12, 16\}$ 和 $\{10, 16\}$。它们的 GCD 分别为 2，4 和 2，因此输出应为它们的 LCM，即 4。

注意，第五条指令 “U 3 21” 更新了序列，从而改变了第六条指令 “Q 1 3 1” 的答案。该更新使子序列变为 12 10 21。因此，排除一项后的集合变为 $\{12, 10\}$，$\{12, 21\}$ 和 $\{10, 21\}$。它们的 GCD 分别为 2，3 和 1，因此该查询的输出应为它们的 LCM，即 6。