2170 - 親密なシェフ (Intimate Chef)

時間制限 3 秒 / メモリ制限 1024 MB / 得点 100 / Writer syoribu / x 0 / 統計 /

TLE
3sec
MLE
1024MB
得点
100

問題文

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

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

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

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

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

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

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

制約

  • 2 ≦ N ≦ 400 000．
  • 1 ≦ Ai ≦ 109 (1 ≦ i ≦ N)．
  • 1 ≦ Bi ≦ 109 (1 ≦ i ≦ N)．
  • 0 ≦ M ≦ 400 000．
  • M < N(N - 1)÷2．
  • 1 ≦ Uj < Vj ≦ N (1 ≦ j ≦ M)．
  • (Ui, Vi) ≠ (Uj, Vj) (1 ≦ i < j ≦ M)．
  • 1 ≦ Q ≦ 400 000．
  • 1 ≦ Xk ≦ 400 000 (1 ≦ k ≦ Q)．
  • Xk ≦ N(N - 1)÷2 - M (1 ≦ k ≦ Q)．
  • 入力される値はすべて整数である．

小課題

  1. (4 点) N ≦ 50，M ≦ 50，Q ≦ 50，Xk ≦ 50 (1 ≦ k ≦ Q)．
  2. (9 点) Bi = 1 (1 ≦ i ≦ N)，M = 0，Q = 1．
  3. (10 点) Bi = 1 (1 ≦ i ≦ N)，Q = 1．
  4. (5 点) Bi = 1 (1 ≦ i ≦ N)．
  5. (29 点) N ≦ 100 000，M ≦ 100 000，Q = 1，X1 = 1．
  6. (14 点) N ≦ 100 000，M ≦ 100 000，Q = 1，X1 ≦ 100 000．
  7. (18 点) N ≦ 100 000，M ≦ 100 000，Q ≦ 100 000，Xk ≦ 100 000 (1 ≦ k ≦ Q)．
  8. (11 点) 追加の制約はない．

入力

入力は以下の形式で与えられる．
N M Q
A1 A2 … AN
B1 B2 … BN
U1 V1
U2 V2
:
UM VM
X1 X2 … XQ

出力

Q 行に出力せよ．k 行目 (1 ≦ k ≦ Q) には客 k の満足度を出力せよ．

入出力例

入力例 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 の制約を満たす．