Description

At the beginning, Yuuka chooses $n$ flowers in the sunflower field. Each flower has a height $h_i$ and a type $t_i$. They are arranged in a line and numbered $1,2,3\cdots n$. Yuuka has $m$ operations of two kinds:

• $\colorbox{f0f0f0}{\verb!1 l r x!}$: Consider all flowers in the interval $[l,r]$. Take out all flowers whose height is not greater than $x$ (that is, flowers with $h_i\le x$), and arrange them in order (that is, do not change their relative order in the original sequence). Then, according to their types, they can be divided into several consecutive segments (for example, $\{\underline{1,}\ \underline{2,2},\underline{1,1},\underline {3,}\ \underline{4,4,4}\}$ can be divided into $5$ segments). Yuuka wants you to tell her how many segments there are in total.

• $\colorbox{f0f0f0}{\verb!2 x y!}$: Yuuka selects one flower with height $x$ and type $y$, and appends it to the end.

Forced online.

Input Format

• The first line contains three integers $n,m,k$. The meanings of $n,m$ are as above, and $k$ is the forced online parameter.

• The next two lines: the first line contains $n$ integers, representing $\{h_1,h_2\cdots h_n\}$; the third line contains $n$ integers, representing the sequence $\{t_1,t_2\cdots t_n\}$. Their meanings are as described above.

• Then follow $m$ lines. Each line begins with an integer $op$, indicating the type of this operation.

  • If $op = 1$, then three integers $l',r',x'$ follow, describing one query.

  • If $op = 2$, then two integers $x',y'$ follow, describing one modification.

• In all operations, the real $l,r,x,y$ are obtained by XOR-ing the input values $l',r',x',y'$ with $k \times last$. Here, $last$ is the answer of the last query, initially $0$.

Output Format

• There are several lines. For each operation $1$, output one integer per line, which is the answer.

10 10 0
6 8 5 9 6 10 2 4 8 9 
2 4 3 3 4 1 2 3 3 2 
2 2 8
1 1 4 4
2 1 6
2 10 2
1 7 9 7
2 10 8
2 8 4
2 3 10
1 5 16 5
1 4 14 7

0
2
5
5

10 20 0
2 19 13 20 7 19 17 8 15 12 
1 2 4 3 5 3 2 4 2 2 
2 9 3
2 17 3
1 1 9 15
1 1 12 3
2 15 5
1 6 13 6
2 7 1
2 20 3
2 12 1
2 10 1
1 5 9 4
1 1 7 15
2 12 4
1 12 12 14
2 7 5
1 3 18 6
1 7 7 1
2 8 5
1 6 8 10
1 14 18 4

5
1
0
0
3
0
0
0
1
0

Hint

$n'$ denotes the length of the sequence after all operations.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \bf{Subtask} & \bm{n',m} & \textsf{\textbf{Special Property}} & \textsf{\textbf{Score}} \cr\hline 1 & 1\le n',m \le 10^3 & \text{None} & 10 \cr\hline 2 & 1\le n',m \le 3\times 10^5 & k=0 & 20\cr\hline 3 & 1\le n',m \le 3\times 10^5 & l=1 & 25\cr\hline 4 & 1\le n',m \le 10^5 & \text{None} & 15\cr\hline 5 & 1\le n',m \le 3\times 10^5 & \text{None} & 20\cr\hline 6 & \text{No special constraints} & \text{Time limit 3s, memory limit 300MB} & 10\cr\hline \end{array}$$

• For $100\%$ of the testdata:

  $1 \le n',m \le 5 \times 10 ^ 5$。

  $1 \le h_i,t_i,x,y \le 10^9$，$1 \le l \le r \le n'$。

  $1 \le op \le 2$，$0 \le k \le 10^3$。

Hint: please pay attention to constant optimization.

Translated by ChatGPT 5