P12459 [JOI2025 预选赛 R2] 亲密的厨师

在某家玻利维亚餐厅，有 $N$ 位厨师，编号从 $1$ 到 $N$。厨师 $i$ ($1 \le i \le N$) 可以制作美味度为 $A_i$ 的锡尔潘乔 (silpancho) 和美味度为 $B_i$ 的皮克马乔 (pique macho)。 然而，这些厨师都有很强的个性，因此有 $M$ 对厨师彼此不和。第 $j$ 对 ($1 \le j \le M$) 不和的厨师是厨师 $U_j$ 和厨师 $V_j$。 来到这家餐厅的顾客会按以下方式用餐： * 选择满足 $1 \le p < q \le N$ 的整数 $p, q$，并委托厨师 $p$ 和厨师 $q$ 这两人制作料理。但是，不能委托不和的两人组制作料理。 * 锡尔潘乔和皮克马乔这两道菜都由厨师 $p$ 和厨师 $q$ 中能够做出更高美味度料理的那位厨师制作。如果对于某道菜，两人都能做出相同美味度的料理，则由其中一人制作。注意，一位厨师可以制作两道菜。 * 顾客的**满意度**是锡尔潘乔的美味度和皮克马乔的美味度之和。 这家餐厅来了 $Q$ 位顾客，编号从 $1$ 到 $Q$。 顾客 $k$ ($1 \le k \le Q$) 会委托在所有可以委托的两人组中，满意度第 $X_k$ 高的两人组制作料理。具体来说，如果满意度为 $S$，则选择使得 $S \times N^2 + p \times N + q$ 的值是第 $X_k$ 高的厨师 $p$ 和厨师 $q$ ($1 \le p < q \le N$) 两人组来制作料理。 给定餐厅厨师和顾客的信息，请编写一个程序来计算顾客 $k$ ($1 \le k \le Q$) 的满意度。

无

无

### 样例 1 解释 可以委托制作料理的厨师二人组有 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 的二人组。因此，顾客 1 的满意度为 13。 * 顾客 2 选择厨师 1 和厨师 4 的二人组。因此，顾客 2 的满意度为 13。 * 顾客 3 选择厨师 2 和厨师 3 的二人组。因此，顾客 3 的满意度为 11。 * 顾客 4 选择厨师 1 和厨师 2 的二人组。因此，顾客 4 的满意度为 11。 这个输入样例满足子任务 1, 7, 8 的约束。 ### 样例 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 的二人组。因此，顾客 1 的满意度为 6。 这个输入样例满足子任务 1, 3, 4, 5, 6, 7, 8 的约束。 ### 数据范围 * $2 \le N \le 400\,000$ * $1 \le A_i \le 10^9$ ($1 \le i \le N$) * $1 \le B_i \le 10^9$ ($1 \le i \le N$) * $0 \le M \le 400\,000$ * $M < N(N - 1) \div 2$ * $1 \le U_j < V_j \le N$ ($1 \le j \le M$) * $(U_i, V_i) \neq (U_j, V_j)$ ($1 \le i < j \le M$) * $1 \le Q \le 400\,000$ * $1 \le X_k \le 400\,000$ ($1 \le k \le Q$) * $X_k \le N(N - 1) \div 2 - M$ ($1 \le k \le Q$) * 输入的所有值都是整数。 ### 子任务 1. (4 分) $N \le 50$, $M \le 50$, $Q \le 50$, $X_k \le 50$ ($1 \le k \le Q$). 2. (9 分) $B_i = 1$ ($1 \le i \le N$), $M = 0$, $Q = 1$. 3. (10 分) $B_i = 1$ ($1 \le i \le N$), $Q = 1$. 4. (5 分) $B_i = 1$ ($1 \le i \le N$). 5. (29 分) $N \le 100\,000$, $M \le 100\,000$, $Q = 1$, $X_1 = 1$. 6. (14 分) $N \le 100\,000$, $M \le 100\,000$, $Q = 1$, $X_1 \le 100\,000$. 7. (18 分) $N \le 100\,000$, $M \le 100\,000$, $Q \le 100\,000$, $X_k \le 100\,000$ ($1 \le k \le Q$). 8. (11 分) 没有额外的限制。