题目描述

出题人在前几题中已经耗尽了所有创意，所以这道题的题面不会再折磨 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$ 个整数，分别表示各个询问的答案。

输入 #1

3 2
3 3 2
1 3
2 3

输出 #1

18
9

子任务

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