约化区间

G-30矿道的中段，墙壁上嵌着一排能量感应器——每隔十米一个，像一串发光的纽扣。每个感应器显示一个数字，代表那段矿道的能量密度。

"Zero用能量密度来监控矿道的健康度。"Echo飘到感应器前，"正常情况下，所有段的能量值有一个共同的最大公约数——那是Zero设定的基准。如果某一段的能量值和其他段不再共享这个公约数，说明那里出了问题。"

CC沿着感应器走了一圈，金属靴底踩在冰晶上发出细碎的爆裂声："咋个找这个公约数？"

"不是找一个。"你说，"是维护所有段的公约数。每次修改一个段的能量值，都要重新计算整个区间的公约数。"

"那不是很慢？"

"分段记账。"你说，"把矿道分成很多小段，每段的账目单独存。查询整条矿道的账目时，只需要把覆盖那几段的账目合并——两个数的公约数再和第三个数求公约数，一层一层往上报。"

你开始写。先建一本分层台账，每个节点存对应区间的公约数。修改一个点的能量值时，从那一页往上翻，每一级重新算两个子节点的公约数。查询一个区间的账目时，找到覆盖该区间的几页，合并它们的值。

屏幕上跳出了结果。第47号感应器的能量值被修改后，整个矿道的基准公约数从12变成了1。

"1？"CC瞪眼，"那不是没有公约数了？"

"说明第47号感应器出了问题。"Echo说，"那里的能量值和周围格格不入。"

"就像……一个叛徒。"CC说。

Echo没说话。但她的投影在47号感应器前停了很久。

题目描述

$n$ 个数，支持单点修改和区间GCD查询。

输入格式

$n, m$。然后 $n$ 个数。然后 $m$ 个操作，每个操作是修改或查询。

输出格式

每个查询输出区间GCD。

输入样例

5 3
1 3 5 7 9
Q 1 5
C 1 2 2
Q 1 5

输出样例

1
1

提示

• 线段树维护区间GCD。
• 修改时从叶子往上更新，父节点重新计算子节点的GCD。
• 查询时合并覆盖区间的节点的值。

矿道深处的天花板上，嵌着一幅星空图——不是真的星星，是Zero在火星轨道上部署的监控卫星。每个卫星有一个扇形扫描区，覆盖地面上一段区域。

"要统计某个矩形窗口里有多少颗卫星。"Echo说，"不是一颗一颗数——是用推窗法，从左推到右，一路上登记和注销。"

"推窗？"CC问。

"就像拉窗帘。"你说，"窗帘从左往右拉，遇到一颗星星就记下来，遇到窗口的右边界就把这颗星星划掉。同时维护一个y轴上的名册，随时查当前窗帘里有多少颗星星。"