Problem L: RMQ 2

Problem

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

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

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

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

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

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