Một nhà hàng chuyên phục vụ các món ăn Bolivia có \(N\) đầu bếp, được đánh số từ \(1\) đến \(N\). Đầu bếp \(i\) (\(1 \le i \le N\)) có thể nấu món silpancho với độ ngon \(A_i\) và món pique macho với độ ngon \(B_i\).

Tuy nhiên, các đầu bếp rất có chính kiến nên có \(M\) cặp đầu bếp không hòa thuận với nhau. Cặp không hòa thuận thứ \(j\) (\(1 \le j \le M\)) gồm đầu bếp \(U_j\) và đầu bếp \(V_j\).

Khách đến nhà hàng dùng bữa theo cách sau:

• Chọn hai số nguyên \(p, q\) thỏa mãn \(1 \le p < q \le N\), rồi nhờ cặp đầu bếp \(p\) và \(q\) nấu ăn. Không được chọn một cặp đầu bếp không hòa thuận với nhau.
• Với mỗi món silpancho và pique macho, người nấu là đầu bếp có thể nấu món đó với độ ngon cao hơn trong hai đầu bếp \(p\) và \(q\). Nếu cả hai nấu một món ngon như nhau thì một trong hai người sẽ nấu món đó. Lưu ý rằng một đầu bếp có thể nấu cả hai món.
• Mức độ hài lòng của khách là tổng độ ngon của món silpancho và món pique macho.

Có \(Q\) khách đến nhà hàng, được đánh số từ \(1\) đến \(Q\).

Khách \(k\) (\(1 \le k \le Q\)) chọn cặp đầu bếp mang lại mức độ hài lòng cao thứ \(X_k\) trong số các cặp được phép chọn. Cụ thể, gọi mức độ hài lòng là \(S\), khách chọn cặp đầu bếp \(p\) và \(q\) (\(1 \le p < q \le N\)) có giá trị \(S \times N^2 + p \times N + q\) lớn thứ \(X_k\).

Cho thông tin về các đầu bếp và khách, hãy tính mức độ hài lòng của từng khách \(k\) (\(1 \le k \le Q\)).

Dữ liệu vào

Dữ liệu vào có dạng:

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

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa mức độ hài lòng của khách \(k\).

Ràng buộc

• \(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)/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)/2-M\) (\(1 \le k \le Q\)).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Chấm điểm

1. 4 điểm: \(N \le 50\), \(M \le 50\), \(Q \le 50\), \(X_k \le 50\) (\(1 \le k \le Q\)).
2. 9 điểm: \(B_i=1\) (\(1 \le i \le N\)), \(M=0\), \(Q=1\).
3. 10 điểm: \(B_i=1\) (\(1 \le i \le N\)), \(Q=1\).
4. 5 điểm: \(B_i=1\) (\(1 \le i \le N\)).
5. 29 điểm: \(N \le 100\,000\), \(M \le 100\,000\), \(Q=1\), \(X_1=1\).
6. 14 điểm: \(N \le 100\,000\), \(M \le 100\,000\), \(Q=1\), \(X_1 \le 100\,000\).
7. 18 điểm: \(N \le 100\,000\), \(M \le 100\,000\), \(Q \le 100\,000\), \(X_k \le 100\,000\) (\(1 \le k \le Q\)).
8. 11 điểm: Không có ràng buộc bổ sung.

Ví dụ

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

Nguồn

Bản dịch tiếng Việt từ đề gốc tiếng Nhật của bài Intimate Chef, JOI 2024/2025, vòng loại thứ hai, bài 4 của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch được cung cấp theo giấy phép CC BY-SA 4.0.