B'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: 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 <= i <= n ). You need to process q queries of two types: For each query of the 1 -st type output the required sum. The first line contains two integers n ( 2 <= n <= 2 cdot 10^5 ) and q ( 1 <= q <= 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 <= 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. For each query of the 1 -st type, output on a separate line one integer -- the required sum. Initially, the permutation has the form [1, 2, 3, 4] . Queries processing is as follows: '...