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

Update operation: Given $x, y, d, w$, increase the weight of all integer points $(X, Y)$ satisfying $X \ge x, Y \ge y, X+Y < x+y+d$ by $w$.

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 should be taken modulo $2^{30}$.

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

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

Examples

Input 1

8
1 8 10 2 2
2 1 5 3 4
1 8 5 7 10
1 1 5 4 10
1 4 2 1 1
1 8 5 8 9
2 2 6 2 9
1 8 9 2 3

Output 1

0
61

Subtasks

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

For $25\%$ of the data, $m, x_1, x_2, y_1, y_2, x, y, d, w \le 50$.

For another $25\%$ of the data, $m \le 2000$.

For another $25\%$ of the data, all update operations occur before all query operations.

For $100\%$ of the data, $1 \le m \le 2 \times 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$.