You need to maintain a set of integer points on a plane, each initially having a point weight of $0$. There are $m$ operations in total.

Update operation: Given $x, y, d, w$, increase the weight of every integer point $(X, Y)$ satisfying $|X-x| < d$ and $|Y-y| < d$ by $w \cdot (d - \max(|X-x|, |Y-y|))$.

Query operation: Given $x_1, x_2, y_1, y_2$, calculate the sum of weights of all integer points $(X, Y)$ satisfying $x_1 \le X \le x_2$ and $y_1 \le Y \le y_2$. The answer should be taken modulo $2^{30}$.

Input

Read data from standard input.

The first line contains an integer $m$. The next $m$ lines each describe an operation.

An update operation is represented as 1 x y d w.

A query operation is represented as 2 x1 x2 y1 y2.

Output

Output to standard output.

For each query operation, output a single line containing an integer representing the answer modulo $2^{30}$.

Examples

Input 1

5
1 3 4 5 1
2 1 4 3 5
1 2 4 2 2
2 4 5 3 5
1 4 4 4 8

Output 1

46
21

Subtasks

For $23\%$ of the data, $1 \le m \le 10^3$.

For $31\%$ of the data, $1 \le m \le 2 \times 10^4$.

For $39\%$ of the data, $1 \le m \le 4 \times 10^4$.

For $47\%$ of the data, $1 \le m \le 6 \times 10^4$.

For $55\%$ of the data, $1 \le m \le 8 \times 10^4$.

For another $15\%$ of the data, for any query operation, there is no update operation that occurs after that query operation.

For another $10\%$ of the data, $x_2 - x_1 \le 5$, $y_2 - y_1 \le 5$, and $d \le 5$.

For another $10\%$ of the data, $d \le 5$.

For $100\%$ of the data, $1 \le m \le 10^5$, $1 \le x_1 \le x_2 \le 10^8$, $1 \le y_1 \le y_2 \le 10^8$, and $1 \le x, y, d, w \le 10^8$.

Each category of data constitutes a subtask.