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