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