Problem: 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, …, n]. In other words, a[i] = i (1 ≤ i ≤ 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] + … + 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] → [1, 4, 2, 3] → [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 ≤ n ≤ 2 ⋅ 10^5) and q (1 ≤ q ≤ 2 ⋅ 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 ≤ l ≤ r ≤ n), the 2-nd type query consists of two integers 2 and x (1 ≤ x ≤ 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: 

  1. 2 + 3 + 4 = 9; 
  2. [1, 2, 3, 4] → [1, 2, 4, 3] → [1, 3, 2, 4] → [1, 3, 4, 2]; 
  3. 1 + 3 = 4; 
  4. 4 + 2 = 6 

Solution (in JAVA):

Solution:
import java.util.*;
import java.io.*;

public class Main {
    public static void main(String args[]) {new Main().run();}

    FastReader in = new FastReader();
    PrintWriter out = new PrintWriter(System.out);
    void run(){
        work();
        out.flush();
    }
    long mod=1000000007;
    long gcd(long a,long b) {
        return a==0?b:gcd(b%a,a);
    }
    void work() {
        int n=ni(),q=ni();
        if(n<=15){
            int cur=1;
            for(;q>0;q--){
                int t=ni();
                if(t==1){
                    int l=ni()-1,r=ni()-1;
                    long[] A=new long[n];
                    boolean[] vis=new boolean[n+1];
                    long remain=cur;
                    for(int c=n-1;c>=0;c--){
                        long b=count(c);
                        long v=remain/b+1;
                        if(remain%b==0)v--;
                        for(int i=1,cnt=0;i<=n&&cnt<v;i++){
                            if(!vis[i]){
                                cnt++;
                                if(cnt==v){
                                    vis[i]=true;
                                    A[n-1-c]=i;
                                }
                            }
                        }
                        remain-=(v-1)*b;
                    }

                    long ret=0;
                    for(int i=l;i<=r;i++){
                        ret+=A[i];
                    }
                    out.println(ret);
                }else{
                    cur+=ni();
                }
            }
        }else{
            int vv=1;
            long cur=1;
            long[] sum=new long[n+1];
            for(int i=1;i<=n;i++){
               sum[i]=i+sum[i-1];
            }
            int start=n-14;
            for(;q>0;q--){
                int t=ni();
                if(t==1){
                    int l=ni(),r=ni();
                    long[] A=new long[15];
                    boolean[] vis=new boolean[16];
                    long remain=cur;
                    for(int c=14;c>=0;c--){
                        long b=count(c);
                        long v=remain/b+1;
                        if(remain%b==0)v--;
                        for(int i=1,cnt=0;i<=15&&cnt<v;i++){
                            if(!vis[i]){
                                cnt++;
                                if(cnt==v){
                                    vis[i]=true;
                                    A[14-c]=i;
                                }
                            }
                        }
                        remain-=(v-1)*b;
                    }
                    if(start>r){
                        out.println(sum[r]-sum[l-1]);
                    }else if(l<start&&r>=start){
                        long ret=sum[start-1]-sum[l-1];
                        for(int i=start;i<=r;i++){
                            ret+=A[i-start]+n-15;
                        }
                        out.println(ret);
                    }else{
                        long ret=0;
                        for(int i=l;i<=r;i++){
                            ret+=A[i-start]+n-15;
                        }
                        out.println(ret);
                    }

                }else{
                    cur+=ni();
                }
            }
        }
    }

    long count(int c){
        long ret=1;
        for(int i=1;i<=c;i++){
            ret*=i;
        }
        return ret;
    }

    private ArrayList<long[]>[] ngw(int n, int m) {
        ArrayList<long[]>[] graph=(ArrayList<long[]>[])new ArrayList[n];
        for(int i=0;i<n;i++) {
            graph[i]=new ArrayList<>();
        }
        for(int i=1;i<=m;i++) {
            long s=in.nextLong()-1,e=in.nextLong()-1,w=in.nextLong();
            graph[(int)s].add(new long[] {e,w,i});
            graph[(int)e].add(new long[] {s,w});
        }
        return graph;
    }

    private int ni() {
        return in.nextInt();
    }

    private long nl() {
        return in.nextLong();
    }

    private String ns() {
        return in.next();
    }

    private long[] na(int n) {
        long[] A=new long[n];
        for(int i=0;i<n;i++) {
            A[i]=in.nextLong();
        }
        return A;
    }
    private int[] nia(int n) {
        int[] A=new int[n];
        for(int i=0;i<n;i++) {
            A[i]=in.nextInt();
        }
        return A;
    }
}

class FastReader
{
    BufferedReader br;
    StringTokenizer st;

    public FastReader()
    {
        br=new BufferedReader(new InputStreamReader(System.in));
    }


    public String next()
    {
        while(st==null || !st.hasMoreElements())//回车，空行情况
        {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (IOException e) {
                e.printStackTrace();
            }
        }
        return st.nextToken();
    }

    public int nextInt()
    {
        return Integer.parseInt(next());
    }

    public long nextLong()
    {
        return Long.parseLong(next());
    }
}