Long Permutation

A permutation is a sequence of integers from $$$1$$$ to $$$n$$$ of length $$$n$$$ containing each number exactly once. For example, $$$[1]$$$, $$$[4, 3, 5, 1, 2]$$$, $$$[3, 2, 1]$$$ — are permutations, and $$$[1, 1]$$$, $$$[4, 3, 1]$$$, $$$[2, 3, 4]$$$ — no.

Permutation $$$a$$$ is lexicographically smaller than permutation $$$b$$$ (they have the same length $$$n$$$), if in the first index $$$i$$$ in which they differ, $$$a[i] < b[i]$$$. For example, the permutation $$$[1, 3, 2, 4]$$$ is lexicographically smaller than the permutation $$$[1, 3, 4, 2]$$$, because the first two elements are equal, and the third element in the first permutation is smaller than in the second.

The next permutation for a permutation $$$a$$$ of length $$$n$$$ — is the lexicographically smallest permutation $$$b$$$ of length $$$n$$$ that lexicographically larger than $$$a$$$. For example:

• for permutation $$$[2, 1, 4, 3]$$$ the next permutation is $$$[2, 3, 1, 4]$$$;
• for permutation $$$[1, 2, 3]$$$ the next permutation is $$$[1, 3, 2]$$$;
• for permutation $$$[2, 1]$$$ next permutation does not exist.

You are given the number $$$n$$$ — the length of the initial permutation. The initial permutation has the form $$$a = [1, 2, \ldots, n]$$$. In other words, $$$a[i] = i$$$ ($$$1 \le i \le n$$$).

You need to process $$$q$$$ queries of two types:

• $$$1$$$ $$$l$$$ $$$r$$$: query for the sum of all elements on the segment $$$[l, r]$$$. More formally, you need to find $$$a[l] + a[l + 1] + \ldots + a[r]$$$.
• $$$2$$$ $$$x$$$: $$$x$$$ times replace the current permutation with the next permutation. For example, if $$$x=2$$$ and the current permutation has the form $$$[1, 3, 4, 2]$$$, then we should perform such a chain of replacements $$$[1, 3, 4, 2] \rightarrow [1, 4, 2, 3] \rightarrow [1, 4, 3, 2]$$$.

For each query of the $$$1$$$-st type output the required sum.