친밀한 셰프

식당에는 1부터 N까지 번호가 붙은 셰프 N명이 일한다. 셰프 i (1 ≤ i ≤ N)는 맛이 $A_i$인 실파초와 맛이 $B_i$인 피케마초를 만들 수 있다.

사이가 나쁜 셰프 2명의 조가 M개 있다. j번째 조 (1 ≤ j ≤ M)는 셰프 $U_j$와 셰프 $V_j$이다.

손님은 다음과 같이 음식을 먹는다.

• $1 \le p < q \le N$을 만족하는 정수 $p, q$를 고르고, 셰프 p와 셰프 q 두 명에게 요리를 부탁한다. 단, 사이가 나쁜 두 명에게는 부탁할 수 없다.
• 실파초와 피케마초는 각각 셰프 p와 셰프 q 중 맛을 더 높게 낼 수 있는 셰프가 만든다. 두 셰프가 같은 맛의 요리를 만들 수 있으면 둘 중 한 명이 만든다. 한 셰프가 두 요리를 모두 만드는 것도 가능하다.
• 손님의 만족도는 실파초 맛과 피케마초 맛의 합이다.

1부터 Q까지 번호가 붙은 손님 Q명이 방문한다. 손님 k (1 ≤ k ≤ Q)는 부탁할 수 있는 두 명의 조 가운데 만족도가 $X_k$번째로 높은 조에게 부탁한다. 구체적으로 만족도를 S라 하면, $S \times N^2 + p \times N + q$가 $X_k$번째로 큰 셰프 p와 셰프 q (1 ≤ p < q ≤ N)의 조에게 부탁한다.

셰프와 손님의 정보가 주어질 때, 손님 k (1 ≤ k ≤ Q)의 만족도를 구하라.

N M Q
A1 A2 … AN
B1 B2 … BN
U1 V1
U2 V2
:
UM VM
X1 X2 … XQ

Q개의 줄에 출력한다. k번째 줄 (1 ≤ k ≤ Q)에는 손님 k의 만족도를 출력한다.

• $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) \ne (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$).
• 입력되는 값은 모두 정수이다.