Background

Ringo and Seiran are two Moon Rabbits who came from the Lunar Capital to Gensokyo. Since they landed in Gensokyo to investigate, they make a living there by opening a dango shop and selling dango.

To cope with the increasingly booming market, they bought a dango machine from Nitori Kawashiro, which can efficiently produce colorful dango. Dango of different colors have different prices. Because there are many customers every day and they buy a lot of dango, Seiran is always confused about how much a big pile of dango costs.

Seiran came to you and hopes you can tell her the total price of the dango sold each time.

Problem Description

Using the kappa's machine, Seiran can produce dango of many different colors. She found that for a dango with color $\bm c$, its price is $\bm c$. At the same time, the dango machine has a feature: the colors of the produced dango must form a consecutive segment of integers.

To store the produced dango, Seiran uses a structure similar to a "stack". At the start of the day, the stack is empty. Now there are $n$ operations of two types:

1. $\colorbox{f0f0f0}{\verb!1 l r!}$: The machine produces dango with colors $l,l+1,\cdots r-1,r$. Seiran pushes these dango onto the stack in order. That is, she adds $l,l+1,l+2,\cdots r-1,r$ to the top of the stack in sequence.
2. $\colorbox{f0f0f0}{\verb!2 k!}$: A customer wants to buy $k$ dango. Seiran will then pop $k$ dango from the top of the stack in order and sell them. It is guaranteed that $k$ is not greater than the number of dango currently in the stack.

Your task is: for each operation of type $2$, output the total price of these dango.

Input Format

The first line contains an integer $n$, the number of operations.
The next $n$ lines each describe one query. The first integer $op$ indicates the type of the query: if it is $1$, it is operation $1$; if it is $2$, it is operation $2$.

• For operation $1$, it is followed by two integers $l,r$, with the meaning as described above.
• For operation $2$, it is followed by one integer $k$, with the meaning as described above.

Output Format

Output several lines. For each operation of type $2$, output the sum of the prices of the sold dango.

6
1 1 14
2 5
1 14 19
1 1 9
2 8
2 10

60
44
124

Hint

Sample $2$ can be found in the attached files $\textbf{\textit{stack2.in}/\textit{stack2.out}}$.

Constraints

• For the first $30\%$ of the testdata, $n,l,r\le100$.
• For another $20\%$ of the testdata, $l=r$.
• For another $20\%$ of the testdata, $k\le 10$.
• For $100\%$ of the testdata, $1\le n\le 5\times 10^5$, $0\le l\le r \le 10^6$, $1\le k \le 10^{12}$.

Translated by ChatGPT 5