第24回日本情報オリンピック　二次予選

2024年12月10日
情報オリンピック日本委員会

問題文

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

ただし，シェフはこだわりが強いため仲が悪い 2 人組が M 組いる．仲が悪い 2 人組の j 番目 (1 ≦ j ≦ M) はシェフ U_j とシェフ V_j の 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 人組のうち，満足度が X_k 番目に高くなる 2 人組に料理を作ることを依頼した．具体的には満足度を S として，S × N² + p × N + q が X_k 番目に高くなるシェフ p とシェフ q (1 ≦ p < q ≦ N) の 2 人組に料理を作ることを依頼した．

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

制約

• 2 ≦ N ≦ 400 000．
• 1 ≦ A_i ≦ 10⁹ (1 ≦ i ≦ N)．
• 1 ≦ B_i ≦ 10⁹ (1 ≦ i ≦ N)．
• 0 ≦ M ≦ 400 000．
• M < N(N - 1)÷2．
• 1 ≦ U_j < V_j ≦ N (1 ≦ j ≦ M)．
• (U_i, V_i) ≠ (U_j, V_j) (1 ≦ i < j ≦ M)．
• 1 ≦ Q ≦ 400 000．
• 1 ≦ X_k ≦ 400 000 (1 ≦ k ≦ Q)．
• X_k ≦ N(N - 1)÷2 - M (1 ≦ k ≦ Q)．
• 入力される値はすべて整数である．

小課題

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

入力

入力は以下の形式で与えられる．
N M Q
A₁ A₂ … A_N
B₁ B₂ … B_N
U₁ V₁
U₂ V₂
:
U_M V_M
X₁ X₂ … X_Q

出力

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