题目描述

小可穿越了，来到一处神秘地下室之中，而离开地下室的大门有一只神兽把守。

地下室内有一排整齐排列的袋子，依次编号为 $1$ 到 $n$。每个袋子里都装着数量不等的普通宝石，第 $i$ 个袋子里的宝石数量为 $a_i$。另外还有一件可以进行宝石融合的法器，可以将 $k$ 枚普通宝石融合为 $1$ 枚高阶宝石。

要想离开地下室，必须解答正确神兽所提出的 $q$ 次询问。每次询问神兽都会给出一个区间 $[l, r]$，问把这个区间内编号所有袋子的的普通宝石进行融合，可以获得多少枚高阶宝石

现在，请你帮助小可计算出每次询问能够获得多少颗高阶宝石。

输入格式

第一行包含三个整数 $n$、$q$ 和 $k$，分别表示袋子的数量、询问的次数以及融合出一颗高阶宝石所需的普通宝石的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \cdots, a_n$，其中 $a_i$ 表示第 $i$ 个袋子里的普通宝石数量。

接下来 $q$ 行，每行包含两个整数 $l$ 和 $r$，表示一次神兽询问的问题的区间。

输出格式

输出 $q$ 行，每行一个整数，表示对对应区间内普通宝石进行融合小可能够获得的高阶宝石对数量。

5 3 2
1 2 3 4 5
1 3
2 4
3 5

3
4
6

数据范围

对于 $30\%$ 的数据：

• $1\leq l \leq r \leq n\leq 10^2$

• $1\leq q\leq 10^2$

对于 $100\%$ 的数据：

• $1\leq l \leq r \leq n\leq 10^5$

• $1\leq q\leq 10^5$

• $1\leq k\leq 10^3$

• $0\leq a_i\leq 10^3$