# RMQ 2

Time Limit : 2 sec, Memory Limit : 262144 KB

# Problem L: RMQ 2

## Problem

$N$2̐$A$$B^B͂߁AA$$i$ڂ$a_i$łA$B$$iڂb_iłB ȉ̂悤Ȍ̖ߕvQ^̂ŁA^ꂽɏsvO쐬B eߕ3̐x,y,zŕ\B • A$$y$ڂ̒l$z$ɂB ($x=1$̂Ƃ)
• $B$$yڂ̒lzɂB (x=2̂Ƃ) • A$$y$ڂ$z$ڂ̒ōŏ̒lĕ񍐂B ($x=3$̂Ƃ)
• $B$$y$ڂ$z$ڂ̒ōŏ̒lĕ񍐂B ($x=4$̂Ƃ)
• $A$A$B$ƑSɂȂ悤ɕύXB ($x=5$̂Ƃ)
• $B$A$A$ƑSɂȂ悤ɕύXB ($x=6$̂Ƃ)

## Input

͈͂ȉ̌ŗ^B

$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

͈͂ȉ̏𖞂B

• $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$̖ߕ͂ŗ^xɁAl1sɏo͂B

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


Source: Aizu Competitive Programming Camp 2017 , Day 2, Aizu-Wakamatsu, Japan, 2017-09-19