D. What's the Time, Mr. Fox?
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

"What's the Time, Mr. Fox?" (狐狸先生幾多點) is a popular children's game in Hong Kong. In this chase/tag-styled game, $$$N$$$ players cautiously approach the tagger, Mr. Fox, before desperately trying to avoid being caught.

Today, you are participating in a "What's the Time, Mr. Fox?" game with $$$N$$$ friends. You will be playing as Mr. Fox, while your friends will be the $$$N$$$ players trying to avoid being caught by you. The game is played on a track of length $$$L$$$, where point 0 is the origin, and point $$$L$$$ is the destination. All $$$N$$$ players are initially positioned at point 0, while you are initially positioned at point $$$L$$$. The $$$i$$$-th player ($$$1 \leq i \leq N$$$) has a pace of $$$A_i$$$.

It is guaranteed that $$$1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq L$$$, and $$$A_{i+1} - A_i \geq A_{i+2} - A_{i+1}$$$ for $$$1 \leq i \leq N - 2$$$.

The players' goal is to reach the destination or avoid being caught by you, while your goal is to catch as many players as possible.

The game proceeds as follows:

  1. First Stage: You select a positive real number $$$U$$$, and each player $$$i$$$ walks a distance of $$$A_i \times U$$$.
    • If a player $$$i$$$ walks a distance $$$A_i \times U \geq L$$$, they have reached or exceeded the destination and are safe (i.e., they will not be caught by you).
  2. Second Stage: You shout "Catch!" and start running from point $$$L$$$ back to point 0 to catch the players. For each player $$$i$$$ who did not reach the destination (i.e., $$$A_i \times U \lt L$$$), they start running from point $$$A_i \times U$$$ back to point 0. Specifically,
    • Player $$$i$$$ starts running back to point 0 at a speed of $$$P$$$ units per second.
    • You start running from point $$$L$$$ to point 0 at a speed of $$$W$$$ units per second, where $$$P \lt W$$$.
    • If player $$$i$$$ reaches point 0 on or before the time you reach point 0, player $$$i$$$ is safe.

If a player has not walked a distance of at least $$$L$$$ in the first stage, and reached point 0 strictly after the time you reached point 0 in the second stage, that player is considered caught by you. (In other words, any player that is not safe is caught by you.)

Given $$$Q$$$ scenarios, where in the $$$i$$$-th scenario, you are provided with the integers $$$P$$$ and $$$W$$$, the players' running speed and your running speed in the second stage respectively, determine, with the optimal choice of the real number $$$U$$$ (such $$$U$$$ may not be unique), what is the maximum number of players that you can possibly catch.

Input

The first line contains three integers $$$N$$$, $$$L$$$, and $$$Q$$$ ($$$1 \leq N, Q \leq 2 \times 10^5$$$, $$$1 \leq L \leq 10^9$$$), representing the number of players (not counting you), the length of the track, and the number of scenarios respectively.

The second line contains $$$N$$$ integers $$$A_1, A_2, \ldots, A_N$$$, representing the pace of the players. You are reminded that $$$1 \leq A_1 \lt A_2 \lt \dots \lt A_N \leq L$$$ and $$$A_{i+1} - A_i \geq A_{i+2} - A_{i+1}$$$ for $$$1 \leq i \leq N - 2$$$.

The next $$$Q$$$ lines each contain two integers $$$P$$$ and $$$W$$$ ($$$1 \leq P \lt W \leq 10^9$$$), representing the parameters for a scenario.

Output

For each scenario, output one integer, the maximum number of players that you can possibly catch.

Example
Input
4 70 1
1 2 3 4
42 69
Output
2
Note

Sample 1:

By choosing 22 as $$$U$$$, we can catch player 2 and 3.