T426518 「YAC Round 5」秘神摩多罗

 > 究极的绝对秘神

秘神摩多罗隐岐奈拥有在任何事物上做出门扉程度的能力。现在有 $n$ 个世界，第 $i$ 个世界拥有一个结界强度 $a_i$。 各个世界 **两两之间都可以构建一个门** ，摩多罗隐岐奈可以通过构建两个世界之间的门来实现在世界之间来回穿梭。摩多罗隐岐奈从第 $i$ 个世界通往第 $j$ 个世界，需要消耗 $a_i - 2 \times a_j + c$ 的法力来构建一道门，其中 $c$ 为常数，且 **保证 $a_i - 2 \times a_j + c$ 是一个非负数**。 摩多罗隐岐奈需要尽可能地节省自己的法力来构建用于穿梭于世界之间的门。现在给出 $q$ 组询问，每组询问给出一个由若干互不相同的世界构成的 **集合**，表示摩多罗隐岐奈当前需要进入的所有世界。对于每组询问，你需要找到一个 **包含当前集合中所有世界**的 并且 消耗 **总法力值最小** 的简单路径。 简单路径：**经过所有点 且 路径上每条边只经过一次的路径**。对于本题来说就是 经过集合中所有世界 且 两个世界之间构建的门只会走一次 的一条路径。 对于每次询问，请你输出满足要求的简单路径的 **最小消耗总法力值** 。

第一行输入三个整数 $n,c,q$，其中 $n$ 表示世界总数，$c$ 表示题中的常数，$q$ 表示询问个数。 第二行输入 $n$ 个整数 $a_1, a_2, \ldots , a_n$，表示每个世界的结界强度。 接下来 $q$ 行。每行第一个整数 $|S|$，表示当前询问的集合大小，后面 $|S|$ 个互不相同的整数 $S_i$ 构成当前询问的集合。

输出 $q$ 行，每行一个整数，表示询问的答案。

#### 样例解释  每两个点之间的边权如图所示。为了便于选手观察，边权的颜色与它所对应的边的颜色相同。 对于第一个询问，可以找到路径 $4\to 1$ 消耗法力最少，总法力值消耗为 $11$； 对于第二个询问，可以找到路径 $3\to 2\to 1$ 消耗法力最少，总法力值消耗为 $14 + 10 = 24$； 对于第三个询问，可以找到路径 $2\to 4 \to 1\to 5$，总法力值消耗为 $14 + 11 + 9 = 34$。 #### 数据范围 $1 \leq n \leq 10^6$，$1 \le c \le 10^9$，$1 \le q \leq 10^6$， $1 \le a_i \le 10^9$， $1\leq \sum |S| \le 10^6$，$1 \le S_i \le n$ 。