You are given an infinite 2D cardinal plane but this plane is not normal. And, you have many balls but the balls are not also normal. Upon each ball a coordinate value $(x, y)$ is written which means that you can place this ball on this point on the plane. For a given value of $k$, the power of a ball is defined as $f(k) = (|x + y| - k)^2$. Initially, you have $N$ containers and each container has a ball. Now, you will perform two types of queries that are defined as:

• $+ \ i \ x\ y$ : Put a ball in the $i^{th}$ container that has $(x, y)$ written upon it.
• $?\ l \ r \ k$ : Now choose $2$ balls from among all balls contained in the containers from $l$ to $r$ such that $|f_i(k) - f_j(k)|$ is maximum possible and print this value. Here $f_i(k)$ denotes the power of a ball chosen from the $i^{th}$ container for a particular value of $k$.

For each query of type $'?'$, find the maximum possible value of $|f_i(k) - f_j(k)|$ for the given $k$.

Note: It is not necessary to select two balls from different containers.

Input format

• The first line contains the number $N$ denotes the number of containers.
• Next $N$ lines contain two space-separated integers $x$ and $y$ denotes the coordinate written upon the $i^{th}$ ball.
• The next line contains $Q$ integers indicating the number of queries to be performed. 
• Next $Q$ lines contain the details of that query with the format as described in the problem statement.

Output format

For each query of type $'?'$, print the maximum possible value of $|f_i(k) - f_j(k)|$ for the given $k$ in the new line.

Constraints

$2 \leq N \leq 10^5$

$1 \leq Q \leq 2*10^5$

$1 \leq i \leq N$

$1 \leq l < r \leq N$

$-10^8 \leq x, y, k \leq 10^8$