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,|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,\;y_1\le Y\le y_2$. The answer is taken modulo $2^{30}$.

Input Format

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

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

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

Output Format

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

Idea: nzhtl1477, Solution: ccz181078, Code: ccz181078, Data: ccz181078.

Constraints: 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$, $1\le x,y,d,w\le {10}^8$.

Translated by ChatGPT 5