该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

Background

TG T1 view.cpp

Description

小 Q 家的旁边有一段无限长的墙壁，墙壁上涂满了不同的颜色。奇怪的是，每一种颜色是连在一起的，也就是说在一段距离内只存在一种颜色。

小 Q 是一个艺术家，他发现在一段连续的墙壁中，我们可以将其切成不同的几段墙壁，使得每段墙壁的长度不超过$k$，且没有两段墙壁包含相同的颜色。也就是说，每种颜色不会在不同的墙壁段中出现。

一段连续墙壁的风景值被定义为符合以上条件切法的墙壁段的最小值。

小 Q 发现这个问题并不简单，所以他把这个问题告诉了聪明的你，希望你可以帮助他解决这个问题。

Format

Input

输入共 $q+2$ 行。

第一行，输入三个数 $n,q,k$，表示颜色数量，询问个数和题目中所描述的 $k$。

接下来一行，输入 $n$ 个数 $a_i$，分别表示每段颜色的墙壁的长度。

若输入 $x\ y$，那么实际墙壁上1号颜色的位置为 $[1,x]$，2号颜色的位置为 $[x+1,x+y]$。

接下来 $q$ 行，每行两个数 $l,r$ ，表示询问距离 $l$ 到距离 $r$ 这一段墙壁的风景值。

Output

输出包括 $q$ 行，表示每一个询问的答案。

Samples

5 3 3
2 3 1 1 3
3 6
5 9
2 8

2
2
3

8 10 5
3 4 2 2 1 1 2 5
11 18
1 5
1 10
4 10
4 8
3 10
1 17
3 19
10 11
1 20

2
1
3
2
1
2
4
4
1
5

样例 3 参见附件 view03.in\view03.ans。

Explanation

Sample 1 Explanation

询问 1：从 3 到 6 的位置上，可以分成 3-5，6 两段墙壁使得没有两段墙壁拥有相同的颜色并且长度小于 $k$，且易证不存在另一种方法可以满足上述条件且分成更少段墙壁。

询问 2：从 5 到 9 的位置上，可以分成 5-7，8-9 或者 5-6，7-9 两种方法使得满足以上条件且分成的段数最小。

询问 3：从 2 到 8 的位置上，可以分成 2，3-5，6-8 三端墙壁使得满足条件，易证此为最优解。

Sample 2 Explanation

本样例只提供一种询问分段的答案。

询问 1：分成 11-13，14-18。

询问 2：分成 1-5。

询问 3：分成 1-3，4-7，8-10。

询问 4：分成 4-7，8-10。

询问 5：分成 4-8。

询问 6：分成 3-7，8-10。

询问 7：分成 1-3，4-7，8-12，13-17。

询问 8：分成 3-7，8-11，12-15，16-19。

询问 9：分成 10-11。

询问 10：分成 1-3，4-7，8-11，12-15，16-20。

Limitation

对于$100\%$的数据，保证 $n\leq 10^6,q\leq 5\times 10^5,1\leq l\leq r\leq\sum^{n}_{i=1}{a_i}\leq 10^{16},1\leq a_i\leq k\leq 10^9$。

时空限制：1500ms/512MB。