Description

However, the dark forces can change the terrain, which makes it very difficult for the army to advance.

To help the army move faster, Steve brought nuclear weapons to the front line to destroy the terrain.

Also, Steve cares a lot about the current terrain situation.

Specifically, the front-line terrain can be divided into $n$ segments, with initial height $0$. During the final battle, $m$ events will happen. An event can be:

1. Steve asks: in the interval $[l,r]$, how many segments have height less than the given height $h$.
2. Steve uses nuclear weapons: in the interval $[l,r]$, for segments whose height is greater than $h$, reduce their height to $h$.
3. The dark forces change the terrain: in the interval $[l,r]$, for segments whose height is less than $h$, increase their height to $h$.

Because the battle is very urgent, some test points require online processing.

For test points with $k=1$, let the answer to the last type 1 event be $lastans$. You need to XOR $l$, $r$, and $h$ with $lastans$ respectively to get the actual values. If no type 1 event has been answered yet, then $lastans=0$.

Input Format

The first line contains $3$ integers $n,m,k$.

The next $m$ lines each contain $4$ integers describing an event.

The first integer $opt$ indicates the event type, followed by $3$ integers $l,r,h$, with meanings as described above.

There are cases where $l>r$ in the testdata. In this case, please ignore this operation directly.

Output Format

For each type 1 event, output one integer per line, which is the answer to the query.

10 8 0
1 1 5 1
3 1 3 5
1 1 5 3
2 2 3 3
1 1 5 3
1 1 5 5
3 3 4 2
1 1 5 3

5
2
2
4
2

Hint

Sample explanation:

[00000]00000=>5[TTTTT]
[000]0000000
[55500]00000=>2[FFFTT]
5[55]0000000
[53300]00000=>2[FFFTT]
[53300]00000=>4[FTTTT]
53[30]000000
[53320]00000=>2[FFFTT]

Constraints:

For all data, it is guaranteed that $1\le l \le r \le n,0\le h \le 10^9$.

Subtask 1 is the data used during the contest.

For test point 6, it is guaranteed that all type 1 events occur after type 2 and type 3 events.

Subtask 2 is unscored hack data. It currently only contains one dataset, satisfying the property of #8.

$\color{white}\texttt{No guarantee that the data is random}$

Translated by ChatGPT 5