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\).