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\)