题目描述

为了写论文，Alex 经常要整理大量的数据。这一次，Alex 面临一个严峻的考验：他需要实现一个数据结构来维护一个点集。

现在，二维平面上有 $N$ 个点。

Alex 需要实现以下三种操作：

1. 在点集里添加一个点；

2. 给出一个点，查询它到点集里所有点的曼哈顿距离的最小值；

3. 给出一个点，查询它到点集里所有点的曼哈顿距离的最大值。

两个点的曼哈顿距离定义为它们的横坐标差的绝对值与纵坐标差的绝对值的和。

这么困难的问题，Alex 当然不会做，只好再次请你帮忙了。

输入格式

第一行包含一个整数 $N$，表示点集最初的点数。

接下来 $N$ 行，每行两个整数，依次表示每个点的横坐标和纵坐标。

第 $N+2$ 行包含一个整数 $Q$，表示询问的数目。

接下来 $Q$ 行，每行三个整数，依次表示询问的类型，点的横坐标和纵坐标。$0$ 类型表示添加一个点，$1$ 类型表示查询到该点的曼哈顿距离的最小值，$2$ 类型表示查询最大值。

输出格式

输出若干行，依次表示每个查询操作的答案。

3
7 5
6 2
3 1
5
1 6 1
1 5 5
2 7 1
0 3 2
1 1 0

1
2
4
3

提示

对于前 $20 \%$ 的数据：$1\le N , Q\le 10^3$

对于前 $100 \%$ 的数据： $1\le N , Q \le 10^5$；

点的坐标是不超过 $10^9$ 的非负整数。