该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

给定一个初始为空的可重集，你需要维护 $Q$ 次操作，每次操作形如：

• 1 x：加入一个数 $x$，保证 $1 \le x \le n$。
• 2 l r：询问区间 $[l,r]$，对于所有 $d \in [l,r]$，不断释放如下法术：
  • 将集合中所有数减去 $d$，如果存在至少一个数 $\le 0$，则删除这些数后重新释放法术；否则结束释放。
  • 你需要求出总共 $r-l+1$ 个 $d$ 的释放次数之和。

输入格式

第一行两个整数 $n,Q$。

接下来 $Q$ 行，每行表示一个操作。

输出格式

对于每个 $2$ 操作，输出一行一个整数表示答案。

样例

样例输入

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

数据范围与约定

对于所有数据，有：

• $1 \le n\le 10^5$
• $1 \le x \le n$
• $1 \le Q \le 10^6$