E. Длинная перестановка
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановка — это последовательность длины $$$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$$$. Например:

  • для перестановки $$$[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$$$-го типа выведите искомую сумму.

Входные данные

В первой строке находится два целых числа $$$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]$$$. Обработка запросов происходит следующим образом:

  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$$$