题目背景

本题测试数据较大，可能需要等待较长时间加载数据。

题目描述

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

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

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

经理 K 目前正在考虑 $Q$ 个工作计划。第 $q$ 个计划 ($1 \leq q \leq Q$) 是让面包师 $A_q$ 在时间 $B_q$ 开始工作。为了帮助做出决定，对于这 $Q$ 个计划中的每一个，他想知道如果执行该计划，可以完成的订单的最大顾客数量。请注意，面包师到达后开始制作牛角面包所需的时间，以及制作完一个后开始制作下一个新牛角面包所需的时间，均可以忽略不计。

给定有关光顾 JOI 面包店的顾客信息和工作计划，编写一个程序，求出每个计划中可以完成订单的最大顾客数量。

输入格式

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

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

输出格式

向标准输出写入 $Q$ 行。输出的第 $q$ 行 ($1 \leq q \leq Q$) 应包含一个整数，表示在第 $q$ 个工作计划中可以完成订单的最大顾客数量。

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

3
2
2
0

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

5
4
3
0

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

2
2
4
3
1
2
5
0
3
2

提示

样例 1

关于第 $1$ 个工作计划，面包师 $2$ 在时间 $3$ 开始工作，可以完成 $3$ 位顾客 $1, 2$ 和 $3$ 的订单，例如方案如下：

• 首先，为了完成顾客 $1$ 的订单，在时间 $3$ 开始制作牛角面包，并在 $2$ 分钟后的时间 $5$ 完成。（这满足了在时间 $T_1 + L = 0 + 6 = 6$ 之前完成的条件。）
• 接下来，为了完成顾客 $2$ 的订单，在时间 $5$ 开始制作牛角面包，并在 $2$ 分钟后的时间 $7$ 完成。（这满足了在时间 $T_2 + L = 2 + 6 = 8$ 之前完成的条件。）
• 最后，为了完成顾客 $3$ 的订单，在时间 $7$ 开始制作牛角面包，并在 $2$ 分钟后的时间 $9$ 完成。（这满足了在时间 $T_3 + L = 3 + 6 = 9$ 之前完成的条件。）

顾客 $4$ 的订单被忽略，因为它是在面包师开始时间之后到达的，所以无法完成。因此，最多可以完成 $3$ 位顾客的订单，所以第 $1$ 行输出 $3$。

关于第 $2$ 个工作计划，面包师 $1$ 在时间 $6$ 开始工作，可以完成 $2$ 位顾客 $2$ 和 $3$ 的订单，例如方案如下：

• 首先，为了完成顾客 $3$ 的订单，在时间 $6$ 开始制作牛角面包，并在 $1$ 分钟后的时间 $7$ 完成。（这满足了在时间 $T_3 + L = 3 + 6 = 9$ 之前完成的条件。）
• 接下来，为了完成顾客 $2$ 的订单，在时间 $7$ 开始制作牛角面包，并在 $1$ 分钟后的时间 $8$ 完成。（这满足了在时间 $T_2 + L = 2 + 6 = 8$ 之前完成的条件。）

顾客 $4$ 的订单由于在开始时间之后到达而被忽略。此外，顾客 $1$ 的订单由于需要在时间 $6$ 之前完成，因此无法完成。因此，最多可以完成 $2$ 位顾客的订单，所以第 $2$ 行输出 $2$。

关于第 $3$ 个工作计划，面包师 $3$ 在时间 $3$ 开始工作，可以完成顾客 $1$ 和 $3$、或者顾客 $2$ 和 $3$ 的订单，但不能同时完成顾客 $1, 2$ 和 $3$ 的所有订单。他们也无法完成在开始时间之后到达的顾客 $4$ 的订单。因此，最多可以完成 $2$ 位顾客的订单，所以第 $3$ 行输出 $2$。

关于第 $4$ 个工作计划，面包师 $4$ 在时间 $7$ 开始工作，无法完成任何顾客的订单。因此，第 $4$ 行输出 $0$。

该样例输入满足子任务 $1, 2, 5$ 和 $6$ 的约束。

样例 2

该样例输入满足所有子任务的约束。

样例 3

该样例输入满足子任务 $1, 2, 5$ 和 $6$ 的约束。

约束条件

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

子任务

1. (8 分) $M \leq 10, Q \leq 100000$。
2. (12 分) $M \leq 500, Q \leq 100000$。
3. (30 分) $T_M \leq B_q < T_1 + L$ ($1 \leq q \leq Q$)。
4. (10 分) $T_M \leq B_q$ ($1 \leq q \leq Q$)。
5. (22 分) $M \leq 500000, Q \leq 100000$。
6. (18 分) 无附加约束。