Mokia | cho.sh

Problem

The Moldovan mobile phone company Mokia has built a new customer location system. Like other location systems it answers a query of the form "Where is customer C?" with millimeter precision, and it also answers a query of the form "How many customers are inside a given rectangular area?".

The system treats the world as a square of size $W \times W$ that is divided into cells of size $1 \times 1$ . A cell is named by a pair of indices $(x, y)$ with $1 \le x, y \le W$ . Indexing starts at 1, so a table of size $4 \times 4$ has $1 \le x \le 4$ and $1 \le y \le 4$ .

Write a program that reports how many customers are inside a given rectangular area.

Input

Each instruction is on its own line and consists of one instruction integer followed by its parameters.

Instruction	Parameters	Meaning
0	W	Create a table of size $W \times W$ whose cells are all 0. This instruction is given once, as the first instruction.
1	x y A	Add $A$ to the number of customers in cell $(x, y)$ . $A$ is a positive integer.
2	X1 Y1 X2 Y2	Ask for the total number of customers in the cells $(x, y)$ with $X_1 \le x \le X_2$ and $Y_1 \le y \le Y_2$ .
3	none	Stop the program. This instruction is given once, as the last instruction.

A query counts only the add instructions that come before it in the input. Print nothing for a line whose instruction is not 2.

Output

For every instruction 2, print the requested number of customers on its own line, in the order the queries are given.

Constraints

$1 \le W \le 2\,000\,000$
$1 \le X_1 \le X_2 \le W$
$1 \le Y_1 \le Y_2 \le W$
$1 \le x, y \le W$
$0 < A \le 10\,000$
The number of instruction 1 lines is at most 160,000.
The number of instruction 2 lines is at most 10,000.