Description

There are n gas stations on a highway, the i-th station is located at the x_i km of the highway, and you can get v_i unit of fuel (an unit of fuel can drive 1 km) if you stop and refuel at this station. Also, you can't stop at the i+1, i+2, ..., n-th station if you don't stop at the i-th station.

Now you are at the 0 km of the highway and your car has V unit of fuel. Besides, there are q places you want to visit, the i-th place is located at the p_i km of the highway.  Now, for each place, answer at least how many gas station you need to stop in order to reach the place.

Hint

Let T_i be the total unit of fuel you will have if you stop at 1, 2, ... i-th station. Then T_i = V + v₁ + v₂ + ... + v_i by definition, which can be computed in O(n) time using the following recurrence:

• T₀ = V (We define T₀ as the total unit of fuel if you don't stop at any station)
• T_i = T_i-1 + v_i, i = 1, 2, ..., n

Input

The first line contains two integers: n, q, V. 

For the next n lines, each line contains two integers: x_i, v_i (i = 1, 2, ..., n).

The last line contains q integers: p₁, p₂, ..., p_n.

Constrain

• 1 ≤ n, q ≤ 10⁵
• 1 ≤ x₁ < x₂ < ... < x_n ≤ 10⁹
• 1 ≤ v_i ≤ 10⁹, i = 1, 2, ..., n
• 1 ≤ p_i ≤ 10⁹, i = 1, 2, ..., q

Output

Output n lines, each line contains one integer: the answer of the i-th place. If it is impossible to reach the place, output -1.

 

Sample Input  Download

Sample Output  Download

Tags

Discuss