Directed Graph Shortest Path with Energy Constraints

You are given an integer n and an array a of length n along with a constant c. Consider a complete directed graph G with n vertices (numbered 1 through n). For every ordered pair of distinct vertices i and j, the directed edge from i to j has a non‐negative weight defined by

$w(i,j)=a_i-2a_j+c$

It is guaranteed that all edge weights are non‐negative. You are then given q queries. In each query, you are given a set of vertices S. Your task is to find the minimum possible total weight among simple paths in G that pass through every vertex in S (the path may include vertices not in S at most once). A simple path is one which does not visit any vertex more than once. Print the total weight of such a path.

Explanation. Suppose the chosen path has vertices \(p_1, p_2, \dots, p_k\) (with \(k\ge 1\)). Its total weight is

$\sum_{i=1}^{k-1} \left(a_{p_i}-2a_{p_{i+1}}+c\right)=2a_{p_1}-\sum_{i=1}^{k}a_{p_i}+(k-1)c$.

Your goal is to choose a set of vertices \(X\) (with \(S\subseteq X\subseteq\{1, 2, \dots, n\}\)) and an ordering \(p_1, p_2, \dots, p_{|X|}\) of them so that the expression

$f(X)=2\min_{x\in X}a_x-\sum_{x\in X}a_x+(|X|-1)c$

is minimized. Note that when \(|S|=1\) a trivial one-vertex path is allowed with cost 0.

Input/Output specifications follow.

inputFormat

The first line contains two integers n and c (\(1\le n\le N\), \(0\le c\le 10^9\)).

The second line contains n integers: a₁, a₂, ..., a_n.

The third line contains an integer q, the number of queries.

Each query is given in the following format: The first integer k is the size of the required vertex set, followed by k distinct integers denoting the vertices in the set S (1-indexed).

outputFormat

For each query, output a single integer: the minimum total weight of a simple path that visits every vertex in S. If \(|S|=1\), output 0.

sample

3 5
10 7 12
2
1 1
2 1 3

0
-5

</p>