题目描述

在某家玻利维亚餐厅，有 $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$) 的满意度。

输入格式

输入按照如下格式给出：

$$\begin{aligned} &N\ M\ Q\\ &A_1\ A_2\ \ldots\ A_N\\ &B_1\ B_2\ \ldots\ B_N\\ &U_1\ V_1\\ &U_2\ V_2\\ &\vdots\\ &U_M\ V_M\\ &X_1\ X_2\ \ldots\ X_Q\\ \end{aligned} $$

输出格式

输出 $Q$ 行。第 $k$ 行 ($1 \le k \le Q$) 输出顾客 $k$ 的满意度。

4 2 4
2 7 3 5
4 3 4 8
1 3
2 4
1 2 3 4

13
13
11
11

4 3 1
3 6 5 4
1 1 1 1
1 2
2 3
2 4
1

6

5 0 4
1 2 3 4 5
5 4 3 2 1
3 9 10 1

9
7
7
10

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

121
169
129
174
169
137
183
148
169
183

提示

样例 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 分) 没有额外的限制。