Background

Problem Description

Brief Statement

You are given a sequence $a$ of length $n$ and a constant $c$. Construct a complete directed graph $G$ with $n$ vertices such that the length of edge $i \to j$ ($i \neq j$) is $a_i - 2 a_j + c$, and it is guaranteed that all edge weights are non-negative.

Then there are $q$ queries. In each query, a set of vertices is given. Please find a shortest simple path in graph $G$ that visits all vertices in the set, and output its length.

---

Original Statement

Merry had a dream in which she traveled into the Bamboo Forest of the Lost in Gensokyo. After waking up, she hoped to cross the boundary again together with Renko and enter Gensokyo once more.

However, this time, she saw $n$ worlds. In the $i$-th world, the boundary strength is $a_i$. Between every pair of worlds, there is a passage connecting them, and Renko and Merry travel between worlds through these passages.

To avoid missing the world where Gensokyo is located, every time they arrive at a world, they will cross its boundary. Starting from the $i$-th world, going through a passage, and then crossing the boundary to enter the $j$-th world requires spiritual energy of $a_i - 2 a_j + c$ (it is guaranteed to be non-negative). Here, $c$ is a constant, representing the extra spiritual energy cost that Merry needs each time she crosses a boundary. Note that this also means that the spiritual energy cost from world $i$ to world $j$ and from world $j$ to world $i$ may be different.

In order to find Gensokyo efficiently, they will ask you $q$ queries. In each query, a set is given, representing the worlds they want to enter. Since there are many worlds, they want to save spiritual energy. Therefore, they want you to find, among all simple paths that contain all these worlds (i.e., the same passage between worlds will not be traversed more than once), the path with the minimum total spiritual energy cost. You only need to tell them what this minimum total cost is.

Input Format

• The first line contains three integers $n, c, q$.
• The second line contains $n$ integers representing the sequence $a$.
• The next $q$ lines: each line starts with an integer $|S|$, the size of set $S$, followed by $|S|$ distinct integers representing set $S$.

Output Format

• Output $q$ lines in total. Each line contains one integer, the answer to the corresponding query.

5 20 3
7 4 2 5 9
2 1 4
3 1 2 3
4 1 4 2 5

11
24
34

10 928698067 3
331485039 15480787 61584781 252174726 472089427 95998831 252561792 118119945 315548522 24453837
4 9 1 10 2
5 10 6 1 5 8
1 5

1798602551
2249463436
0

Hint

Sample Explanation

Sample #1

The edge weights between every two vertices are shown in the figure. To make it easier for contestants to observe, the color of each edge weight matches the color of its corresponding edge.

For the first query, a path $4 \to 1$ can be found; for the second query, a path $3 \to 2 \to 1$ can be found; for the third query, a path $2 \to 4 \to 1 \to 5$ can be found. It can be proven that these three solutions are optimal for their respective queries.

Sample #2

This sample satisfies the constraints of $\textbf{Subtask 1}$.

Constraints

This problem uses bundled testdata.

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|c|c|c|c|}\hline \textbf{Subtask} & \textbf{\textsf{分值}} & \bm{n\le } & \bm{q\le} & \bm{\sum |S|\le} & \textbf{\textsf{特殊性质}}&\textbf{Subtask \textsf{依赖}}\cr\hline 1 & 30 & 10 & 10 & 10 & - &-\cr\hline 2 & 20 & 10^5 & 10^5 & 10^5 & \mathbf{A}&- \cr\hline 3 & 20 & 10^5 & 10^5 & 10^5 & \mathbf{B}&- \cr\hline 4 & 30 & 10^6 & 10^6 & 10^6& -&1,2,3 \cr\hline \end{array}$$

• Special property $\bf A$: $a_i$ is monotonically increasing.
• Special property $\bf B$: all $a_i$ are equal.

For $100\%$ of the data, it is guaranteed that $1 \leq S_i \leq n \leq 10^6$, $1 \leq \sum |S|, q \leq 10^6$, and $1 \le a_i, c \le 10^9$.

Translated by ChatGPT 5