1
#include <cstdio>
2
#include <cstring>
3
#include <algorithm>
4
#include <cmath>
5

6
using namespace std;
7

8
inline int read()
9
{
10
    int x=0,f=1;char ch=getchar();
11
    while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
12
    while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
13
    return x*f;
14
}
15

16
const int INF = 0x3f3f3f3f;
17
const double alpha = 0.756;
18
const int MAXN = 5e5 + 5;
19

20
int now;
21

22
struct Point
23
{
24
    int d[2];
25
    int &operator[](const int &x)
26
    {
27
        return d[x];
28
    }
29
    inline bool operator < (const Point &x) const
30
    {
31
        return d[now] == x.d[now] ? d[now ^ 1] < x.d[now ^ 1] : d[now] < x.d[now];
32
    }
33
}a[MAXN], cur;
34

35
#define dis(_, __) (\
36
    int(abs(_[0] - __[0]) + abs(_[1] - __[1]))\
37
)
38

39
#define size(_) ((_) ? (_)->s : 0)
40

41
struct Node
42
{
43
    Node *ch[2];
44
    Point v;
45
    int s, d;
46
    int Max[2], Min[2];
47
    Node(Point x)
48
    {
49
        ch[0] = ch[1] = NULL;
50
        v = x;
51
        s = 1, d = now;
52
        Max[0] = Min[0] = x[0];
53
        Max[1] = Min[1] = x[1];
54
    }
55
    Node(){;}
56
    inline bool operator < (const Node &x) const
57
    {
58
        return v < x.v;
59
    }
60
    bool IsBad()
61
    {
62
        return ((size(ch[0]) > s * alpha) || (size(ch[1]) > s * alpha));
63
    }
64
    void Pushup(Node *x)
65
    {
66
        if (!x) return;
67
        for (int i = 0; i <= 1; i++) Min[i] = min(Min[i], x->Min[i]);
68
        for (int i = 0; i <= 1; i++) Max[i] = max(Max[i], x->Max[i]);
69
        s += x->s;
70
    }
71
    int min_dis()
72
    {
73
        int ans = 0;
74
        ans += max(Min[0] - cur[0], 0) + max(cur[0] - Max[0], 0);
75
        ans += max(Min[1] - cur[1], 0) + max(cur[1] - Max[1], 0);
76
        return ans;
77
    }
78
}*root;
79

80
inline void Build(Node *&rt, int l, int r, int d = 0)
81
{
82
    if (l > r) return;
83
    int mid = l + r >> 1;
84
    now = d;
85
    nth_element(a + l, a + mid, a + r + 1);
86
    rt = new Node(a[mid]);
87
    Build(rt->ch[0], l, mid - 1, d ^ 1);
88
    Build(rt->ch[1], mid + 1, r, d ^ 1);
89
    rt->s = 1;
90
    rt->Pushup(rt->ch[0]);
91
    rt->Pushup(rt->ch[1]);
92
}
93

94
Node **res;
95

96
inline void Insert(Node *&rt)
97
{
98
    if (rt == NULL)
99
    {
100
        rt = new Node(cur);
101
        res = NULL;
102
        return;
103
    }
104
    now = rt->d;
105
    if (cur < rt->v) Insert(rt->ch[0]);
106
    else Insert(rt->ch[1]);
107
    rt->s = 1;
108
    rt->Pushup(rt->ch[0]);
109
    rt->Pushup(rt->ch[1]);
110
    if (rt->IsBad()) res = &rt;
111
}
112

113

114
inline void Insert(Point x)
115
{
116
    cur = x;
117
    Insert(root);
118
}
119

120
int Min_ans;
121

122
inline void Query(Node *rt)
123
{
124
    if (!rt) return;
125
    // if (rt->min_dis() > Min_ans) return;
126
    Min_ans = min(Min_ans, dis(rt->v, cur));
127
    int dis_l = rt->ch[0] ? rt->ch[0]->min_dis() : INF;
128
    int dis_r = rt->ch[1] ? rt->ch[1]->min_dis() : INF;
129
    if (dis_l < dis_r)
130
    {
131
        Query(rt->ch[0]);
132
        if (dis_r < Min_ans) Query(rt->ch[1]);
133
    }
134
    else
135
    {
136
        Query(rt->ch[1]);
137
        if (dis_l < Min_ans) Query(rt->ch[0]);
138
    }
139
}
140

141
inline int Query(Point x)
142
{
143
    cur = x;
144
    Min_ans = INF;
145
    Query(root);
146
    return Min_ans;
147
}
148

149
int main()
150
{
151
    // freopen("1.in", "r", stdin);
152
    // freopen("2.out", "w", stdout);
153
    int n, m;
154
    n = read(), m = read();
155
    for (int i = 1; i <= n; i++)
156
        a[i][0] = read(), a[i][1] = read();
157
    Build(root, 1, n);
158
    Point x;
159
    while (m--)
160
    {
161
        int t = read();
162
        if (t == 1)
163
        {
164
            x[0] = read(), x[1] = read();
165
            Insert(x);
166
        }
167
        else
168
        {
169
            x[0] = read(), x[1] = read();
170
            printf ("%d\n", Query(x));
171
        }
172
    }
173
}