CF1443E Long Permutation

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.

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.

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: 1. $ 2 + 3 + 4 = 9 $ ; 2. $ [1, 2, 3, 4] \rightarrow [1, 2, 4, 3] \rightarrow [1, 3, 2, 4] \rightarrow [1, 3, 4, 2] $ ; 3. $ 1 + 3 = 4 $ ; 4. $ 4 + 2 = 6 $