Long Permutation
Contest: Codeforces Round 681 (Div. 2, based on VK Cup 2019-2020 - Final)
Difficulty rating: 2400
Tags: brute force, math, two pointers

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.

Input format:
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.

Output format:
For each query of the $$$1$$$-st type, output on a separate line one integer — the required sum.

Constraints:
Time limit: 4.0 s
Memory limit: 256.0 MB

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

Example input:
4 4
1 2 4
2 3
1 1 2
1 3 4

Example output:
9
4
6

Editorial:
Let's notice that most of the elements in the original permutation will not change during all queries. Since the maximum permutation number does not exceed $$$10^{10}$$$, only the last $$$15$$$ elements of the permutation will change.
Thus, after each query of the second type, you need to generate a permutation with the corresponding number.
To answer the query of the first type, you need to split the segment into two parts: we sum the part of the segment that fell in the last $$$15$$$ elements in a simple cycle and calculate the other part of the segment using the formula of an arithmetic progression.