T113174 [IV] Angel of Sin

**赛时通知 : 比赛延后 1.5h** 「夢に縛られたのに，誰かのため 涙 流す」 「明明——困于梦境，却依然，依然为某人——泪流不止」

在 4102 年，刚刚转学的 Zaych 还在沉浸在她的~~校园生活~~的时候。 她在耀夜姬的扇子上看到了一个水题 : 这个题目大概为 $a \bmod b=c$。 时隔 5000 年，她开始解决这个问题。 虽然她很懒，但是她觉得用她的使魔 Smallrabbit 19c 来解决这个问题是大材小用。 所以她在睡前想到了另一个问题 : 给你一个长度为 $N$ 的数列 $num_{1\dots N}$ 和一个固定的常数 $k$ 。 一共有 $M$ 个询问，每个询问查询包含一个区间 $[l,r]$： $$ \sum\limits_{l \leq i,j \leq r} [\ num_i \bmod num_j=k \ ] $$ 为了表示她使魔的强大，她设定时间限制 : $2.5\text s$，空间限制 : $350 \text M$。 Smallrabbit 19c 觉得太简单了，它把这个问题丢给了你。

一行三个正整数 $N,M,K$，意义如上。 第二行 $N$ 个正整数 代表 $num_{1\dots N}$。 以下 $M$ 行每行两个正整数 $l,r$。

一共 $M$ 行，每行一个非负整数代表答案。

样例 $\text 1$ 说明 : 对于第一个询问，有数对 $(1,7)$ $(1,2)$ $(7,2)$ 贡献。 对于第二个询问，有数对 $(7,2)$ $(5,2)$ $(5,4)$ 贡献。 对于第三个询问，$2\bmod 4=2 , 4 \bmod 2=0$，所以没有贡献。 --- $\max num_i \leq N$ , 除了样例。 |数据|$N,M$|$k$| |:-:|:-:|:-:|:-:| |$1$|$10$|$k \leq 10$| |$2$|$10^2$|$k \leq 2\times 10$| |$3$|$10^4$|$10^2 \leq k \leq 2 \times 10^2$| |$4$|$10^4$|$10^2 \leq k \leq 2 \times 10^2$| |$5$|$10^4$|$10^2 \leq k \leq 2 \times 10^2$| |$6$|$5 \times 10^4$|$10^2 \leq k \leq 2 \times 10^2$| |$7$|$5 \times 10^4$|$10^2 \leq k \leq 2 \times 10^2$| |$8$|$5 \times 10^4$|$10^2 \leq k \leq 2 \times 10^2$| |$9$|$5 \times 10^4$|$5 \times 10^2 \leq k \leq 2 \times 10^3$| |$10$|$5 \times 10^4$|$5 \times 10^3 \leq k \leq 2 \times 10^4$|