親密なシェフ (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\)) の満足度を求めるプログラムを作成せよ．

• \(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\) 点) 追加の制約はない．

入力は以下の形式で与えられる．

\(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\) の満足度を出力せよ．

JOI 2025 · JCIOI · CC BY-SA 4.0