农民 Bajtazar 购买了一块面积为 $n$ 公亩的土地，并打算在上面种植草。割下并晒干的草将作为他农场里饲养的动物的饲料。

这块土地上将种植 $n$ 种草的混合物，每种草各占地 1 公亩。已知第 $i$ 种草每天生长 $a_i$ 厘米，且不受天气条件或土壤肥力的影响。此外，已知在 1 公亩的土地上割下 1 厘米高的草可以获得正好 1 公斤的干草。

Bajtazar 有一台割草机，可以将其设置为任意高度 $b$ —— 在此设置下，所有高于 $b$ 厘米的草都会被修剪到正好 $b$ 厘米的高度。

Bajtockie 法律要求在每次割草后记录所获得的干草量。Bajtazar 面临一个选择：要么买一台秤，要么编写一个程序，根据割草的日期和割草机的设置来估算每次割草后获得的干草重量。他觉得后一种选择更方便、更便宜。

假设草是在第 0 天午夜播种的，并且总是在午夜进行收割。我们还假设将土地割到任意高度 $b$ 所需的时间可以忽略不计。

输入格式

输入的第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 500\,000$)，分别表示 Bajtazar 的土地面积（公亩，同时也是种植的草的种类数）和割草次数。第二行包含一个由 $n$ 个整数组成的序列 $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^6$)，表示各品种草的生长速度。

接下来的 $m$ 行描述了 Bajtazar 进行的割草操作：第 $i$ 次割草由该行中的两个整数 $d_i$ 和 $b_i$ ($1 \le d_i \le 10^{12}, 0 \le b_i \le 10^{12}$) 描述，表示在第 $d_i$ 天，Bajtazar 将草修剪到了 $b_i$ 厘米的高度。你可以假设割草操作是按时间顺序给出的，即 $d_1 < d_2 < \dots < d_m$。

此外，你可以假设 Bajtazar 永远不会让土地上任何地方的草高度超过 $10^{12}$ 厘米。

输出格式

输出应包含 $m$ 行。第 $i$ 行应包含第 $i$ 次割草后获得的干草总重量（单位：公斤）。

样例

输入格式 1

4 4
1 2 4 3
1 1
2 2
3 0
4 4

输出格式 1

6
6
18
0

说明 1

下表显示了在每次割草前后，第 1、2、3、4 种草的高度：

• 第 1 天：割草前高度为 1, 2, 4, 3；割草后高度为 1, 1, 1, 1。
• 第 2 天：割草前高度为 2, 3, 5, 4；割草后高度为 2, 2, 2, 2。
• 第 3 天：割草前高度为 3, 4, 6, 5；割草后高度为 0, 0, 0, 0。
• 第 4 天：割草前高度为 1, 2, 4, 3；割草后高度为 1, 2, 4, 3。