P2794 Facer和教官

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`，输出一行，表示队伍里和这个人最相似的人与这个人的相似度。

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