레이팅 미적용あるボリビア料理レストランでは 1 から N までの番号が付けられている N 人のシェフが働いている.シェフ i ( \(1 \le i \le N\) ) は 美味しさ が A i であるシルパンチョと美味しさが B i であるピケマチョを作ることができる.
ただし,シェフはこだわりが強いため仲が悪い 2 人組が M 組いる.仲が悪い 2 人組の j 番目 ( \(1 \le j \le M\) ) はシェフ U j とシェフ V j の 2 人組である.
このレストランに来店する客は以下のようにして料理を食べる.
\(1 \le p < q \le N\) を満たす整数 p, q を選び,シェフ p とシェフ q の 2 人組に料理を作ることを依頼する.ただし,仲が悪い 2 人組に料理を作ることを依頼することはできない.
シルパンチョとピケマチョの各料理はシェフ p とシェフ q のうち美味しさがより高いものを作ることができるシェフが作る.ある料理について 2 人が同じ美味しさの料理を作ることができるとき,どちらか 1 人のシェフが作る. 1 人のシェフが 2 つの料理を作ることも可能であることに注意せよ.
客の 満足度 はシルパンチョの美味しさとピケマチョの美味しさの合計である.
このレストランに 1 から Q までの番号が付けられている Q 人の客が来店した.
客 k ( \(1 \le k \le Q\) ) は,料理を作ることを依頼することができる 2 人組のうち,満足度が X k 番目に高くなる 2 人組に料理を作ることを依頼した.具体的には満足度を S として, S × N 2 + p × N + q が X k 番目に高くなるシェフ p とシェフ q ( \(1 \le p < q \le N\) ) の 2 人組に料理を作ることを依頼した.
レストランのシェフと客の情報が与えられたとき,客 k ( \(1 \le k \le Q\) ) の満足度を求めるプログラムを作成せよ.
2 ≦ N ≦ 400 000 .
1 ≦ A i ≦ 10 9 ( \(1 \le i \le N\) ).
1 ≦ B i ≦ 10 9 ( \(1 \le i \le N\) ).
0 ≦ M ≦ 400 000 .
M < N(N - 1)÷2 .
1 ≦ U j < V j ≦ N ( \(1 \le j \le M\) ).
(U i , V i ) ≠ (U j , V j ) ( \(1 \le i < j \le M\) ).
1 ≦ Q ≦ 400 000 .
1 ≦ X k ≦ 400 000 ( \(1 \le k \le Q\) ).
X k ≦ N(N - 1)÷2 - M ( \(1 \le k \le Q\) ).
入力される値はすべて整数である.
( 4 点) \(N \le 50\) , \(M \le 50\) , \(Q \le 50\) , X k ≦ 50 ( \(1 \le k \le Q\) ).
( 9 点) B i = 1 ( \(1 \le i \le N\) ), M = 0 , Q = 1 .
( 10 点) B i = 1 ( \(1 \le i \le N\) ), Q = 1 .
( 5 点) B i = 1 ( \(1 \le i \le N\) ).
( 29 点) N ≦ 100 000 , M ≦ 100 000 , Q = 1 , X 1 = 1 .
( 14 点) N ≦ 100 000 , M ≦ 100 000 , Q = 1 , X 1 ≦ 100 000 .
( 18 点) N ≦ 100 000 , M ≦ 100 000 , Q ≦ 100 000 , X k ≦ 100 000 ( \(1 \le k \le Q\) ).
( 11 点) 追加の制約はない.
入力は以下の形式で与えられる.
N M Q
A 1 A 2 ... A N
B 1 B 2 ... B N
U 1 V 1
U 2 V 2
:
U M V M
X 1 X 2 ... X Q
Q 行に出力せよ. k 行目 ( \(1 \le k \le Q\) ) には客 k の満足度を出力せよ.
4 2 4
2 7 3 5
4 3 4 8
1 3
2 4
1 2 3 4
13
13
11
11
4 3 1
3 6 5 4
1 1 1 1
1 2
2 3
2 4
1
6
5 0 4
1 2 3 4 5
5 4 3 2 1
3 9 10 1
9
7
7
10
13 12 10
2 28 28 60 48 77 63 92 13 71 36 91 87
85 7 64 15 55 92 66 91 83 35 49 22 61
2 9
8 13
7 11
9 11
8 12
5 12
4 7
11 12
10 12
4 11
1 5
3 8
49 21 46 13 20 41 6 33 24 7
121
169
129
174
169
137
183
148
169
183