Weighted Point Operations

You are given a plane with integer coordinates, where each lattice point initially has a weight of 0. There are a total of $m$ operations. There are two types of operations:

1. Modification Operation: Given integers $x$, $y$, $d$, and $w$, increase the weight of every lattice point $(X,Y)$ satisfying

by $w$.

2. Query Operation: Given integers $x_1$, $x_2$, $y_1$, and $y_2$, compute the sum of weights of all lattice points $(X,Y)$ satisfying

and output the result modulo $2^{30}$.

All mathematical formulas are in LaTeX format. HTML tags may be used in this description.

inputFormat

The first line contains an integer $m$, the number of operations. Each of the following $m$ lines represents an operation. An operation starting with 1 indicates a modification operation and is followed by four integers: $x$, $y$, $d$, and $w$. An operation starting with 2 indicates a query operation and is followed by four integers: $x_1$, $x_2$, $y_1$, and $y_2$.

outputFormat

For each query operation, output a single line containing the computed sum modulo $2^{30}$.

sample

3
1 1 1 3 5
2 1 3 1 3
2 2 5 2 5

30
5