U522345 pithier

给定长度为 $n$ 的正整数（所有正整数均在 **$2$~$9$** 之间）序列 $a$（下标从 $1$ 开始）和 $m$ 次操作，每次操作需要求出 $\sum_{i=l}^{r}(\sum_{j=l}^{i}a_j)\operatorname{mod}a_{i}$。

第一行有两个整数：$n$ 和 $m$。 第二行有 $n$ 个 $2$~$9$ 之间的正整数，表示这个序列 $a$。 接下来 $m$ 行，每行两个整数 $l$，$r$，表示一次查询操作。

共有 $m$ 行，每行输出所查询的值。

对于 $30\%$ 的数据 $1\le n,m\le 1000$。 对于 $100\%$ 的数据 $1\le n,m\le 200000$。