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.