Description

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

现在，二维平面上有N个点。Alex 需要实现以下三种操作：

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

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

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

两个点的曼哈顿距离定义为它们的横坐标差的绝对值与纵坐标差的绝对值的和。这么困难的问题，Alex当然不会做，只好再次请你帮忙了。

Format

Input

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

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

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

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

1 ≤ N, Q ≤ 100,000，点的坐标是不超过10^9的非负整数

Output

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

Samples

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