思路分析

1. 分数公式化简

首先，我们分析分数的计算公式。分数由两部分组成：

• 正贡献项: 序列中所有下标是 $x$ 的倍数的元素之和, 即 $\sum a_{i \cdot x}$。
• 负贡献项: 序列中所有下标是 $y$ 的倍数的元素之和, 即 $\sum a_{j \cdot y}$。

我们考虑一个下标 $k$，如果它同时是 $x$ 的倍数和 $y$ 的倍数，那么它一定是 $x$ 和 $y$ 的最小公倍数 $\text{lcm}(x, y)$ 的倍数。在这种情况下，元素 $a_k$ 会在正贡献项中被加一次，在负贡献项中被减一次，所以 $a_k - a_k = 0$，它们对总分数的贡献相互抵消了。

题目内容

多多有一个长度为 $n$ 的序列 $(a_1,a_2,...,a_n)$，对于给定的 $x$ 和 $y$ ；

一个序列的分数定义为 $\sum_{1}^{\left\lfloor\frac{n}{x}\right\rfloor} a_{i \cdot x}-\sum_{1}^{\left\lfloor\frac{n}{y}\right\rfloor} a_{j \cdot y}$

序列元素可任意交换位置，得到一个新的序列。多多想知道，经过若干次操作后，新的序列的最大分数是多少。

输入描述

第一行为 $2$ 个数字，$n,q$ ，其中 $n≤2*10^5,q≤10^4$

接下来 $1$ 行 $n$ 个数字，分别为 $a_1,a_2,...,a_n$ ，其中 $0≤a_1＜10^9$

接下来 $q$ 行，每行两个数字 $x,y$ ，其中 $1≤x,y≤n$

输出描述

输出 $q$ 行，每行包含一个数字，代表序列的最大分数

样例1

输入

7 1
5 9 3 8 2 10 3
2 3

输出

17

说明

按照题目中的分数定义，序列的分数为

$(a_2+a_4+a_6)-(a_3+a_6)$ ；

经过元素交换后一种可能的序列为

$3$ $9$ $2$ $10$ $8$ $5$ $3$ ，

此时分数最大为 $(9+10+5)-(2+5)=17$