Description

一开始，幽香选择了太阳花田当中的 $n$ 朵花朵。每朵花有一个高度 $h_i$ ，以及它属于的类别 $t_i$ 。它们排成了一列，并且被标号为 $1,2,3\cdots n$ 。幽香有 $m$ 次操作，分为两种：

• $\colorbox{f0f0f0}{\verb!1 l r x!}$ ：考虑区间 $[l,r]$ 内的所有花朵。我们取出其中所有高度不超过 $x$ 的花朵（即 $h_i\le x$ 的花朵），依次排列（即不改变花朵在原序列中的顺序），可以根据它们的种类划分为若干段（比如，$\{\underline{1,}\ \underline{2,2},\underline{1,1},\underline {3,}\ \underline{4,4,4}\}$ 就能分为 $5$ 段）。幽香希望你告诉她一共有多少段。

• $\colorbox{f0f0f0}{\verb!2 x y!}$ ：幽香挑选了一朵高度为 $x$ ，种类为 $y$ 的花朵，拼接在末尾。

强制在线。

Input Format

• 第一行三个整数 $n,m,k$ 。$n,m$ 含义如上，而 $k$ 为强制在线参数。

• 接下来两行，第一行是 $n$ 个整数，表示 $\{h_1,h_2\cdots h_n\}$ ；第三行 $n$ 个整数，表示序列 $t_1,t_2\cdots t_n\}$ 。含义如题所示。

• 接下来 $m$ 行，每行首先一个整数 $op$ ，表示本次操作的种类。

  • 如果 $op = 1$，接下来三个整数 $l',r',x'$，描述一次查询。

  • 如果 $op = 2$，接下来两个整数 $x',y'$，表示一次修改。

• 在所有操作中，真正的 $l,r,x,y$ 都是输入的 $l',r',x',y'$ 异或上 $k \times last$ 后的值。其中， $last$ 表示最后一次查询的答案，初始为 $0$。

Output Format

• 共有若干行。对于每个操作 $1$ ，每行输出一个整数，表示答案。

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'$ 表示进行所有操作后的序列长度。

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|}\hline \bf{Subtask} & \bm{n',m} & \textsf{\textbf{特殊性质}} & \textsf{\textbf{分值}} \cr\hline 1 & 1\le n',m \le 10^3 & \text{无} & 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{无} & 15\cr\hline 5 & 1\le n',m \le 3\times 10^5 & \text{无} & 20\cr\hline 6 & \text{无特殊限制} & \text{时限 3s，空限 300MB} & 10\cr\hline \end{array}$$

• 对于 $100\%$ 的数据：

  $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$。

提示：请注意常数优化。