Перестановка — это последовательность длины $$$n$$$ целых чисел от $$$1$$$ до $$$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]$$$, потому что первые два элемента совпадают, а третий элемент в первой перестановке меньше, чем во второй.
Следующая перестановка для перестановки $$$a$$$ длины $$$n$$$ — это лексикографически наименьшая перестановка $$$b$$$ длины $$$n$$$ лексикографически большая $$$a$$$. Например:
Вам дано число $$$n$$$ — длина изначальной перестановки. Изначальная перестановка имеет вид $$$a = [1, 2, \ldots, n]$$$. Другими словами $$$a[i] = i$$$ ($$$1 \le i \le n$$$).
Вам требуется обработать $$$q$$$ запросов двух типов.
Для каждого запроса $$$1$$$-го типа выведите искомую сумму.
В первой строке находится два целых числа $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) и $$$q$$$ ($$$1 \le q \le 2 \cdot 10^5$$$), где $$$n$$$ — длина исходной перестановки, а $$$q$$$ — количество запросов.
В следующих $$$q$$$ строках находится по одному запросу $$$1$$$ или $$$2$$$ типа. Запрос $$$1$$$ типа состоит из трёх целых чисел $$$1$$$, $$$l$$$ и $$$r$$$ $$$(1 \le l \le r \le n)$$$, запрос $$$2$$$ типа состоит из двух целых чисел $$$2$$$ и $$$x$$$ $$$(1 \le x \le 10^5)$$$.
Гарантируется, что все запросы $$$2$$$-го типа выполнить возможно.
Для каждого запроса $$$1$$$ типа выведите в отдельной строке одно целое число — искомую сумму.
4 4 1 2 4 2 3 1 1 2 1 3 4
9 4 6
Изначально перестановка имеет вид $$$[1, 2, 3, 4]$$$. Обработка запросов происходит следующим образом:
Название |
---|