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:
// Main Code at the Bottom
import java.util.*;
import java.io.*; 
public class Main{
	//Fast IO class
    static class FastReader {
        BufferedReader br; 
        StringTokenizer st; 
        public FastReader() {
        	boolean env=System.getProperty("ONLINE_JUDGE") != null;
        	if(!env) {
        		try {
					br=new BufferedReader(new FileReader("src\\input.txt"));
				} catch (FileNotFoundException e) {
					e.printStackTrace();
				}
        	}
        	else br = new BufferedReader(new InputStreamReader(System.in)); 
        } 
        String next() {
            while (st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine()); 
                } 
                catch (IOException  e) {
                    e.printStackTrace(); 
                } 
            } 
            return st.nextToken(); 
        } 
        int nextInt() {
            return Integer.parseInt(next()); 
        } 
        long nextLong() {
            return Long.parseLong(next()); 
        } 
        double nextDouble() {
            return Double.parseDouble(next()); 
        } 
        String nextLine() {
            String str = ""; 
            try {
                str = br.readLine(); 
            } 
            catch (IOException e) {
                e.printStackTrace(); 
            } 
            return str; 
        } 
    }     
    static long MOD=(long)1e9+7;
    //debug
    static void debug(Object... o) {
        System.out.println(Arrays.deepToString(o));
    }
    // Pair
    static class pair{
    	long x,y;
    	pair(long a,long b){
    		this.x=a;
    		this.y=b;
    	}
    	public boolean equals(Object obj) {
    		if(obj == null || obj.getClass()!= this.getClass()) return false;
            pair p = (pair) obj;
            return (this.x==p.x && this.y==p.y);
        }
    	public int hashCode() {
            return Objects.hash(x,y);
        }
    }
    static FastReader sc=new FastReader();
    static PrintWriter out=new PrintWriter(System.out);  
    //Global variables and functions
    static long fact[]=new long[16];
    static int perm[];
    static void kthPerm(long k,int n) {
    	ArrayList<Integer> arr=new ArrayList<>();
    	for(int i=1;i<=n;i++) arr.add(i);
    	for(int i=0;i<n;i++) {
    		long idx=k/fact[n-i-1];
    		perm[i]=arr.get((int)idx);
    		arr.remove((int)idx);
    		k-=idx*fact[n-i-1];
    	}
    }
    //Main function(The main code starts from here)
    public static void main (String[] args) throws java.lang.Exception {
    	fact[0]=1;
    	for(int i=1;i<=15;i++) {
    		fact[i]=i*fact[i-1];
    	}
    	int test=1;
    	//test=sc.nextInt();
    	while(test-->0) {
    		int n=sc.nextInt(),q=sc.nextInt();
    		perm=new int[Math.min(n, 15)];
    		for(int i=0;i<Math.min(n, 15);i++) perm[i]=i+1;
    		long k=0;
    		while(q-->0) {
    			int type=sc.nextInt();
    			if(type==2) {
    				k+=sc.nextInt();
    				kthPerm(k,Math.min(n, 15));
    				long val=Math.max(0, n-15);
    				for(int i=0;i<Math.min(n, 15);i++) perm[i]+=val;
    			}
    			else {
    				int l=sc.nextInt(),r=sc.nextInt();
    				long sum=0;
    				if(l<=n-15) {
    					long N=(Math.min(n-15, r)-l+1),a=l;
    					sum+=((2*a+N-1)*N)/2;
    				}
    				if(r>n-15) {
    					int N=r-Math.max((n-15),0);
    					int L=Math.max(l-(n-15)-1,0);
    					if(n<=15) L=l-1;
    					for(int i=L;i<N;i++) sum+=perm[i];
    				}
    				out.println(sum);
    			}
    		}
    	}	
        out.flush();
        out.close();
    }
}