问题描述
给定一个长度为 n 的正整数序列 A，你要对这个序列进行 Q 次操作。
操作有两种类型：
- 1 L R：求 gcd(AL, lcm(AL+1, gcd(AL+2, ...((R−L) mod 2 = 1? gcd(AR−1, AR) : lcm(AR−1, AR)))))
- 2 i x：把 Ai 变成 x
输入格式
第一行两个正整数 n 和 Q，表示序列的长度和操作次数。
接下来 Q 行，每行输入一个操作。
输出格式
对于每个操作 1，输出答案。
样例 1 输入
5 3 1 4 6 9 3 1 3 5 2 1 8 1 1 5样例 1 输出
34大样例
数据规模与约定
对于所有数据，满足$ 2 ≤ n ≤ 2 × 10^5，1 ≤ Q ≤ 2 × 10^5，1 ≤ L < R ≤ n，1 ≤ Ai , x ≤ 10^9$
Subtask1 10pts: $n, Q ≤ 5 × 10^3$
Subtask2 20pts: Ai ≤ 10，没有操作 2
Subtask3 20pts: 没有操作 2，依赖 Subtask 2
Subtask4 50pts: 无特殊限制，依赖 Subtask 1,2,3