配点: 100 点
問題文
在一家玻利维亚餐厅 编号至 1 它们的编号最大为 N 编号最多为 N 厨师在那里工作。厨师 i (1 \leqq i \leqq N) 是美味是 A_i Silpancho 和美味 您可以制作一个 B_i 的 piquemacho。
然而,厨师很挑剔,和他相处得不好。 2 一群人 M 组。关系不好 2 人类组 j 番目 (1 \leqq j \leqq M) 是一名厨师 U_j 和厨师 V_j 的 2 这是一群人。
来这家餐厅的顾客吃的食物如下。 选择
- 1 \leqq p < q \leqq N 的整数只有 p, q ,厨师 p 和厨师 q 的 2 请一群人做饭。然而我们关系并不好 2 你不能要求一群人为你做饭。
- Silpancho和Piquemacho的每道菜都是由厨师准备的。 p 和厨师 q 是由一位能做出最美味的厨师制作的。关于某道菜 2 当两个人能做出一道味道一样的菜时,选哪一个? 1 由厨师制作。1 厨师 2 请注意,也可以制作两道菜。
- 客户的満足度是Silpancho的美味和Piquemacho的美味的总和。
在这家餐厅 1 它们的编号最大为 Q 编号最多为 Q 店里来了很多顾客。
客 k (1 \leqq k \leqq Q)可以要求做饭。 2 在各组中,满意度为 X_k 最高 2 我请了一群人给我做饭。具体来说,满意 作为 S ,S \times N^2 + p \times N + q 是 X_k 最高厨师 p 和厨师 q (1 \leqq p < q \leqq N)的 2 我请了一群人给我做饭。
给定有关餐厅厨师和顾客的信息, 编写一个程序来查找 k (1 \leqq k \leqq Q的满意度。
制約
- 2 \leqq N \leqq 400\,000.
- 1 \leqq A_i \leqq 10^9 (1 \leqq i \leqq N).
- 1 \leqq B_i \leqq 10^9 (1 \leqq i \leqq N).
- 0 \leqq M \leqq 400\,000.
- M < \frac{N(N - 1)}{2}.
- 1 \leqq U_j < V_j \leqq N (1 \leqq j \leqq M).
- (U_i, V_i) \neq (U_j, V_j) (1 \leqq i < j \leqq M).
- 1 \leqq Q \leqq 400\,000.
- 1 \leqq X_k \leqq 400\,000 (1 \leqq k \leqq Q).
- X_k \leqq \frac{N(N - 1)}{2} - M (1 \leqq k \leqq Q).
- 所有输入值都是整数。
小課題
- (4 点) N \leqq 50,M \leqq 50,Q \leqq 50,X_k \leqq 50 (1 \leqq k \leqq Q).
- (9 点) B_i = 1 (1 \leqq i \leqq N),M = 0,Q = 1.
- (10 点) B_i = 1 (1 \leqq i \leqq N),Q = 1.
- (5 点) B_i = 1 (1 \leqq i \leqq N).
- (29 点) N \leqq 100\,000,M \leqq 100\,000,Q = 1,X_1 = 1.
- (14 点) N \leqq 100\,000,M \leqq 100\,000,Q = 1,X_1 \leqq 100\,000.
- (18 点) N \leqq 100\,000,M \leqq 100\,000,Q \leqq 100\,000,X_k \leqq 100\,000 (1 \leqq k \leqq Q).
- (11 点)没有额外的限制。 在
入力
输入按以下格式给出。 输出
N M Q A_1 A_2 \cdots A_N B_1 B_2 \cdots B_N U_1 V_1 U_2 V_2 \vdots U_M V_M X_1 X_2 \cdots X_Q
出力
Q 行输出。k 行目 (1 \leqq k \leqq 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
可以被要求准备菜肴的厨师。 2 人类群体是 4 有两种方法,每种方法的客户满意度如下。
- 厨师 当你选择 1 和厨师 2 时,Silpancho就成为一名厨师。 由 2 创建,Piquemacho 是一名厨师 由 1 创建。因此,Silpancho的美味在于 7 Piquemacho的美味在于 4 变为。因此,顾客满意度是 7 + 4 = 11 。 在
- 厨师 当你选择 1 和厨师 4 时,Silpancho就成为一名厨师。 由 4 创建,Piquemacho 是一名厨师 由 4 创建。因此,Silpancho的美味在于 5 Piquemacho的美味在于 8 变为。因此,顾客满意度是 5 + 8 = 13 。 在
- 厨师 当你选择 2 和厨师 3 时,Silpancho就成为一名厨师。 由 2 创建,Piquemacho 是一名厨师 由 3 创建。因此,Silpancho的美味在于 7 Piquemacho的美味在于 4 变为。因此,顾客满意度是 7 + 4 = 11 。 在
- 厨师 当你选择 3 和厨师 4 时,Silpancho就成为一名厨师。 由 4 创建,Piquemacho 是一名厨师 由 4 创建。因此,Silpancho的美味在于 5 Piquemacho的美味在于 8 变为。因此,顾客满意度是 5 + 8 = 13 。 在
因此,我们了解每个客户的以下信息。
- 客 1 是一名厨师 3 和厨师 4 的 2 我选择了一群人。因此,客户 1 的满意度为 它变成了 13 。
- 客 2 是一名厨师 1 和厨师 4 的 2 我选择了一群人。因此,客户 2 的满意度为 它变成了 13 。
- 客 3 是一名厨师 2 和厨师 3 的 2 我选择了一群人。因此,客户 3 的满意度为 它变成了 11 。
- 客 4 是一名厨师 1 和厨师 2 的 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
可以被要求准备菜肴的厨师。 2 人类群体是 3 有两种方法,每种方法的客户满意度如下。
- 厨师 当你选择 1 和厨师 3 时,Silpancho就成为一名厨师。 由 3 创建,Piquemacho 是一名厨师 由 1 卡厨师 3 创建。因此,Silpancho的美味在于 5 Piquemacho的美味在于 1 变为。因此,顾客满意度是 5 + 1 = 6 。 在
- 厨师 当你选择 1 和厨师 4 时,Silpancho就成为一名厨师。 由 4 创建,Piquemacho 是一名厨师 由 1 卡厨师 4 创建。因此,Silpancho的美味在于 4 Piquemacho的美味在于 1 变为。因此,顾客满意度是 4 + 1 = 5 。 在
- 厨师 当你选择 3 和厨师 4 时,Silpancho就成为一名厨师。 由 3 创建,Piquemacho 是一名厨师 由 3 卡厨师 4 创建。因此,Silpancho的美味在于 5 Piquemacho的美味在于 1 变为。因此,顾客满意度是 5 + 1 = 6 。 在
因此,客户 我们了解以下有关 1 的信息。
- 客 1 是一名厨师 3 和厨师 4 的 2 我选择了一群人。因此,客户 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 满足约束。