You are given \(N\) parabolas opening to the bottom and \(Q\) queries with an x-axis (horizontal) coordinate each. Your mission, should you choose to accept it, is to answer each query by printing the (one-based) index of the parabola whose value is the highest at the corresponding x-axis coordinate.

It is guaranteed that each parabola will be unique and none of the query points will be at the intersection of two parabolas whose values are the highest.

Input

The first line contains two integers, \(N\) and \(Q\).

The next \(N\) lines contains \(2\) integers \(b_i\) and \(c_i\) each, which correspond to the coefficients of parabolas in the form of \(y_i = -x^2 + b_ix + c_i\).

The next \(Q\) lines contain one integer \(x_i\) each, which correspond to x-axis coordinates where the parabolas should be evaluated.

• \(1 \le N, Q \le 10^5\)
• \(-10^9 \le b_i, c_i \le 10^9\)
• \(-10^9 \le x_i \le 10^9\)

Output

Print \(Q\) integers which correspond to the (one-based) index of the parabola that is the highest at the query point.

Example

Input 1:

2 3
-6 -4
3 5
-4
5
2

Output 1:

1
2
2

Explanation

Input 1:

The blue parabola corresponds to parabola \(1\) and the red parabola corresponds to parabola \(2\).