Background

I kept the...
p...promise.

【You worked really hard.】
I worked very, very hard...

【Although you said that yesterday too...】
【Welcome back, Chtholly.】

I am back...
I finally said it...
【Yes, I finally heard it.】
Red hair, is it strange?
【It is a very pretty color, and it suits you well.】
Really...
I... I am fine now.
【Really? Is your health okay?】
【If you are forcing yourself, I will not forgive you.】
It is okay. There is still a lot of work to do, like cooking and washing clothes.
【Do not push yourself too hard.】

Hmph, just be mentally prepared and wait.

Background

I kept the...
p...promise.

【You worked really hard.】
I worked very, very hard...

【Although you said that yesterday too...】
【Welcome back, Chtholly.】

I am back...
I finally said it...
【Yes, I finally heard it.】
Red hair, is it strange?
【It is a very pretty color, and it suits you well.】
Really...
I... I am fine now.
【Really? Is your health okay?】
【If you are forcing yourself, I will not forgive you.】
It is okay. There is still a lot of work to do, like cooking and washing clothes.
【Do not push yourself too hard.】

Hmph, just be mentally prepared and wait.

Problem Description

When Chtholly plays Hearthstone, he can never pull off a textbook-quality Defile, so he rewrote a new “Hearthstone”, and changed the description of Defile to:

“Randomly choose an integer uniformly from $[L, R]$ as the damage value $d$, deal $d$ damage to all minions. If any minion dies, cast this spell again, but the damage value is not rerolled. If no minion dies, stop casting.”

He also removed the limit on the number of minions on the board and the limit that Defile can trigger at most 14 times.

Chtholly does not know how this modified Defile works, so he plans to run some tests. There will be $m$ operations of the following types:

1. Add a minion with health $h$ onto the board. Here, a minion’s health will not exceed $n$.
2. Given $L, R$, ask for the expected number of times Defile triggers.

Chtholly can only do operation 1, so he leaves operation 2 to you.

Input Format

The first line contains two integers $n$ and $m$, separated by spaces.

The next $m$ lines each describe one operation. Operation 1 is written as $1\;h$, and operation 2 is written as $2\;L\;R$.

Output Format

To avoid printing decimals, for each operation 2, output an integer equal to the expected value multiplied by $(R - L + 1)$.

10 10
2 7 9
1 6
2 7 10
1 10
1 7
2 7 10
1 7
1 1
2 6 7
1 4

3
8
11
6

Hint

Idea: oscar, Solution: ccz181078, Code: ccz181078, Data: nzhtl1477.

For $100\%$ of the testdata, it is guaranteed that: $1\le n\le 10^5$, in each type 1 operation $1\le h\le n$, and in each type 2 operation $1\le L\le R\le n$. $1\le m\le 10^6$. All values above are integers.

Translated by ChatGPT 5