题目描述

欧阳南德和上官琐艾经营着一家餐厅，这里有 $n$ 位厨师，编号从 $1$ 到 $n$。厨师 $i$ ($1 \le i \le n$) 可以制作美味度为 $a_i$ 的锡尔潘乔和美味度为 $b_i$ 的皮克马乔。

然而，这些厨师都有很强的个性，因此有 $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$) 两人组来制作料理。

欧阳南德和上官琐艾想请你帮忙计算每位顾客的满意度。

输入格式

第一行给出三个整数 $n,m,q$。

第二行给出 $n$ 个整数 $a_i$。

第三行给出 $n$ 个整数 $b_i$。

接下来的 $m$ 行，每行给出两个整数 $u_i$ 和 $v_i$。

最后一行给出 $q$ 个整数 $x_i$。

输出格式

输出 $q$ 行，第 $k$ 行输出第 $k$ 个顾客的满意度。

样例 #1

输入 #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

输入 #2

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

输出 #2

6

样例 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$。

样例 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$。

数据范围

• $2 \le n \le 400\,000$，$0 \le m \le 400\,000$，$1 \le q \le 400\,000$；
• $1 \le a_i,b_i \le 10^9$；
• $m < \frac{n(n - 1)}{2}$，$1 \le u_j < v_j \le n$。对于 $i\neq j$，$(u_i, v_i) \neq (u_j, v_j)$；
• $1 \le x_k \le 400\,000$，$x_k \le \frac{n(n - 1)}{2} - m$；

• 特殊性质 A：保证 $\forall i\in [1,n],b_i=1$；
• 特殊性质 B：保证 $m=0$；
• 特殊性质 C：保证 $q=1$；
• 特殊性质 D：保证 $x_1=1$；
• 特殊性质 E：保证 $x_1\le 10^5$；
• 特殊性质 F：保证 $\forall i\in [1,n],x_i\le 10^5$。
• 特殊性质 G：保证 $\forall i\in [1,n],x_i\le 50$。