Problem Description

There is an initially empty set of segments. You need to process $q$ queries. Each query is in one of the following three forms:

1. Add a new segment $[l_i, r_i]$.
2. For all segments in the set that intersect with $[l_i, r_i]$, modify each of them into its intersection with $[l_i, r_i]$.
3. Compute the sum of lengths of the intersections between $[l_i, r_i]$ and all segments in the set that intersect with $[l_i, r_i]$.

Two segments $[a,b]$ and $[c,d]$ intersect if and only if $\max\{a,c\} \leq \min\{b,d\}$. Their intersection is $[\max\{a,c\}, \min\{b,d\}]$.

The length of a segment $[a,b]$ is $b-a$.

In some test points, you need to perform these operations online.

Note: In this problem, a segment may degenerate into a single point.

Input Format

The first line contains two positive integers $q$ and $type$, representing the number of operations and the forced online parameter.

The next $q$ lines each contain three positive integers $opt, l_i', r_i'$, where $opt$ indicates the operation type.

Let $last$ be the answer to the previous type $3$ query ($last$ is initially $0$). Then the real values are $l_i = ( l_i' + type \times last ) \bmod ( 2 \times 10^5 + 1 )$, $r_i = ( r_i' + type \times last ) \bmod ( 2 \times 10^5 + 1 )$.

The data guarantees that $1 \leq l_i \leq r_i \leq 2 \times 10^5$.

Output Format

For each type $3$ query, output one line containing the answer.

9 0
1 1 5
1 6 8
1 2 3
3 3 8
2 4 6
1 5 9
2 2 7
3 2 7
3 3 6

4
4
2

Hint

Sample Explanation

The set of segments after each operation:

• After the first: $\{ [1,5] \}$
• After the second: $\{ [1,5],[6,8] \}$
• After the third: $\{ [1,5],[6,8],[2,3] \}$
• After the fifth: $\{ [4,5],[6,6],[2,3] \}$
• After the sixth: $\{ [4,5],[6,6],[2,3],[5,9] \}$
• After the seventh: $\{ [4,5],[6,6],[2,3],[5,7] \}$

Constraints

Let $k_1, k_2, k_3$ be the numbers of queries with $opt=1,2,3$, respectively.

For all data, $1 \leq q \leq 5 \times 10^5$, $k_3 \geq 1$, $0 \leq l_i', r_i' \leq 2 \times 10^5$, $1 \leq l_i \leq r_i \leq 2 \times 10^5$, $0 \leq type \leq 1$, $1 \leq opt \leq 3$.

Translated by ChatGPT 5