H. Hacker in the system
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Carolina, a skilled programmer from Monitoramento e Proteção Paulista (MPP), specialized in information security, faces her biggest challenge: a hacker has invaded the database of the social security system in São Paulo!

The hacker completely scrambled the database, but fortunately, Carolina has a plan to recover this data. We can represent the scrambled database as a very long sequence of data. Carolina divides this sequence into consecutive blocks of size $$$K$$$, meaning the first block contains positions from $$$0$$$ to $$$K-1$$$, the next from $$$K$$$ to $$$2K-1$$$, and so on. To recover the original sequence, Carolina wants to apply a sequence of operations to the database, which consist of block rotations, position swaps, and queries on data segments to check consistency.

Formally, we have a sequence $$$A$$$ of integers that represents the initial positions of the data (scrambled), i.e., initially $$$A[i] = i$$$ for all $$$i \ge 0$$$. It can be considered that the sequence is infinite. Carolina's plan consists of operations of the following types:

1 p: rotates each of the blocks to the left $$$p$$$ times. This operation is applied to each block independently. Each time the block is rotated to the left, the last value of $$$A[i]$$$ becomes the first, and all other values of $$$A[i]$$$ become equal to $$$A[i+1]$$$.

2 s t: swaps the values of $$$A[i\cdot K + s]$$$ and $$$A[i\cdot K + t]$$$ for all $$$i \ge 0$$$.

3 l r: prints the sum of $$$A[i]$$$ for all $$$i$$$ such that $$$l \le i \le r$$$.

After implementing the recovery system, Carolina needs to validate whether the operations were applied correctly. Write a program that, given the operations of Carolina's plan in the order they were applied, prints the output of all operations of type 3.

Input

The first line contains two integers $$$Q$$$ and $$$K$$$ $$$(1 \le Q \le 10^5, 2 \le K \le 10^6)$$$, the number of operations and the size of the blocks, respectively.

The following $$$Q$$$ lines contain the description of each operation, as in the statement, in the order they are applied. It is guaranteed that $$$1 \le p \le K$$$ in each operation of type 1, that $$$0 \le s, t \lt K, s \neq t$$$, in each operation of type 2, and that $$$0 \le l \le r \le 10^9$$$ in each operation of type 3.

Output

The output consists of one line for each operation of type 3, containing an integer equal to the result of each operation of type 3, in the order they appear in the input.

Examples
Input
5 5
3 1 8
2 0 3
3 1 8
1 3
3 2 7
Output
36
33
28
Input
6 500
1 100
2 25 75
3 1050 9000
1 50
2 30 60
3 1000000 500000000
Output
39948825
124999500250500150
Note

Explanation of example 1:

In this first example, the first two blocks of 5 positions look like this: