National Arena

Task

National Arena is the largest stadium in Romania, hosting the most important matches.

For the next match of the national football team, the organizers have decided to arrange a choreography in Stand 1. The choreography consists of spectators wearing t-shirts with numbers that, when viewed from a distance, will form something relevant to that match.

Stand 1 has $M$ columns, and each column contains $N$ seats. The columns are numbered from $1$ to $M$ from left to right, and the seats in a column are numbered from $1$ to $N$ from bottom to top.

Thus, the organizing team has to manage $Q$ operations of three types on the stand:

• $1$ $X$ $i$ - The lowest unoccupied seat in column $i$ is taken by a spectator wearing a t-shirt with number $X$;
• $2$ $idx$ $i$ - The spectator sitting on seat with number $idx$ in column $i$ leaves. Since people want a better view of the match, all spectators sitting in seats with higher numbers than $idx$ in the same column move down one seat.
• $3$ $st$ $dr$ $L$ $R$ - what is the sum of the numbers written on the t-shirts of spectators sitting on seats with numbers in the range $[st, dr]$, in columns within the range $[L, R]$?

Your task is to help the organizers effectively manage these $Q$ operations.

Input data

The first line contains the numbers $N$ ($1 \leq N \leq 10^5$), $M$ ($1 \leq M \leq 5 \cdot 10^4$), and $Q$ ($1 \leq Q \leq N$).

Each of the following $Q$ lines will describe an operation, as defined in the statement.

• For operations of type $1$: $0 \leq X \leq 10^6$ and $1 \leq i \leq M$.
• For operations of type $2$: $1 \leq idx \leq$ the number of people then seated in column $i$ and $1 \leq i \leq M$.
• For operations of type $3$: $1 \leq st \leq dr \leq N$ and $1 \leq L \leq R \leq M$.

Output data

The number of type $3$ operations will determine the number of lines in the output.

Each line will represent, in order, the answers to the type $3$ operations and will contain a single number.

Example

stdin

4 3 11
1 3 1
1 7 1
1 5 3
3 1 2 1 3
2 1 1
1 4 2
1 5 2
1 6 2
3 1 3 1 3
2 2 2
3 1 2 2 3

stdout

15
27
15