페이지가 로드되지 않나요? 여기를 눌러보면 고쳐질 수도 있어요.
Placeholder

#8231
서브태스크

볼리비아 셰프 3초 1024MB

문제

볼리비아 요리 레스토랑에서는 1부터 N까지 번호가 붙여진 N명의 셰프가 일하고 있습니다. 셰프 i (1 ≦ i ≦ N)는 맛이 A_i인 실판초와 맛이 B_i인 피케마초를 만들 수 있습니다.

하지만 셰프들은 고집이 세서 사이가 안 좋은 2인 조합이 M개 있습니다. 사이가 안 좋은 2인 조합의 j번째 (1 ≦ j ≦ M)는 셰프 U_j와 셰프 V_j의 2인 조합입니다.

이 레스토랑에 오는 손님은 다음과 같이 요리를 먹습니다.

1 ≦ p < q ≦ N을 만족하는 정수 p, q를 선택하고, 셰프 p와 셰프 q의 2인 조합에 요리를 만들도록 의뢰합니다. 단, 사이가 안 좋은 2인 조합에 요리를 의뢰할 수는 없습니다. 실판초와 피케마초 각각의 요리는 셰프 p와 셰프 q 중 맛이 더 높은 셰프가 만듭니다. 만약 두 셰프가 같은 맛의 요리를 만들 수 있다면, 둘 중 하나가 만듭니다. 한 명의 셰프가 두 가지 요리를 모두 만들 수 있다는 점에 유의하십시오. 손님의 만족도는 실판초의 맛과 피케마초의 맛 합계입니다. 이 레스토랑에는 1부터 Q까지 번호가 붙여진 Q명의 손님이 방문합니다.

손님 k (1 ≦ k ≦ Q)는 요리를 만들 수 있는 2인 조합 중, 만족도가 X_k번째로 높은 2인 조합에 요리를 의뢰하고자 합니다. 구체적으로 만족도를 S로 정의하며, S × N^2 + p × N + q가 X_k번째로 높은 셰프 p와 셰프 q (1 ≦ p < q ≦ N)의 2인 조합에 요리를 의뢰합니다.

레스토랑의 셰프와 손님의 정보가 주어졌을 때, 손님 k (1 ≦ k ≦ Q)의 만족도를 구하는 프로그램을 작성하세요.


입력

입력은 아래와 같은 형식으로 주어진다.

N\ M\ Q

A_1\ A_2\ …\ A_N

B_1\ B_2\ …\ B_N

U_1\ V_1

U_2\ V_2

:

U_M\ V_M

X_1\ X_2\ …\ X_Q

[제약 조건]

  • 2 ≦ N ≦ 400, 000

  • 1 ≦ A_i ≦ 10^9 (1 ≦ i ≦ N)

  • 1 ≦ B_i ≦ 10^9 (1 ≦ i ≦ N)

  • 0 ≦ M ≦ 400, 000

  • M < N(N - 1)÷2

  • 1 ≦ U_j < V_j ≦ N (1 ≦ j ≦ M)

  • (U_i, V_i) ≠ (U_j, V_j) (1 ≦ i < j ≦ M)

  • 1 ≦ Q ≦ 400, 000

  • 1 ≦ X_k ≦ 400, 000 (1 ≦ k ≦ Q)

  • X_k ≦ N(N - 1)÷2 - M (1 ≦ k ≦ Q)


출력

Q 행에 걸쳐 k 번째 행 (1 ≦ k ≦ Q)에는 손님 k의 만족도를 출력하시오.


부분문제

번호 점수 조건
#14점

N ≦ 50，M ≦ 50，Q ≦ 50，X_k ≦ 50\ (1 ≦ k ≦ Q)

#29점

B_i = 1\ (1 ≦ i ≦ N)，M = 0，Q = 1

#310점

B_i = 1\ (1 ≦ i ≦ N)，Q = 1

#45점

B_i = 1\ (1 ≦ i ≦ N)

#529점

N ≦ 100 000，M ≦ 100 000，Q = 1，X_1 = 1

#614점

N ≦ 100 000，M ≦ 100 000，Q = 1，X_1 ≦ 100 000

#718점

N ≦ 100 000，M ≦ 100 000，Q ≦ 100 000，X_k ≦ 100 000\ (1 ≦ k ≦ Q)

#811점

추가 제약 조건 없음


예제1

입력
424
2735
4348
13
24
1234
출력
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

입력
431
3654
1111
12
23
24
1
출력
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

입력
504
12345
54321
39101
출력
9
7
7
10

예제4

입력
131210
2282860487763921371369187
8576415559266918335492261
29
813
711
911
812
512
47
1112
1012
411
15
38
492146132041633247
출력
121
169
129
174
169
137
183
148
169
183

출처

JOI 2025 예선2

역링크