Description

The mobile phone company Mokia in Morvado has designed a new user localization system. Like other localization systems, it can quickly answer any question of the form “Where is user C?”, accurate to the millimeter. But its truly high-tech feature is that it can answer questions like “How many users are there in a given area?”.

In this localization system, the world is considered a $w\times w$ square region, composed of $1\times 1$ cells. Each cell has a coordinate $(x, y)$, $1\leq x,y\leq w$. Coordinates are 1-indexed. For a $4\times 4$ square, we have $1\leq x\leq 4$, $1\leq y\leq 4$ (see the figure).

Please help Mokia write a program to compute how many users are in a rectangular region.

Input Format

There are three types of commands with the following meanings:

The input consists of multiple lines. Each line contains several integers representing one command.

Output Format

For every command $2$, output one integer on a separate line: the number of users currently in the queried rectangle.

0 4
1 2 3 3
2 1 1 3 3
1 2 2 2
2 2 2 3 4
3

3
5

Hint

Constraints

For $100\%$ of the testdata, it is guaranteed that:

• $1\leq w\leq 2\times 10 ^ 6$.
• $1\leq x_1\leq x_2\leq w$, $1\leq y_1\leq y_2\leq w$, $1\leq x,y\leq w$, $0<a\leq 10000$.
• The number of command $1$ does not exceed $160000$.
• The number of command $2$ does not exceed $10000$.

Translated by ChatGPT 5