时空限制

2S/512M

题目描述

定义 $f(x)$ 为满足：使得从 $1$ 到 $y$ 的所有正整数都能整除 $x$ 的最大正整数 $y$。

给定一个长度为 $n$ 的数组 $a$ 和 $q$ 次询问。每次询问会给出区间 $[l,r]$。对于每次询问 $[l, r]$，请计算 $f(\operatorname{lcm}(a_l, \dots, a_r))$。

其中，$\operatorname{lcm}(a_l,a_{l+1}, \dots ,a_r)$ 表示这几个数的最小公倍数。

格式

输入格式

第一行包含两个正整数 $n$ 和 $q$，分别表示数组 $a$ 的长度和询问的次数。

第二行包含 $n$ 个正整数，第 $i$ 个数表示 $a_i$。

接下来 $q$ 行，每行包含两个正整数 $l$ 和 $r$，表示一组询问的区间。

输出格式

输出共 $q$ 行，第 $i$ 行输出一个正整数，表示第 $i$ 组询问的答案。

样例

样例输入 #1

5 3
1 2 3 4 5
1 3
2 4
1 5

样例输出 #1

3
4
6

样例解释 #1

• 对于第 $1$ 个询问 $l=1, r=3$：区间元素为 $1, 2, 3$，最小公倍数为 $\operatorname{lcm}(1, 2, 3) = 6$。$1, 2, 3$ 都能整除 $6$，而 $4$ 不能整除 $6$，因此满足条件的最大正整数 $y = 3$，$f(6) = 3$。
• 对于第 $2$ 个询问 $l=2, r=4$：区间元素为 $2, 3, 4$，最小公倍数为 $\operatorname{lcm}(2, 3, 4) = 12$。$1, 2, 3, 4$ 都能整除 $12$，而 $5$ 不能整除 $12$，因此满足条件的最大正整数 $y = 4$，$f(12) = 4$。
• 对于第 $3$ 个询问 $l=1, r=5$：区间元素为 $1, 2, 3, 4, 5$，最小公倍数为 $\operatorname{lcm}(1, 2, 3, 4, 5) = 60$。$1, 2, 3, 4, 5, 6$ 都能整除 $60$，而 $7$ 不能整除 $60$，因此满足条件的最大正整数 $y = 6$，$f(60) = 6$。

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$1 \le n,q \le 2 \times 10^5$，$1 \leq a_i \leq 10^6$。