排列是从 $$$1$$$ 到 $$$n$$$ 的整数序列,长度为 $$$n$$$,每个数字恰好包含一次。例如,$$$[1]$$$、$$$[4, 3, 5, 1, 2]$$$、$$$[3, 2, 1]$$$ — 是排列,$$$[1, 1]$$$、$$$[4, 3, 1]$$$、$$$[2, 3, 4]$$$ — 否。
排列 $$$a$$$ 按字典顺序小于排列 $$$b$$$ (它们具有相同的长度 $$$n$$$),如果在它们不同的第一个索引 $$$i$$$ 中,则 $$$a[i] < b[i]$$$。例如,排列 $$$[1, 3, 2, 4]$$$ 按字典顺序小于排列 $$$[1, 3, 4, 2]$$$,因为前两个元素相等,并且第一个排列中的第三个元素小于第二个排列中的第三个元素。
长度为 $$$n$$$ 的排列 $$$a$$$ 的下一个排列 - 是长度为 $$$n$$$ 的字典顺序最小排列 $$$b$$$,按字典顺序大于 $$$a$$$。例如:
- 对于排列 $$$[2, 1, 4, 3]$$$,下一个排列是 $$$[2, 3, 1, 4]$$$;
- 对于排列 $$$[1, 2, 3]$$$,下一个排列是 $$$[1, 3, 2]$$$;
- 对于排列 $$$[2, 1]$$$ 下一个排列不存在。
您将得到数字 $$$n$$$ — 初始排列的长度。初始排列的形式为 $$$a = [1, 2, \ldots, n]$$$。换句话说,$$$a[i] = i$$$ ($$$1 \le i \le n$$$)。
您需要处理两种类型的 $$$q$$$ 查询:
- $$$1$$$ $$$l$$$ $$$r$$$:查询$$$[l, r]$$$段上所有元素的总和。更正式地说,您需要找到 $$$a[l] + a[l + 1] + \ldots + a[r]$$$。
- $$$2$$$ $$$x$$$:$$$x$$$ 次用下一个排列替换当前排列。例如,如果 $$$x=2$$$ 并且当前排列的形式为 $$$[1, 3, 4, 2]$$$,那么我们应该执行这样的替换链 $$$[1, 3, 4, 2] \rightarrow [1, 4, 2, 3] \rightarrow [1, 4, 3, 2]$$$。
对于 $$$1$$$-st 类型的每个查询,输出所需的总和。
输入
第一行包含两个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) 和 $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$),其中 $$$n$$$ — 初始排列的长度,$$$q$$$ — 查询数。
接下来的 $$$q$$$ 行包含 $$$1$$$-st 或 $$$2$$$-nd 类型的单个查询。 $$$1$$$-st 类型查询由三个整数 $$$1$$$、$$$l$$$ 和 $$$r$$$ $$$(1 \le l \le r \le n)$$$ 组成,$$$2$$$-nd 类型查询由两个整数 $$$2$$$ 和 $$$x$$$ $$$(1 \le x \le 10^5)$$$ 组成。
保证$$$2$$$-nd 类型的所有请求都可以处理。
输出
对于 $$$1$$$-st 类型的每个查询,在单独的行上输出一个整数 - 所需的总和。
示例
输入 #1
4 4 1 2 4 2 3 1 1 2 1 3 4
输出 #1
9 4 6
注意
最初,排列的形式为 $$$[1, 2, 3, 4]$$$。查询处理如下:
1. $$$2 + 3 + 4 = 9$$$;
2. $$$[1, 2, 3, 4] \rightarrow [1, 2, 4, 3] \rightarrow [1, 3, 2, 4] \rightarrow [1, 3, 4, 2]$$$;
3. $$$1 + 3 = 4$$$;
4. $$$4 + 2 = 6$$$