친밀한 셰프

문제

어느 볼리비아 요리 레스토랑에서는 $1$ 부터 $N$ 까지 번호가 붙은 $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$ 중 맛있음이 더 높은 것을 만들 수 있는 셰프가 만든다. 어떤 요리에 대해 두 사람이 같은 맛있음의 요리를 만들 수 있을 때는, 둘 중 한 명의 셰프가 만든다. 한 명의 셰프가 두 요리를 모두 만드는 것도 가능하다는 점에 주의하라.
• 손님의 만족도는 실판초의 맛있음과 피케 마초의 맛있음의 합이다.

이 레스토랑에 $1$ 부터 $Q$ 까지 번호가 붙은 $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$) 의 만족도를 구하는 프로그램을 작성하시오.

제한

• $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$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 주어진다.
$N$ $M$ $Q$
$A_{1}$ $A_{2}$ $\dots$ $A_{N}$
$B_{1}$ $B_{2}$ $\dots$ $B_{N}$
$U_{1}$ $V_{1}$
$U_{2}$ $V_{2}$
$:$
$U_{M}$ $V_{M}$
$X_{1}$ $X_{2}$ $\dots$ $X_{Q}$

출력

$Q$ 줄로 출력한다. $k$ 번째 줄 ($1 \le k \le Q$) 에는 손님 $k$ 의 만족도를 출력한다.

예제 입력 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

요리를 만들어 달라고 의뢰할 수 있는 셰프의 조는 $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

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

예제 출력 2

6

요리를 만들어 달라고 의뢰할 수 있는 셰프의 조는 $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$ 의 제약을 만족한다.

예제 입력 3

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

예제 출력 3

9
7
7
10

이 예제는 서브태스크 $1,7,8$ 의 제약을 만족한다.

예제 입력 4

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

예제 출력 4

121
169
129
174
169
137
183
148
169
183

이 예제는 서브태스크 $1,7,8$ 의 제약을 만족한다.