Problem L: RMQ 2

Problem

長さ$N$の2つの数列$A$と$B$が与えられる。はじめ、数列$A$の$i$項目は$a_i$であり、数列$B$の$i$項目は$b_i$である。

以下のような形式の命令文が合計$Q$個与えられるので、与えられた順に処理を行うプログラムを作成せよ。

各命令文は3つの整数$x,y,z$で表される。

• 数列$A$の$y$項目の値を$z$にする。 ($x=1$のとき)
• 数列$B$の$y$項目の値を$z$にする。 ($x=2$のとき)
• 数列$A$の$y$項目から$z$項目の中で最小の値を見つけて報告する。 ($x=3$のとき)
• 数列$B$の$y$項目から$z$項目の中で最小の値を見つけて報告する。 ($x=4$のとき)
• 数列$A$を、数列$B$と全く同じになるように変更する。 ($x=5$のとき)
• 数列$B$を、数列$A$と全く同じになるように変更する。 ($x=6$のとき)

Input

入力は以下の形式で与えられる。

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

Constraints

入力は以下の条件を満たす。

• $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 $ ($1 \le x_i \le 4$のとき)
• $y_i = -1$ ($x_i=5, 6$のとき)
• $1 \le z_i \le 10^9$ ($x_i=1, 2$のとき)
• $y_i \le z_i \le N$ ($x_i=3, 4$のとき)
• $z_i = -1$ ($x_i=5, 6$のとき)
• 入力はすべて整数

Output

$x=3$または$x=4$の命令文が入力で与えられる度に、見つけた値を1行に出力する。

Sample Input 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

Sample Output 1

7
2
2
8
1

Note

Link

 

---