AT_joi2025_yo2_d 親密なシェフ (Intimate Chef)

あるボリビア料理レストランでは $ 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 $ ) の満足度を求めるプログラムを作成せよ．

入力は以下の形式で与えられる． > $ N $ $ M $ $ Q $ $ A_1 $ $ A_2 $ $ \cdots $ $ A_N $ $ B_1 $ $ B_2 $ $ \cdots $ $ B_N $ $ U_1 $ $ V_1 $ $ U_2 $ $ V_2 $ $ \vdots $ $ U_M $ $ V_M $ $ X_1 $ $ X_2 $ $ \cdots $ $ X_Q $

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

### 小課題 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 $ 点) 追加の制約はない． ### Sample Explanation 1 料理を作ることを依頼することができるシェフの $ 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 $ の制約を満たす． ### Sample Explanation 2 料理を作ることを依頼することができるシェフの $ 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 $ の制約を満たす． ### Sample Explanation 3 この入力例は小課題 $ 1,7,8 $ の制約を満たす． ### Sample Explanation 4 この入力例は小課題 $ 1,7,8 $ の制約を満たす． ### Constraints - $ 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 $ )． - 入力される値はすべて整数である．