Problem Description

You need to maintain integer lattice points on a plane. Each point initially has weight $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$, query 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 is taken modulo $2^{30}$.

Input Format

Read input from standard input.

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

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

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

Output Format

Write output to standard output.

For each query operation, output one line containing an integer, which is the answer after taking modulo.

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

46
21

Hint

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

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

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

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

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

For another $15\%$ of the testdata, for any query operation, there does not exist an update operation that occurs after this query operation.

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

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

For $100\%$ of the testdata, $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 testdata forms a subtask.

Translated by ChatGPT 5