Source

This problem is proposed by . All rights reserved.

Problem Source: https://www.luogu.com.cn/problem/T565371

Problem Background

"Extinguished in radiance, disintegrated from order, vanished in ashes."

Problem Description

After the "God" created the "World," the "Demon," representing destruction and the end, once again descended upon the "World."

Initially, the "World" consists of $n$ empty "lands," and there are $V$ types of substances numbered starting from $0$.
As "history" gradually unfolds, the "God" and the "Demon" engage in several battles on it, while you, as the proxy of the "God," watch the fight from the clouds.
During this period, a total of $m$ events occur, each starting with a number $T$ and belonging to one of the following four types:

• 0 l r: You inquire about the $\text{mex}$ of all substance types that have appeared in $[l,r]$, i.e., the smallest-numbered substance that has not appeared. If all have appeared, the answer is $V$.
• 1 op l r v: If $op=1$, the "God" creates the $v$-th substance on every "land" in $[l,r]$. Otherwise, the "Demon" destroys all $v$-th substances on those lands.
• 2 op x: If $op=1$, the "God" creates an empty "land" before the $x$-th "land." Otherwise, the "Demon" completely destroys the $x$-th "land."
• 3 l r v: The "God" or the "Demon" changes every $i$-th substance (if any) on each "land" in $[l,r]$ to the $(i+v)\bmod V$-th substance.

Clearly, no one will answer your questions for you. Therefore, with the pride of the "God," please depict this apocalyptic battle.

Input Format

The first line contains three integers $n$, $m$, $V$.
The next $m$ lines describe each event, as specified above.

Output Format

For each query with $T=0$, output the answer on a separate line.

Samples

5 5 4
1 1 1 3 0
1 1 2 4 1
1 1 3 5 2
2 0 3
0 2 4

3

15 18 4
1 0 1 10 0
1 1 5 14 2
2 0 15
2 1 5
3 7 10 1
3 6 8 0
3 4 9 2
2 0 9
0 1 9
2 0 2
2 1 7
1 0 7 11 3
1 0 4 11 1
1 0 6 12 1
0 2 7
1 0 1 8 1
3 7 11 2
0 1 8

2
1
1

5 7 1024
2 0 5
1 0 2 4 108
1 1 2 3 85
3 4 4 588
2 1 4
2 1 5
0 2 5

0

Sample 1 Explanation

• Initial "World": $\{\varnothing,\varnothing,\varnothing,\varnothing,\varnothing\}$.
• After the first battle: $\{\{0\},\{0\},\{0\},\varnothing,\varnothing\}$.
• After the second battle: $\{\{0\},\{0,1\},\{0,1\},\{1\},\varnothing\}$.
• After the third battle: $\{\{0\},\{0,1\},\{0,1,2\},\{1,2\},\{2\}\}$.
• After the fourth battle: $\{\{0\},\{0,1\},\{1,2\},\{2\}\}$.
• The fifth query: $\{\{0,1\},\{1,2\},\{2\}\}$, where the smallest-numbered substance not appearing is the $3$-rd, so output it.

Data Range

This problem uses bundling tests.

This problem is slightly time-sensitive, so please pay attention to constant-level optimizations.

For all data:

• $1\le n,m\le10^5$.
• $4\le V\le2^{10}$.
• $0\le T\le3$.
• $0\le op\le1$.
• $0\le v<V$.
• Ensure that $l,r,x$ in any event are within the size range of the "World."
• The "World" will never be completely destroyed at any moment.