#include <bits/stdc++.h>

#define FASTER() ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define ff first
#define ss second
#define pb push_back
#define all(a) a.begin(), a.end()
#define dbg(x) cerr<<" "<<#x<<" "<<x<<endl

typedef long long ll;

using namespace std;

const int maxn = 1e6 + 13;

struct point {
    int x, y;
};

bool cmp(point a, point b) {
    if(a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}

void print(vector <int> v) {
    for(auto a : v) cout << a << ' ';
    cout << endl;
}

struct segTree {
    int sz;
    vector <vector <int>> tree;

    segTree() {
       sz = 1;
       while(sz < maxn) {
           sz <<= 1;
       }
       tree.assign(2 * sz - 1, vector <int>());
    }

    void upd(int x, int lx, int rx, int i, vector <int> &v) {
        if(rx - lx == 1) {
            tree[x] = v;
            return;
        }
        int m = (lx + rx) >> 1;
        if(i < m) {
            upd(2 * x + 1, lx, m, i, v);
        } else {
            upd(2 * x + 2, m, rx, i, v);
        }
        tree[x] = tree[2 * x + 1];
        tree[x].insert(tree[x].end(), all(tree[2 * x + 2]));
        sort(all(tree[x]));
    }

    void upd(int i, vector <int> &v) {
        upd(0, 0, sz, i, v);
    }

    void print() {
        cout << "SEGTREE\n";
        for(int i = 0; i < 10; i++) {
            for(auto i : tree[i]) cout << i << " ";
            cout << endl;
        }
    }

    int get(int x, int lx, int rx, int l, int r, int ly, int ry) {
        if(l >= rx || r <= lx || x > tree.size()) {
            return 0;
        }
        if(lx >= l && rx <= l) {
            int f1 = lower_bound(all(tree[x]), ly) - tree[x].begin();
            int f2 = upper_bound(all(tree[x]), ry) - tree[x].begin();
            return f2 - f1;
        }
        int m = (lx + rx) >> 1;
        int f1 = get(2 * x + 1, lx, m, l, r, ly, ry);
        int f2 = get(2 * x + 2, m, rx, l, r, ly, ry);
        return f1 + f2;
    }

    int get(int l, int r, int ly, int ry) {
        return get(0, 0, sz, l, r, ly, ry);
    }
};

int main() {
    FASTER();
    int n, q;
    cin >> n >> q;
    segTree st;
    vector <point> p(n);
    vector <point> build(n);
    for(int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        p[i] = {x + y, x - y};
        build[i] = p[i];
    }

    sort(all(build), cmp);
    vector <int> temp;
    temp.pb(build[0].y);
    for(int i = 1; i < n; i++) {
        if(build[i - 1].x != build[i].x) {
            st.upd(build[i - 1].x, temp);
            temp = vector <int>{};
        }
        temp.pb(build[i].y);
    }
    if(temp.size() != 0) {
        st.upd(build[n - 1].x, temp);
    }

    for(int i = 0; i < q; i++) {
        int id, k;
        cin >> id >> k;
        id--;
        int x = p[id].x, y = p[id].y;
        int l = 0, r = (int)1e6 + 1;
        while(r - l > 1) { // ВОТ тут нужна помощь
            int m = (l + r) >> 1;
            int lx = min(m - x, m + x);
            int rx = max(m - x, m + x);
            int ly = min(m - y, m + y);
            int ry = min(m - y, m + y);
            if(st.get(lx, rx, ly, ry) <= k + 1) {
                l = m;
            } else {
                m = m;
            }
        }
        cout << l << endl;
    }
}