【题目描述】

有 $n$ 个人要吃饭。有 $m$ 个电饭锅供他们使用。每个人煮饭都需要 $T$ 的时间。当一个电饭锅被一个人占用时，另一个人不能同时用它。第 $i$ 个人计划在时刻 $t_i$ 煮饭，他不会在 $t_i$ 时刻之前煮饭，但他可能必须等待其他人煮完饭才能煮自己的饭。给定每个人计划煮饭的时间，你需要安排大家煮饭的时间和所用的电饭锅，使得所有人等待的时长之和最小。即：你需要确定 $s_i\ge t_i$ 表示第 $i$ 个人真实的煮饭时间，以及 $p_i\in[1,m]$ 表示第 $i$ 个人使用的电饭锅，使得 $p_i=p_j \Rightarrow |s_i-s_j| \ge T$ 恒成立，并最小化 $\sum_{i=1}^n (s_i-t_i)$。

然而，计划赶不上变化，现在情况有变，有人可能要迟到。你需要回答 $q$ 个询问，第 $j$ 个询问为：如果 $t_{a_j}$ 变为 $t_{a_j}+b_j$，那么原问题的答案会变成什么。注意：询问间独立，即每次询问并不会真的把 $t_{a_j}$ 变为 $t_{a_j}+b_j$。

【输入格式】

从文件 $measure.in$ 中读入数据。

第一行三个正整数 $n,m,T$（$n \le 3\times 10^5$，$m \le 5$，$T \le 10^9$）。

第二行 $n$ 个正整数，第 $i$ 个数为 $t_i$（$t_i \le 10^9$）。

第三行一个非负整数 $q$（$q \le 10^5$）。

接下来 $q$ 行，每行两个正整数 $a_j,b_j$（$a_j \le n$，$b_j \le 10^9$）。

【输出格式】

输出到文件 $measure.out$ 中。

共 $q$ 行，每行一个非负整数，表示第 $j$ 次询问的答案。

【样例 #1】

输入：

5 2 5
2 4 6 7 8
3
1 6
2 3
3 4

输出：

11
8
3

【样例 #2】

输入：

11 3 3
1 4 1 5 9 2 6 5 3 5 8
9
7 9
3 2
3 8
4 6
2 6
4 3
3 8
3 2
7 9

输出：

6
15
9
5
7
7
9
15
6

【数据范围和约定】

对于 $20\%$ 的数据：$n,q\le 100$；

对于 $30\%$ 的数据：$n,q\le 1000$；

对于另外 $10\%$ 的数据：$q\le 5$；

对于再另外 $20\%$ 的数据：$m=1$；

对于 $100\%$ 的数据：$1\le a_j\le n \le 3\times 10^5$，$1\le m \le 5$，$0\le q \le 10^5$，$1 \le T,t_i,b_j \le 10^9$。