問題文

あるボリビア料理レストランでは 1 から N までの番号が付けられている N 人のシェフが働いている．シェフ i (1 \leqq i \leqq N) は美味しさが A_i であるシルパンチョと美味しさが B_i であるピケマチョを作ることができる．

ただし，シェフはこだわりが強いため仲が悪い 2 人組が M 組いる．仲が悪い 2 人組の j 番目 (1 \leqq j \leqq M) はシェフ U_j とシェフ V_j の 2 人組である．

このレストランに来店する客は以下のようにして料理を食べる．

• 1 \leqq p < q \leqq N を満たす整数 p, q を選び，シェフ p とシェフ q の 2 人組に料理を作ることを依頼する．ただし，仲が悪い 2 人組に料理を作ることを依頼することはできない．
• シルパンチョとピケマチョの各料理はシェフ p とシェフ q のうち美味しさがより高いものを作ることができるシェフが作る．ある料理について 2 人が同じ美味しさの料理を作ることができるとき，どちらか 1 人のシェフが作る．1 人のシェフが 2 つの料理を作ることも可能であることに注意せよ．
• 客の満足度はシルパンチョの美味しさとピケマチョの美味しさの合計である．

このレストランに 1 から Q までの番号が付けられている Q 人の客が来店した．

客 k (1 \leqq k \leqq Q) は，料理を作ることを依頼することができる 2 人組のうち，満足度が X_k 番目に高くなる 2 人組に料理を作ることを依頼した．具体的には満足度を S として，S \times N^2 + p \times N + q が X_k 番目に高くなるシェフ p とシェフ q (1 \leqq p < q \leqq N) の 2 人組に料理を作ることを依頼した．

レストランのシェフと客の情報が与えられたとき，客 k (1 \leqq k \leqq Q) の満足度を求めるプログラムを作成せよ．

制約

• 2 \leqq N \leqq 400\,000．
• 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N)．
• 1 \leqq B_i \leqq 10^9 (1 \leqq i \leqq N)．
• 0 \leqq M \leqq 400\,000．
• M < \frac{N(N - 1)}{2}．
• 1 \leqq U_j < V_j \leqq N (1 \leqq j \leqq M)．
• (U_i, V_i) \neq (U_j, V_j) (1 \leqq i < j \leqq M)．
• 1 \leqq Q \leqq 400\,000．
• 1 \leqq X_k \leqq 400\,000 (1 \leqq k \leqq Q)．
• X_k \leqq \frac{N(N - 1)}{2} - M (1 \leqq k \leqq Q)．
• 入力される値はすべて整数である．

小課題

1. (4 点) N \leqq 50，M \leqq 50，Q \leqq 50，X_k \leqq 50 (1 \leqq k \leqq Q)．
2. (9 点) B_i = 1 (1 \leqq i \leqq N)，M = 0，Q = 1．
3. (10 点) B_i = 1 (1 \leqq i \leqq N)，Q = 1．
4. (5 点) B_i = 1 (1 \leqq i \leqq N)．
5. (29 点) N \leqq 100\,000，M \leqq 100\,000，Q = 1，X_1 = 1．
6. (14 点) N \leqq 100\,000，M \leqq 100\,000，Q = 1，X_1 \leqq 100\,000．
7. (18 点) N \leqq 100\,000，M \leqq 100\,000，Q \leqq 100\,000，X_k \leqq 100\,000 (1 \leqq k \leqq Q)．
8. (11 点) 追加の制約はない．

入力例 1

4 2 4
2 7 3 5
4 3 4 8
1 3
2 4
1 2 3 4

出力例 1

13
13
11
11

料理を作ることを依頼することができるシェフの 2 人組は 4 通りあり，それぞれにおける客の満足度は以下のようになる．

• シェフ 1 とシェフ 2 を選んだとき，シルパンチョはシェフ 2 が作り，ピケマチョはシェフ 1 が作る．したがって，シルパンチョの美味しさは 7 となり，ピケマチョの美味しさは 4 となる．よって，客の満足度は 7 + 4 = 11 である．
• シェフ 1 とシェフ 4 を選んだとき，シルパンチョはシェフ 4 が作り，ピケマチョはシェフ 4 が作る．したがって，シルパンチョの美味しさは 5 となり，ピケマチョの美味しさは 8 となる．よって，客の満足度は 5 + 8 = 13 である．
• シェフ 2 とシェフ 3 を選んだとき，シルパンチョはシェフ 2 が作り，ピケマチョはシェフ 3 が作る．したがって，シルパンチョの美味しさは 7 となり，ピケマチョの美味しさは 4 となる．よって，客の満足度は 7 + 4 = 11 である．
• シェフ 3 とシェフ 4 を選んだとき，シルパンチョはシェフ 4 が作り，ピケマチョはシェフ 4 が作る．したがって，シルパンチョの美味しさは 5 となり，ピケマチョの美味しさは 8 となる．よって，客の満足度は 5 + 8 = 13 である．

したがって，それぞれの客について以下のことが分かる．

• 客 1 はシェフ 3 とシェフ 4 の 2 人組を選んだ．したがって，客 1 の満足度は 13 となった．
• 客 2 はシェフ 1 とシェフ 4 の 2 人組を選んだ．したがって，客 2 の満足度は 13 となった．
• 客 3 はシェフ 2 とシェフ 3 の 2 人組を選んだ．したがって，客 3 の満足度は 11 となった．
• 客 4 はシェフ 1 とシェフ 2 の 2 人組を選んだ．したがって，客 4 の満足度は 11 となった．

この入力例は小課題 1,7,8 の制約を満たす．

入力例 2

4 3 1
3 6 5 4
1 1 1 1
1 2
2 3
2 4
1

出力例 2

6

料理を作ることを依頼することができるシェフの 2 人組は 3 通りあり，それぞれにおける客の満足度は以下のようになる．

• シェフ 1 とシェフ 3 を選んだとき，シルパンチョはシェフ 3 が作り，ピケマチョはシェフ 1 かシェフ 3 が作る．したがって，シルパンチョの美味しさは 5 となり，ピケマチョの美味しさは 1 となる．よって，客の満足度は 5 + 1 = 6 である．
• シェフ 1 とシェフ 4 を選んだとき，シルパンチョはシェフ 4 が作り，ピケマチョはシェフ 1 かシェフ 4 が作る．したがって，シルパンチョの美味しさは 4 となり，ピケマチョの美味しさは 1 となる．よって，客の満足度は 4 + 1 = 5 である．
• シェフ 3 とシェフ 4 を選んだとき，シルパンチョはシェフ 3 が作り，ピケマチョはシェフ 3 かシェフ 4 が作る．したがって，シルパンチョの美味しさは 5 となり，ピケマチョの美味しさは 1 となる．よって，客の満足度は 5 + 1 = 6 である．

したがって，客 1 について以下のことが分かる．

• 客 1 はシェフ 3 とシェフ 4 の 2 人組を選んだ．したがって，客 1 の満足度は 6 となった．

この入力例は小課題 1,3,4,5,6,7,8 の制約を満たす．

入力例 3

5 0 4
1 2 3 4 5
5 4 3 2 1
3 9 10 1

出力例 3

9
7
7
10

この入力例は小課題 1,7,8 の制約を満たす．

入力例 4

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

出力例 4

121
169
129
174
169
137
183
148
169
183

この入力例は小課題 1,7,8 の制約を満たす．