Point Weight Maintenance

You are given an infinite grid of integer coordinates. Initially, every point has a weight of \(0\). You need to perform \(m\) operations. There are two types of operations:

• Modification Operation: Given integers \(x, y, d, w\), for every point \((X, Y)\) satisfying \[ |X - x| < d \quad \text{and} \quad |Y - y| < d, \] increase its weight by \[ w \cdot (d - \max(|X - x|, |Y - y|)). \]
• Query Operation: Given integers \(x_1, x_2, y_1, y_2\), output the sum of weights of all points \((X, Y)\) satisfying \[ x_1 \le X \le x_2 \quad \text{and} \quad y_1 \le Y \le y_2. \] The answer should be given modulo \(2^{30}\).

inputFormat

The first line contains an integer (m) representing the number of operations. Each of the following (m) lines describes an operation. For a modification operation, the line begins with the integer 1 followed by four integers (x), (y), (d), (w). For a query operation, the line begins with the integer 2 followed by four integers (x_1), (x_2), (y_1), (y_2).

outputFormat

For each query operation, output the computed sum (modulo (2^{30})) on a separate line.

sample

3
1 0 0 2 1
2 -1 1 -1 1
2 0 0 0 0

10
2