题目描述

出题人已将创意全数用于之前的题目，因此本题不会在题面上为难 Anton。他只是给你一个有趣的问题。

给定一个由 $n$ 个整数组成的数组 $a$。同时给出 $q$ 个查询 $[l;r]$。对于每个查询，找出所有对 ($tl;tr$) 中 $\operatorname{sum}[tl;tr] \times \operatorname{gcd}[tl;tr]$ 的最大值，其中

• $l \le tl \le tr \le r$；
• $\operatorname{sum}[tl;tr]$ —— 区间 $[tl;tr]$ 内所有数的和；
• $\operatorname{gcd}[tl;tr]$ —— 区间 $[tl;tr]$ 内所有数的最大公约数。

两个数 $a$ 和 $b$ 的最大公约数是指能同时整除 $a$ 和 $b$ 的最大正整数 $x$。

一组数的最大公约数是指能整除该组所有元素的最大正整数 $x$。

输入格式

• 第一行包含两个整数 $n$、$q$（$1 \le n, q \le 2 \cdot 10^5$）——分别表示数组的元素个数和查询个数。
• 第二行包含 $n$ 个整数 $a_i$（$1 \le a_i \le 6 \cdot 10^6$）——数组的描述。
• 接下来的 $q$ 行，每行包含两个整数 $l$、$r$（$1 \le l \le r \le n$）——查询的描述。

输出格式

输出 $q$ 个整数——每个查询的答案。

3 2
3 3 2
1 3
2 3

18
9

8 6
2 4 8 8 8 2 4 16
1 8
2 5
3 4
2 4
7 7
3 6

256
192
128
128
16
192

提示

在第一个示例中，存在以下区间：

• $[1;1]$ —— $\operatorname{sum}[1;1] \times \operatorname{gcd}[1;1]$ = $3 \times 3$ = $9$；
• $[1;2]$ —— $\operatorname{sum}[1;2] \times \operatorname{gcd}[1;2]$ = $6 \times 3$ = $18$；
• $[1;3]$ —— $\operatorname{sum}[1;3] \times \operatorname{gcd}[1;3]$ = $8 \times 1$ = $8$；
• $[2;2]$ —— $\operatorname{sum}[2;2] \times \operatorname{gcd}[2;2]$ = $3 \times 3$ = $9$；
• $[2;3]$ —— $\operatorname{sum}[2;3] \times \operatorname{gcd}[2;3]$ = $5 \times 1$ = $5$；
• $[3;3]$ —— $\operatorname{sum}[3;3] \times \operatorname{gcd}[3;3]$ = $2 \times 2$ = $4$。

评分细则

• （$4$ 分）：$n \le 3$；
• （$8$ 分）：$n, q \le 10^3$；
• （$5$ 分）：$n \le 10^3$；
• （$17$ 分）：$n, q \le 10^5$；
• （$14$ 分）：$n \le 10^5$；
• （$5$ 分）：$a_i \le 20$；
• （$7$ 分）：$a_i \le 10^3$；
• （$16$ 分）：$l = 1$；
• （$24$ 分）：无额外限制。

翻译由 DeepSeek V3 完成