题目背景

Facer和教官关系很好，被教官任命为副教官。

题目描述

Facer 要训练一个 $N$ 个人的队伍。

每个人有一个智力值 $a_i$ 和一个体力值 $b_i$。

Facer 希望两个人组队，组队的两个人要尽量相似。

具体来说，编号为 $i$ 和 $j$ 的人的相似度为 $| a_i - a_j + b_j - b_i | + | a_i - a_j |$。相似度越小，表示越相似。

现在队伍里有 $N$ 个人，但是 Facer 想要进行 $M$ 次操作。有以下两种操作：

• 在队伍里加入一个人。
• 给出一个不在队伍里的人的数据，输出他和队伍里所有人的相似度中最低的相似度。注意，操作结束后，不要将这个人加入队伍，也不要将找到的人移出队伍。

输入格式

第一行，两个整数 $N,M$。

接下来 $N$ 行，第 $i$ 行两个数 $a_i,b_i$，表示队伍中第 $i$ 个人的智力值 $a_i$，体力值 $b_i$。

接下来 $M$ 行，每行一个操作。

• 1 a b：表示队伍中新加入了一个人，智力为 $a$，体力为 $b$。
• 2 a b：表示有一个不在队伍里的人的智力为 $a$，体力为 $b$，输出队伍里和这个人最相似的人与这个人的相似度。

输出格式

对于每个操作 2，输出一行，表示队伍里和这个人最相似的人与这个人的相似度。

3 3
1 7
2 -1
6 6
1 1 5
2 4 5
2 3 0

3
1

提示

对于 $40\%$ 的数据，$1 \le N,M \le 1000$。

对于 $100\%$ 的数据，$1 \le N,M \le {10}^5$。