P5624 [Celeste-A] Black Moonrise

> 幽灵 > > 不属于这个世界 > >但因这个世界而诞生 > >潜藏在秩序之外 > >$$ > > 醒来吧，我的心是堡垒\\ > >在梦中我易受伤害

在 Madeline 的梦境中，城市的边境是由大大小小的宇宙碎片构成的。 每个宇宙碎片都有一定的能量值，由于碎片的大小有一定的差异，因此它们的能量值也有大有小。 Madeline 很享受在碎片之间穿梭，她每次都会选择两个宇宙碎片，并获得它们能量值的最大公约数的愉悦值。注意这两个宇宙碎片可以相同。 宇宙碎片构成了一段序列 $a_1,a_2,\cdots,a_n$，每次 Madeline 都会选择它的一个区间，对于这个区间里面的任意两个宇宙碎片 $(u,v)$，她都会进行一次穿梭。**注意这里的 $(u,v)$ 是有序对。** 形式化地，Madeline 每次获得的愉悦值为 $$\sum_{i=l}^r\sum_{j=l}^r \gcd(a_i,a_j)$$ 当 Madeline 从她的梦中被唤醒时，她发现所有的宇宙碎片都消失了。她不记得在梦中每次穿梭时获得的愉悦值是多少，只依稀记得她选择的区间了。 于是她找到了你——一个信息学大佬，请你根据她每次选择的区间，还原她当时的愉悦值。

第一行两个正整数 $n,q$，分别表示碎片个数以及询问数。 第二行有 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，表示每个碎片的能量值。 接下来 $q$ 行，每行两个整数 $l_i,r_i$，表示第 $i$ 次询问 Madeline 选择的区间。

对于每个询问输出一行，表示在这次询问中，Madeline 获得的愉悦值的总和。

- 对于 $10\%$ 的数据，满足 $n,q\leq 200$； - 对于 $20\%$ 的数据，满足 $n,q\leq 2250$； - 对于 $40\%$ 的数据，满足 $n,q\leq 4000$； - 对于 $100\%$ 的数据，满足 $n,q,a_i\leq 10^5$。 **保证数列和询问均为随机生成。**