P15948 Baker

JOI Bakery is a bakery famous for its mouth-watering croissants. JOI Bakery has $N$ bakers numbered from $1$ to $N$. Baker $i$ ($1 \leq i \leq N$) takes $i$ minutes to make one croissant. One baker cannot make multiple croissants at the same time. Today, $M$ customers numbered from $1$ to $M$ are scheduled to visit JOI Bakery, and each customer plans to order one croissant. Customer $j$ ($1 \leq j \leq M$) will order a croissant at time $T_j$, where time $t$ denotes the time $t$ minutes from now. However, a customer who cannot receive their croissant within $L$ minutes of ordering will give up and leave the shop. In other words, to fulfill the order of customer $j$ ($1 \leq j \leq M$), the croissant must be finished by time $T_j + L$ (including exactly at time $T_j + L$). Manager $K$, who manages JOI Bakery, plans to have exactly one baker work today and is considering which baker to send and at what time. Since bakers focus intensely on bread-making during their shift, **they ignore all orders placed after their start time (not including exactly at the start time)**. That is, a baker starting work at time $t$ cannot fulfill orders from customers $j$ ($1 \leq j \leq M$) such that $T_j > t$. Manager $K$ is currently considering $Q$ work plans. The $q$-th plan ($1 \leq q \leq Q$) is to have baker $A_q$ start work at time $B_q$. To help with the decision, for each of the $Q$ plans, he wants to know the maximum number of customers whose orders can be fulfilled if that plan is executed. Note that the time it takes for a baker to start making a croissant after arriving, and the time it takes to start making a new croissant after finishing one, can be ignored. Given information about the customers visiting JOI Bakery and the work plans, create a program to find the maximum number of customers whose orders can be fulfilled for each plan.

Read the following data from the standard input. > $N$ $M$ $L$ $Q$\ > $T_1$ $T_2$ $\cdots$ $T_M$\ > $A_1$ $B_1$\ > $A_2$ $B_2$\ > $\vdots$\ > $A_Q$ $B_Q$

Write $Q$ lines to the standard output. The $q$-th line ($1 \leq q \leq Q$) of the output should contain an integer representing the maximum number of customers whose orders can be fulfilled in the $q$-th work plan.

### Sample 1 Regarding the $1$st work plan, baker $2$ starting at time $3$ can fulfill the orders of $3$ customers $1,2$, and $3$, for example, as follows: - First, to fulfill customer $1$’s order, start making a croissant at time $3$ and finish it $2$ minutes later at time $5$. (This satisfies the condition to finish by time $T_1 + L = 0 + 6 = 6$.) - Next, to fulfill customer $2$’s order, start making a croissant at time $5$ and finish it $2$ minutes later at time $7$. (This satisfies the condition to finish by time $T_2 + L = 2 + 6 = 8$.) - Finally, to fulfill customer $3$’s order, start making a croissant at time $7$ and finish it $2$ minutes later at time $9$. (This satisfies the condition to finish by time $T_3 + L = 3 + 6 = 9$.) Customer $4$’s order is ignored because it arrives after the baker’s start time, so it cannot be fulfilled. Thus, a maximum of $3$ customers’ orders can be fulfilled, so the $1$st line outputs $3$. Regarding the $2$nd work plan, baker $1$ starting at time $6$ can fulfill the orders of $2$ customers $2$ and $3$, for example, as follows: - First, to fulfill customer $3$’s order, start making a croissant at time $6$ and finish it $1$ minute later at time $7$. (This satisfies the condition to finish by time $T_3 + L = 3 + 6 = 9$.) - Next, to fulfill customer $2$’s order, start making a croissant at time $7$ and finish it $1$ minute later at time $8$. (This satisfies the condition to finish by time $T_2 + L = 2 + 6 = 8$.) Customer $4$’s order is ignored because it arrives after the start time. Also, the order of customer $1$, which needs to be finished by time $6$, cannot be fulfilled. Thus, a maximum of $2$ customers’ orders can be fulfilled, so the $2$nd line outputs $2$. Regarding the $3$rd work plan, baker $3$ starting at time $3$ can fulfill orders for customers $1$ and $3$, or customers $2$ and $3$, but cannot fulfill all orders for customers $1,2$, and $3$. They also cannot fulfill the order for customer $4$ which arrives after the start time. Thus, a maximum of $2$ customers’ orders can be fulfilled, so the $3$rd line outputs $2$. Regarding the $4$th work plan, baker $4$ starting at time $7$ cannot fulfill any customer’s order. Thus, the $4$th line outputs $0$. This sample input satisfies the constraints of Subtasks $1,2,5$, and $6$. ### Sample 2 This sample input satisfies the constraints of all the subtasks. ### Sample 3 This sample input satisfies the constraints of Subtasks $1,2,5$, and $6$. ### Constraints - $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$). - Given values are all integers. ### Subtasks 1. (8 points) $M \leq 10,Q \leq 100000$. 2. (12 points) $M \leq 500,Q \leq 100000$. 3. (30 points) $T_M \leq B_q < T_1 + L$ ($1 \leq q \leq Q$). 4. (10 points) $T_M \leq B_q$ ($1 \leq q \leq Q$). 5. (22 points) $M \leq 500000,Q \leq 100000$. 6. (18 points) No additional constraints.