DS Team Selection

The 34th International Olympiad in Data Structures will take place soon. In order to qualify, you need to pass the team selection contest in your country. As a member of the Cat team, you have to solve this problem in the Cat Team Selection contest.

There are infinitely many points with integer coordinates on an infinite plane, each of which can be represented as $(x, y)$. Initially, the weights of all points are $0$. You need to perform $q$ operations, each of which takes the form:

• 1 $x$ $y$ $d$ $w$: For all points $(X,Y)$ that satisfy $|X-x| < d$ and $|Y-y| < d$, increase their point weights by $w \cdot (d - \max(|X-x|,|Y-y|))$.
• 2 $x_1$ $x_2$ $y_1$ $y_2$: Print the sum of the weights of points $(x,y)$ that satisfy $x_1 \le x \le x_2$ and $y_1 \le y \le y_2$. Since the sum can be large, output it modulo $2^{30}$.

The first line contains a single integer $m$ ($1 \le m \le 10^5$), the number of operations.

The next $m$ lines each contain several integers in one of the following forms:

• 1 $x$ $y$ $d$ $w$ ($1 \le x,y,d,w \le 10^8$)
• 2 $x_1$ $x_2$ $y_1$ $y_2$ ($1 \le x_1 \le x_2 \le 10^8$, $1 \le y_1 \le y_2 \le 10^8$)

For each operation of type 2, print a single line containing the requested sum of the weights. Print it modulo $2^{30}$.