3095: Busy Airports

All airports are busy every day. Now, in one airport there are n aircrafts, and the management staff schedules these aircrafts every day to ensure that they provide satisfactory services to passengers. Each aircraft in the airport has two attributes — flight distance a and comfort level b, which are the attributes that passengers are most concerned about. In order to meet the travel needs of different passengers, managers can modify these attributes through the following operations:

• $1~i~A~(1\le i \le n, 1\le A \le 10^5)$ —  Modify the flight distance of the i-th aircraft to A.
• $2~i~B~(1\le i \le n, 1\le B \le 10^5)$ — Modify the comfort level of the i-th aircraft to B.

For passengers, they only care about whether the plane can reach the destination and how comfortable the plane is. Before each flight, passengers will perform the following operations:

• 3 X $(1\le X \le 10^5)$— find an answer that represents the maximum comfort level of all aircrafts with flight distance greater or equal to X.

Now give the execution order of the m operations, including the management personnel to modify the attributes of the aircraft and the query of the passengers. For each passenger's query operation, please help to find out the maximum comfort value of  the aircraft which the passenger travel on.

The first line contains two integers $n,m(1\leq n,m\leq 10^5)$—the number of aircraft, the number of operations。

The second line contains $n$ integers $a_{1},a_{2},...,a_{n}\ (1 \le a_{i} \le 10^{5})$ —the flight distance of each aircraft.

The third line contains $n$ integers $b_{1},b_{2},...,b_{n}\ (1 \le b_{i} \le 10^{5})$ —the comfort value of each aircraft.

Each of the next m lines represent various operations. In each line the first integer is $t \ (1 \le t \le 3)$, which indicates the type of operation.

•  if t = 1, there are two integers  $i$  $A'$ $(1\leq i\leq n,1\leq A'\leq 10^5)$ after $t$ and $A=A'\oplus lastans+1$.
•  if t = 2, there are two integers  $i$  $B'$ $(1\leq i\leq n,1\leq B'\leq 10^5)$ after $t$ and $B=B'\oplus lastans+1$.
•  if t = 3，there are one integers $X'$ $(1\leq X'\leq 10^5)$ after $t$ and $X=X'\oplus lastans+1$.

Let  $lastans$ denote the answer to the last query operation 3 and is initially zero. If there is no aircraft that meets the need, then set lastans=0. And $\oplus$ means XOR operation.

For the passenger request operation in each set of samples, output an integer to indicate the comfort level of the plane which that passenger on. If there is no aircraft that meets the need, please output -1.

3 5
1 2 3
4 5 6
3 4
3 2
1 1 2
2 2 6
3 2

-1
6
4