Range MinPair Query

2 secs 1024 MB
Nachia

問題文


ともに長さ の数列 が与えられます。
個のクエリに答えてください。
各クエリでは つの整数 が与えられるので、 を満たす整数の組 における の最小値を求めてください。

入力


入力は以下の形式で標準入力から与えられます。
番目のクエリにおける です。

入力は以下の制約を満たします。

  • 値はすべて整数

出力


各クエリについて、答えを出力して改行してください。

入力例


入力例1


4
9 5 3 3
1 6 9 7
2
1 3
2 4

出力例1


10
10

入力例2


1
100000000
100000000
1
1 1

出力例2


200000000

入力例3


10
314159 26535 89793 23846 26433 83279 50288 41971 69399 37510
58209 74944 59230 78164 6286 20899 86280 34825 34211 70679
8
1 4
1 7
2 2
2 6
2 10
4 8
5 6
7 10

出力例3


85765
30132
101479
30132
30132
30132
32719
76182

Submit


Go (1.14)