#include <cstdio>

#include <algorithm>

using namespace std;

const int N = , inf = 0x3f3f3f3f;

int n,q,D,rt,op,ans,b[];

struct nd {

    int l,r,d[],mn[],mx[];

    bool operator < (const nd &b) const {return d[D] < b.d[D];}

}t[N<<];

int rd() {

    int r = , f = , c = getchar();

    while(c < '' || c > '') {if(c == '-') f = -; c = getchar();}

    while(c >= '' && c <= '') r = r*+c-'', c = getchar();

    return r*f;

}

void pu(int x) {

    for(int i = ; i < ; i++) {

        t[x].mn[i] = min(t[x].mn[i],min(t[t[x].l].mn[i],t[t[x].r].mn[i]));

        t[x].mx[i] = max(t[x].mx[i],max(t[t[x].l].mx[i],t[t[x].r].mx[i]));

    }

}

int bd(int l, int r, int d) {

    if(l > r) return ;

    int m = (l+r)>>;

    D = d, nth_element(t+l, t+m, t+r+);

    for(int i = ; i < ; i++) t[m].mn[i] = t[m].mx[i] = t[m].d[i];

    t[m].l = bd(l, m-, d^), t[m].r = bd(m+, r, d^), pu(m);

    return m;

}

void in(int o, int d) {

    if(b[d] >= t[o].d[d]) {

        if(t[o].r) in(t[o].r, d^);

        else {

            t[o].r = ++n;

            for(int i = ; i < ; i++) t[n].mn[i] = t[n].mx[i] = t[n].d[i] = b[i];

        }

    } else {

        if(t[o].l) in(t[o].l, d^);

        else {

            t[o].l = ++n;

            for(int i = ; i < ; i++) t[n].mn[i] = t[n].mx[i] = t[n].d[i] = b[i];

        }

    }

    pu(o);

}

int gt(int o, int x, int y) {

    return max(,t[o].mn[]-x)+max(,t[o].mn[]-y)+max(,x-t[o].mx[])+max(,y-t[o].mx[]);

}

void qry(int o, int x, int y) {

    int ds = abs(t[o].d[]-x)+abs(t[o].d[]-y), dl = gt(t[o].l,x,y), dr = gt(t[o].r,x,y);

    ans = min(ans, ds);

    if(!t[o].l) dl = inf; if(!t[o].r) dr = inf;

    if(dl < dr) {

        if(dl < ans) qry(t[o].l,x,y);

        if(dr < ans) qry(t[o].r,x,y);

    } else {

        if(dr < ans) qry(t[o].r,x,y);

        if(dl < ans) qry(t[o].l,x,y);

    }

}

int main() {

    n = rd(), q = rd();

    for(int i = ; i <= n; i++) t[i].d[] = rd(), t[i].d[] = rd();

    t[].mn[] = t[].mn[] = inf, t[].mx[] = t[].mx[] = -inf, rt = bd(, n, );

    while(q--) {

        op = rd(), b[] = rd(), b[] = rd();

        if(op^) ans = inf, qry(rt,b[],b[]), printf("%d\n", ans); else in(rt,);

    }

    return ;

}