RMQ 2

Problem

Given two sequences of length $N$, $A$ and $B$. First, the $i$ item in the sequence $A$ is $a_i$, and the $i$ item in the sequence $B$ is $b_i$.

Since a total of $Q$ of statements of the following format are given, create a program that processes in the given order.

Each statement is represented by three integers $x, y, z$.

• Set the value of the $y$ item in the sequence $A$ to $z$. (When $x = 1$)
• Set the value of the $y$ item in the sequence $B$ to $z$. (When $x = 2$)
• Find and report the smallest value in the $z$ item from the $y$ item in the sequence $A$. (When $x = 3$)
• Find and report the smallest value in the $z$ item from the $y$ item in the sequence $B$. (When $x = 4$)
• Change the sequence $A$ to be exactly the same as the sequence $B$. (When $x = 5$)
• Change the sequence $B$ to be exactly the same as the sequence $A$. (When $x = 6$)

Constraints

The input satisfies the following conditions.

• $2 \ le N \ le 2 \ times 10 ^ 5$
• $2 \ le Q \ le 2 \ times 10 ^ 5$
• $1 \ le a_i \ le 10 ^ 9$
• $1 \ le b_i \ le 10 ^ 9$
• $1 \ le x_i \ le 6$
• $1 \ le y_i \ le N$ (when $1 \ le x_i \ le 4$)
• $y_i = -1$ (when $x_i = 5, 6$)
• $1 \ le z_i \ le 10 ^ 9$ (when $x_i = 1, 2$)
• $y_i \ le z_i \ le N$ (when $x_i = 3, 4$)
• $z_i = -1$ (when $x_i = 5, 6$)
• All inputs are integers

Input

The input is given in the following format.

$N$ $a_ {1}$ $a_ {2}$ ... $a_ {N}$ $b_ {1}$ $b_ {2}$ ... $b_ {N}$ $Q$ $x_1$ $y_1$ $z_1$ $x_2$ $y_2$ $z_2$ ... $x_Q$ $y_Q$ $z_Q$

Output

Every time a statement of $x = 3$ or $x = 4$ is given by input, the found value is output on one line.

Example

Input

5 1 3 5 7 9 6 2 3 2 6 10 1 3 4 3 4 5 4 2 3 5 -1 -1 2 3 8 3 2 5 4 3 3 1 1 1 6 -1 -1 3 1 5

Output

7 2 2 8 1

inputFormat

input satisfies the following conditions.

• $2 \ le N \ le 2 \ times 10 ^ 5$
• $2 \ le Q \ le 2 \ times 10 ^ 5$
• $1 \ le a_i \ le 10 ^ 9$
• $1 \ le b_i \ le 10 ^ 9$
• $1 \ le x_i \ le 6$
• $1 \ le y_i \ le N$ (when $1 \ le x_i \ le 4$)
• $y_i = -1$ (when $x_i = 5, 6$)
• $1 \ le z_i \ le 10 ^ 9$ (when $x_i = 1, 2$)
• $y_i \ le z_i \ le N$ (when $x_i = 3, 4$)
• $z_i = -1$ (when $x_i = 5, 6$)
• All inputs are integers

Input

The input is given in the following format.

$N$ $a_ {1}$ $a_ {2}$ ... $a_ {N}$ $b_ {1}$ $b_ {2}$ ... $b_ {N}$ $Q$ $x_1$ $y_1$ $z_1$ $x_2$ $y_2$ $z_2$ ... $x_Q$ $y_Q$ $z_Q$

outputFormat

Output

Every time a statement of $x = 3$ or $x = 4$ is given by input, the found value is output on one line.

Example

Input

5 1 3 5 7 9 6 2 3 2 6 10 1 3 4 3 4 5 4 2 3 5 -1 -1 2 3 8 3 2 5 4 3 3 1 1 1 6 -1 -1 3 1 5

Output

7 2 2 8 1

样例

5
1 3 5 7 9
6 2 3 2 6
10
1 3 4
3 4 5
4 2 3
5 -1 -1
2 3 8
3 2 5
4 3 3
1 1 1
6 -1 -1
3 1 5

7
2
2
8
1

</p>