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.


-----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.


-----Example-----
Input
4 4
1 2 4
2 3
1 1 2
1 3 4

Output
9
4
6



-----Note-----

Initially, the permutation has the form $[1, 2, 3, 4]$. Queries processing is as follows:   $2 + 3 + 4 = 9$;  $[1, 2, 3, 4] \rightarrow [1, 2, 4, 3] \rightarrow [1, 3, 2, 4] \rightarrow [1, 3, 4, 2]$;  $1 + 3 = 4$;  $4 + 2 = 6$

Difficulty: interview

Starter code:

Solutions:
from math import *

n, q = list(map(int, input().split()))
after = min(15, n)
before = n - after


def calc(left, right):
    return right * (right + 1) // 2 - left * (left - 1) // 2


def perm(i):
    unused = [i + 1 for i in range(after)]
    arr = []
    for j in reversed(list(range(after))):
        cur = i // factorial(j)
        arr.append(unused[cur])
        del unused[cur]
        i -= cur * factorial(j)
    return arr


p = perm(0)
x = 0

for _ in range(q):
    line = list(map(int, input().split()))

    if len(line) == 3:
        # type 1
        l = line[1]
        r = line[2]
        res = 0
        if l <= before:
            if r <= before:
                res += r * (r + 1) // 2
            else:
                res += before * (before + 1) // 2
            res -= l * (l - 1) // 2
            l = before + 1
        if r > before:
            res += sum(p[l-1-before:r-before]) + (r-l+1) * before

        print(res)
    else:
        # type 2
        x += line[1]
        p = perm(x)


import sys
input = sys.stdin.readline

n,q=list(map(int,input().split()))
X=list(range(1,n+1))

S=[0]
for x in X:
    S.append(S[-1]+x)

FACT=[1,1]
for i in range(2,16):
    FACT.append(FACT[-1]*i)

A=X[-15:]
LEN=len(A)
def calc(x):
    AA=[a for a in A]
    ANS=[]

    for i in range(LEN,0,-1):
        q=x//FACT[i-1]
        x-=q*FACT[i-1]

        ANS.append(AA.pop(q))

        #print(q,x,AA,ANS)
    
    return ANS

NOW=0
for queries in range(q):
    Q=list(map(int,input().split()))

    if Q[0]==2:
        NOW+=Q[1]
        continue
    
    l,r=Q[1],Q[2]

    if r<=n-LEN:
        print(S[r]-S[l-1])
        continue

    elif l<=n-LEN:
        ANS=S[-LEN-1]-S[l-1]
        l=0
        r-=n-LEN+1
    else:
        ANS=0
        l-=n-LEN+1
        r-=n-LEN+1

    NOWA=calc(NOW)

    print(ANS+sum(NOWA[l:r+1]))


n, Q = list(map(int, input().split()))
cnt = 1
F = [1]
for i in range(1, 17):
    F.append(F[-1] * i)
st = max(0, n - 15)
a = [0] * (n + 1)
vs = [0] * (n + 1)
for i in range(1, n + 1):
    a[i] = a[i - 1] + i
for _ in range(Q):
    q = list(map(int, input().split()))
    if q[0] == 1:
        l, r = q[1], q[2]
        print(a[r] - a[l - 1])
        continue
    x = q[1]
    cnt += x
    hav = cnt
    for i in range(st, n + 1):
        vs[i] = 0
    for i in range(st, n):
        tmp = 0
        for j in range(st, n + 1):
            if not vs[j]:
                tmp += F[n - i]
                if tmp >= hav:
                    hav -= tmp - F[n - i]
                    a[i] = a[i - 1] + j
                    vs[j] = 1
                    break
    for i in range(st, n + 1):
        if not vs[i]:
            a[n] = a[n - 1] + i
    



import sys
input=sys.stdin.readline

fact=[1]
for i in range(1,15+1):
    fact.append(fact[-1]*i)

def generate_perm(n,m):
    ret=[]
    if n<=15:
        cand=[i+1 for i in range(n)]
    else:
        cand=[i+1 for i in range(n-15,n)]
    for i in range(1,min(15+1,n+1)):
        pos=m//fact[min(15,n)-i]
        m%=fact[min(15,n)-i]
        ret.append(cand[pos])
        del cand[pos]
    return ret

n,q=map(int,input().split())
ids=0
if n<=15:
    perm=[i+1 for i in range(n)]
else:
    perm=[i+1 for i in range(n-15,n)]
for _ in range(q):
    query=list(map(int,input().split()))
    if query[0]==1:
        l,r=query[1],query[2]
        if n<=15:
            print(sum(perm[l-1:r]))
        else:
            if l<=n-15:
                if r<=n-15:
                    print((r*(r+1))//2-(l*(l-1))//2)
                else:
                    print((n-15)*(n-14))//2-(l*(l-1))//2+sum(perm[0:r-(n-15)])
            else:
                print(sum(perm[l-1-(n-15):r-(n-15)]))
    elif query[0]==2:
        ids+=query[1]
        perm=generate_perm(n,ids)

# No need to use segment Tree because apart from the last 14 numbers, nothing will change since 14! > 2*pow(10, 10)

def modify(rest):
	for i in range(len(rest)):
		prefix[-len(rest)+i] = prefix[-len(rest)+(i-1)] + rest[i]
	# print("prefix", prefix)


def next_perm_direct(permc):	# Gets the next permc lexographically bigger permutation
	rest = [x for x in range(max(1, n-14), n+1)]

	temp = 1
	for i in range(1, len(rest)):
		temp = temp*i

	for i in range(len(rest)-1):
		if permc >= temp:
			change = permc//temp
			rest[i], rest[i+change] = rest[i+change], rest[i]
			rest = rest[:i+1] + list(sorted(rest[i+1:]))
			permc = permc%temp
		temp = temp//(len(rest)-1-i)
	# print("rest", rest)
	modify(rest)


n, q = list(map(int, input().split()))
prefix = [0 for i in range(n+1)]
for i in range(1, n+1):
	prefix[i] = prefix[i-1]+i
# print(prefix)

permc = 0
for _ in range(q):
	quer = list(map(int, input().split()))
	if len(quer) == 2:
		permc += quer[1]
		next_perm_direct(permc)
	else:
		l, r = quer[1], quer[2]
		print(prefix[r]-prefix[l-1])