JOI 面包店是一家以其令人垂涎的羊角面包而闻名的面包店。JOI 面包店有 $N$ 名面包师，编号为 $1$ 到 $N$。面包师 $i$ ($1 \le i \le N$) 制作一个羊角面包需要 $i$ 分钟。一名面包师不能同时制作多个羊角面包。

今天，有 $M$ 名顾客（编号为 $1$ 到 $M$）计划光顾 JOI 面包店，每位顾客计划订购一个羊角面包。顾客 $j$ ($1 \le j \le M$) 将在时间 $T_j$ 下订单，其中时间 $t$ 表示从现在起 $t$ 分钟。然而，如果顾客在下单后 $L$ 分钟内无法收到羊角面包，他们就会放弃并离开商店。换句话说，为了满足顾客 $j$ ($1 \le j \le M$) 的订单，羊角面包必须在时间 $T_j + L$ 或之前完成（包括在时间 $T_j + L$ 时完成）。

管理 JOI 面包店的经理 K 计划今天只安排一名面包师工作，并正在考虑派遣哪位面包师以及在什么时间开始工作。由于面包师在轮班期间专注于制作面包，他们会忽略所有在开始工作时间之后（不包括正好在开始工作时间）下的订单。也就是说，在时间 $t$ 开始工作的面包师无法满足顾客 $j$ ($1 \le j \le M$) 且满足 $T_j > t$ 的订单。

经理 K 目前正在考虑 $Q$ 个工作计划。第 $q$ 个计划 ($1 \le q \le Q$) 是让面包师 $A_q$ 在时间 $B_q$ 开始工作。为了帮助决策，他想知道对于每个计划，如果执行该计划，最多能满足多少位顾客的订单。注意，面包师到达后开始制作第一个羊角面包所需的时间，以及完成一个羊角面包后开始制作下一个羊角面包所需的时间，都可以忽略不计。

给定有关光顾 JOI 面包店的顾客信息和工作计划，编写一个程序，找出每个计划中最多能满足的顾客数量。

输入格式

从标准输入读取以下数据：

$N \ M \ L \ Q$ $T_1 \ T_2 \ \dots \ T_M$ $A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_Q \ B_Q$

输出格式

输出 $Q$ 行到标准输出。第 $q$ 行 ($1 \le q \le Q$) 应包含一个整数，表示在第 $q$ 个工作计划中最多能满足的顾客数量。

数据范围

• $1 \le N \le 4 \times 10^{12}$
• $1 \le M \le 2\,000\,000$
• $1 \le L \le 2 \times 10^{12}$
• $1 \le Q \le 400\,000$
• $0 \le T_j \le 2 \times 10^{12}$ ($1 \le j \le M$)
• $T_j \le T_{j+1}$ ($1 \le j \le M - 1$)
• $1 \le A_q \le N$ ($1 \le q \le Q$)
• $0 \le B_q \le 4 \times 10^{12}$ ($1 \le q \le Q$)
• 给定值均为整数。

子任务

1. (8 分) $M \le 10, Q \le 100\,000$
2. (12 分) $M \le 500, Q \le 100\,000$
3. (30 分) $T_M \le B_q < T_1 + L$ ($1 \le q \le Q$)
4. (10 分) $T_M \le B_q$ ($1 \le q \le Q$)
5. (22 分) $M \le 500\,000, Q \le 100\,000$
6. (18 分) 无附加限制

样例

样例输入 1

4 4 6 4
0 2 3 8
2 3
1 6
3 3
4 7

样例输出 1

3
2
2
0

样例输入 2

20 5 12 4
1 2 4 8 10
1 12
3 10
3 11
15 10

样例输出 2

5
4
3
0

样例输入 3

100000 6 272273 10
5 9 209 8128 17202 50102
164 9
11 24
835 9267
2 256
2 314156
18475 142
1826 18978
44757 1
4 1646
218 44

样例输出 3

2
2
4
3
1
2
5
0
3
2