radar

#include <bits/stdc++.h>
using namespace std;

const int DIMN = 100005;
const int DIMQ = 300005;

int v[DIMN], t[DIMN], indices[DIMN];
int st[DIMN], st_lim[DIMN], head = 0;
pair<int, int> qs[DIMQ];
int res[DIMQ];

bool is_better(int i, int j, int x) {
    return 1ULL * v[i] * (x - t[i]) <= 1ULL * v[j] * (x - t[j]);
}

int intersect(int i, int j) {
    return (1LL * v[j] * t[j] - 1LL * v[i] * t[i]) / (v[j] - v[i]);
}

int main() {
    int N, Q;
    assert(cin >> N >> Q);
    assert(1 <= N && N <= 100000 && 1 <= Q && Q <= 300000);
    for (int i = 1; i <= N; ++i) {
        assert(cin >> t[i] >> v[i]);
        assert(-1000000000 <= t[i] && t[i] <= 1000000000);
        assert(-1000000000 <= v[i] && v[i] <= 1000000000 && v[i] != 0);
        v[i] = (v[i] > 0 ? v[i] : -v[i]);
        indices[i] = i;
    }

    sort(indices + 1, indices + N + 1,
         [](int a, int b) { return t[a] < t[b]; });

    for (int i = 1; i <= Q; ++i) {
        assert(cin >> qs[i].first);
        assert(-1000000000 <= qs[i].first && qs[i].first <= 1000000000);
        qs[i].second = i;
        res[i] = -1;
    }

    sort(qs + 1, qs + Q + 1);

    int curr_q = 1;
    while (curr_q <= Q && qs[curr_q].first < t[indices[1]]) curr_q++;

    for (int i = 1; i <= N; ++i) {
        int idx = indices[i];
        while (head) {
            if (st_lim[head] < t[idx] || is_better(idx, st[head], st_lim[head]))
                head--;
            else
                break;
        }

        if (head == 0) {
            head = 1;
            st[1] = idx;
            st_lim[1] = 1000000000;
        } else {
            st[++head] = idx;
            st_lim[head] = intersect(idx, st[head - 1]);
        }

        while (curr_q <= Q &&
               (i == N || qs[curr_q].first < t[indices[i + 1]])) {
            int q = qs[curr_q].first;
            int lef = 1, rig = head;
            while (lef <= rig) {
                int mid = (lef + rig) / 2;
                if (st_lim[mid] < q)
                    rig = mid - 1;
                else
                    lef = mid + 1;
            }
            res[qs[curr_q].second] = st[rig];
            curr_q++;
        }
    }

    for (int i = 1; i <= Q; ++i) cout << res[i] << " \n"[i == Q];

    return 0;
}