Point Weight Maintenance on Plane

You are given an infinite plane with integer lattice points. Each lattice point initially has weight \(0\). You need to perform \(m\) operations. There are two types of operations:

• Modification Operation: Given integers \(x, y, d, w\), for every lattice point \((X,Y)\) satisfying \[ |X-x| < d \quad \text{and} \quad |Y-y| < d, \] add a weight of \(w \cdot (d - \max(|X-x|,|Y-y|))\) to \((X,Y)\). (Note that the formula is in \(\LaTeX\) below: \(w\cdot (d-\max(|X-x|,|Y-y|))\).)
• Query Operation: Given integers \(x_1, x_2, y_1, y_2\), calculate the sum of weights of all lattice points \((X,Y)\) satisfying \[ x_1 \le X \le x_2, \quad y_1 \le Y \le y_2. \] Output the answer modulo \(2^{30}\) (i.e. modulo \(1073741824\)).

The operations are given in order and you should output the answer for each query operation.

inputFormat

The first line contains a single integer \(m\) — the number of operations.

Then \(m\) lines follow. Each line starts with an integer denoting the type of the operation.

• If the type is 1, then four integers follow: \(x\), \(y\), \(d\), and \(w\), describing a modification operation.
• If the type is 2, then four integers follow: \(x_1\), \(x_2\), \(y_1\), and \(y_2\), describing a query operation.

It is guaranteed that all numbers are integers and the operations are within reasonable limits so that a simulation solution will pass.

outputFormat

For each query operation, output its answer on a separate line. The answer is the sum of weights modulo \(2^{30}\) (i.e. modulo \(1073741824\)).

sample

4
1 0 0 2 1
2 -1 0 -1 0
1 1 1 2 2
2 0 2 0 2

5
25