One evening, Jack decides to ride his elephant in a straight line to catch grasshoppers. His elephant is $$$H$$$ units tall.
There are $$$N$$$ grasshoppers in his path. He will encounter the $$$i^{th}$$$ grasshopper when his elephant runs for $$$x_i$$$ units, and its altitude will be $$$y_i$$$ units. He also has $$$M$$$ miracle nets for catching insects. The $$$j^{th}$$$ net is $$$l_j$$$ units long.
He will be able to catch the $$$i^{th}$$$ grasshopper with the $$$j^{th}$$$ net if and only if his elephant runs for $$$\textbf{exactly}$$$ $$$x_i$$$ units and $$$ H - l_j \leq y_i \leq H + l_j$$$. Each net will $$$\textbf{disappear}$$$ when he $$$\textbf{catch a grasshopper with it}$$$ (exchanging for transporting the grasshopper to his kitchen).
Jack has $$$Q$$$ questions for you. For the $$$i^{th}$$$ question, Jack wants to know if he wants to catch $$$q_i$$$ grasshoppers, what is the minimum distance he will have to travel.
The first line contains four integers $$$N$$$, $$$M$$$, $$$H$$$, and $$$Q$$$($$$1 \leq N,\ M,\ Q \leq 2\cdot10^5,\ 1 \leq H \leq 10^9$$$) — the number of grasshoppers, the number of nets, the height of Jack's elephant, and the number of questions, respectively.
The $$$i^{th}$$$ line of the following $$$N$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \leq x_i,\ y_i \leq 10^9, x_i \lt x_{i +1}$$$ for all $$$i \lt N$$$) — the distance the elephant has to run to encounter the $$$i^{th}$$$ grasshopper, and the altitude of the $$$i^{th}$$$ grasshopper.
The next line contains M integers $$$l_1,l_2,\dots,l_M\ (1 \leq l_i \leq 10^9)$$$ — the length of nets.
The $$$i^{th}$$$ line of the following $$$Q$$$ lines contains an integer $$$q_i$$$ ($$$1 \leq q_i \leq N$$$) — the number of grasshoppers asked in the $$$i^{th}$$$ question.
For each question, output $$$-1$$$ if the number of grasshoppers exceeds the maximum he can catch. Otherwise, output one integer — the minimum distance his elephant has to run.
1 1 1 12 5101
2
3 3 5 32 65 1510 101 3 5321
-1 10 2
| Name |
|---|


