Sequence Query Processing

Given an integer Q representing the number of queries and an initial modulo value M, you are to process Q queries. There are two types of queries:

• Type 1: Generate a sequence of length N using the recurrence relation $$a_1 = S_1,\quad a_2 = S_2,\quad a_i = (a_{i-1}+a_{i-2})\mod M \quad \text{for } i\ge3,$$ and then update the elements from index L to R (1-indexed) by replacing each element with its remainder modulo K.
• Type 2: Query the sum of the elements in the current sequence from index L to R (1-indexed).

Process each query in the order given. For every Type 2 query, output the computed sum on a new line.

inputFormat

The first line of input contains two space-separated integers: Q (the number of queries) and M (the initial modulo value).

Each of the following Q lines contains a query in one of the following formats:

• For a Type 1 query: 1 S1 S2 N L R K
• For a Type 2 query: 2 L R

It is guaranteed that there is at least one Type 2 query.

outputFormat

For each Type 2 query, output the sum of the corresponding segment of the current sequence on a new line.

## sample

5 10
1 1 1 5 1 2 3
2 1 5
1 2 3 6 3 4 5
2 1 6
2 4 6

12
12
7

</p>