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.awt.*;
import java.io.*;
import java.util.*;
import java.util.List;

public class Coding {

    private static BufferedReader bi = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
    static long[] segmentTree = new long[4*200000 + 11];

    public static void main(String[] args) {
        try {
            run();
        } catch (Exception e) {
            e.printStackTrace();
        }
    }


    public static void run() throws Exception {
        InputModule inp = new InputModule();
        OutputModule out = new OutputModule();
        long[] fact = new long[15];
        fact[0] = 1;
        for(int i=1;i<=14;++i) fact[i] = fact[i-1]*i;
        int t = 1;
        while (t > 0) {
            int[] ints = inp.cinIntArray(2);
            int n = ints[0];
            int q = ints[1];
            int[] ar = new int[n];
            for(int i=0;i<n;++i) ar[i] = i+1;
            buildTree(0, 0, n-1, ar);
            long sum = 0;
            HashMap<Integer, Integer> mp = new HashMap<>();
            for(int i=0;i<n;++i) {
                mp.put(ar[i], i);
            }
            while (q>0) {
                ints = inp.cinIntArray();
                //System.out.println(ints.length +  " " + ints[0]);
                if (ints[0] == 1) {
                    if (sum>0) {
                        long curr = 0;
                        int start = (n - Math.min(15, n));
                        int maxm = ar[n-1];
                        for (int i = n - 2; i >= 0; --i) {
                            int cn = 0;
                            List<Integer> grt = new ArrayList<>();
                            for (int j = i + 1; j <= n - 1; ++j) if (ar[j] > ar[i]) {
                                cn++;
                                grt.add(ar[j]);
                            }
                            if ((curr + (fact[n - 1 - i] * cn)) >= sum) {
                                //System.out.println("curr is " + curr + " at index " + i);
                                sum -= curr;
                                int ct = 0;
                                while (sum - fact[n - 1 - i] > 0) {
                                    ct++;
                                    sum -= fact[n-1-i];
                                }
                                //System.out.println("ct is  " + ct);
                                Collections.sort(grt);
                                ar[mp.get(grt.get(ct))] = ar[i];
                                mp.put(ar[i], mp.get(grt.get(ct)));
                                ar[i] = grt.get(ct);
                                //out.printIntArray(ar);
                                mp.put(grt.get(ct), i);
                                updateTree(0, 0, n-1, i, ar);
                                List<Integer> cur = new ArrayList<>();
                                for(int j=i+1;j<=n-1;++j) cur.add(ar[j]);
                                Collections.sort(cur);
                                for(int j=i+1;j<=n-1;++j) {
                                    ar[j] = cur.get(j-i-1);
                                    mp.put(ar[j], j);
                                    updateTree(0, 0, n-1, j, ar);
                                }
                                //out.printIntArray(ar);
                                start = i+1;
                                break;
                            } else {
                                curr+=(fact[n - 1 - i] * cn);
                            }
                            maxm = Math.max(maxm, ar[i]);
                        }
                        //System.out.println("Now start is " + start);
                        while (start<=n-1) {
                            int ct = start;
                            while (sum-fact[n-1-start]>0) {
                                sum-=fact[n-1-start];
                                ct++;
                            }
                            if (ct!=start) {
                                int save = ar[ct];
                                for(int i = ct;i>=start+1;--i) {
                                    ar[i] = ar[i-1];
                                    mp.put(ar[i-1], i);
                                    updateTree(0, 0, n-1, i, ar);
                                }
                                ar[start] = save;
                                mp.put(save, start);
                                updateTree(0, 0, n-1, start, ar);
                            }
                            start++;
                        }
                        //out.printIntArray(ar);
                        sum = 0;
                    }
                    out.printLong(query(0, 0, n-1, ints[1]-1, ints[2]-1));
                } else {
                    sum+=ints[1];
                }
                q--;
            }
            t--;
        }
    }


    private static void buildTree(int idx, int l, int r, int[] ar) {
        if (l==r) {
            segmentTree[idx] = ar[l];
        } else {
            int mi = (l+r)/2;
            buildTree(2*idx+1, l, mi, ar);
            buildTree(2*idx+2, mi+1, r, ar);
            segmentTree[idx] = segmentTree[2*idx+1] + segmentTree[2*idx+2];
        }
    }

    private static void updateTree(int idx, int l, int r, int id, int[] ar) {
        if (l==r) {
            segmentTree[idx] = ar[l];
        } else {
            int mi = (l+r)/2;
            if (id<=mi) {
                updateTree(2 * idx + 1, l, mi, id, ar);
            } else {
                updateTree(2 * idx + 2, mi + 1, r, id, ar);
            }
            segmentTree[idx] = segmentTree[2*idx+1] + segmentTree[2*idx+2];
        }
    }

    private static long query(int idx, int l, int r, int ql, int qr) {
        if (ql>r||qr<l) {
            return 0;
        } else if (ql<=l && qr>=r) {
            return segmentTree[idx];
        } else {
            int mid = (l+r)/2;
            return query(2*idx+1, l, mid, ql, qr) + query(2*idx+2, mid+1, r, ql, qr);
        }
    }

    private static class InputModule {
        private int cinInt() throws Exception {
            return Integer.parseInt(bi.readLine().split(" ")[0].trim());
        }

        private long cinLong() throws Exception {
            return Long.parseLong(bi.readLine().split(" ")[0].trim());
        }

        private Double cinDouble() throws Exception {
            return Double.parseDouble(bi.readLine().split(" ")[0].trim());
        }

        private String cinString() throws Exception {
            return bi.readLine();
        }

        private int[] cinIntArray(int n) throws Exception {
            String input = bi.readLine();
            String[] values = input.split(" ");
            int[] ar = new int[n];
            for (int i = 0; i < n; ++i) {
              ar[i] = Integer.parseInt(values[i]);
            }
            return ar;
        }

        private int[] cinIntArray() throws Exception {
            String input = bi.readLine();
            String[] values = input.split(" ");
            int[] ar = new int[values.length];
            for (int i = 0; i < values.length; ++i) {
                ar[i] = Integer.parseInt(values[i]);
            }
            return ar;
        }

        private long[] cinLongArray(int n) throws Exception {
            String input = bi.readLine();
            String[] values = input.split(" ");
            long[] ar = new long[n];
            for (int i = 0; i < n; ++i) {
                ar[i] = Long.parseLong(values[i]);
            }
            return ar;
        }

        private String[] cinStringArray(int n) throws Exception {
            return bi.readLine().split(" ");
        }
    }

    private static class OutputModule {
        private void printInt(int ans) throws Exception {
            writer.append(ans + "\n");
            writer.flush();
        }

        private void printLong(long ans) throws Exception {
            writer.append(ans + "\n");
            writer.flush();
        }

        private void printDouble(Double ans) throws Exception {
            writer.append(String.format("%.10f", ans));
            writer.append("\n");
            writer.flush();
        }

        private void printString(String ans) throws Exception {
            writer.append(ans + "\n");
            writer.flush();
        }

        private void printIntArray(int[] ans) throws Exception {
            for (int i = 0; i < ans.length; ++i) {
                writer.append(ans[i] + " ");
            }
            writer.append("\n");
            writer.flush();
        }

        private void printLongArray(long[] ans) throws Exception {
            for (int i = 0; i < ans.length; ++i) {
                writer.append(ans[i] + " ");
            }
            writer.append("\n");
            writer.flush();
        }

        private void printIntMatrix(int[][] mat, int n, int m) throws Exception {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    writer.append(mat[i][j] + " ");
                }
                writer.append("\n");
            }
            writer.flush();
        }

        private void printLongMatrix(long[][] mat, int n, int m) throws Exception {
            for (int i = 0; i < n; ++i) {
                for (int j = 0; j < m; ++j) {
                    writer.append(mat[i][j] + " ");
                }
                writer.append("\n");
            }
            writer.flush();
        }

        private void printPoint(Point p) throws Exception {
            writer.append(p.x + " " + p.y + "\n");
            writer.flush();
        }

        private void printPoints(List<Point> p) throws Exception {
            for (Point pp : p) {
                writer.append(pp.x + " " + pp.y + "\n");
            }
            writer.flush();
        }
    }
}