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] \lt 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.

Input

The first line contains two integers $n$ ($2 \le n \le 2 \cdot 10^5$) and $q$ ($1 \le q \le 2 \cdot 10^5$), where $n$ — the length of the initial permutation, and $q$ — the number of queries.

The next $q$ lines contain a single query of the $1$-st or $2$-nd type. The $1$-st type query consists of three integers $1$, $l$ and $r$ $(1 \le l \le r \le n)$, the $2$-nd type query consists of two integers $2$ and $x$ $(1 \le x \le 10^5)$.

It is guaranteed that all requests of the $2$-nd type are possible to process.

Output

For each query of the $1$-st type, output on a separate line one integer — the required sum.

Note

Initially, the permutation has the form $[1, 2, 3, 4]$. Queries processing is as follows:

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$