Problem Description

You are given $N$ numbers $- v_1, v_2, \cdots, v_N$, and an integer $A$. You can do an unlimited number of swaps in the array by swapping $v_i$ and $v_{i+1}$ for a cost of $v_i + v_{i+1}$. The new array after the swap would then be $v_1, \cdots , v_{i+1}, v_i \cdots, v_N$. For a certain number $R$, your task it to find the minimum sum of the costs of your swaps and $(v_1 + v_2 + \cdots + v_R) \times A$. Given $Q$ queries and an $R_i$ for each of them, find the minimum cost you can achieve for each query. All queries are independent.

Input Format

There are 3 integers on the first line: $N$ – the size of the array, $Q$ – the number of queries and $A$ – the coefficient $(v_1 + v_2 + \cdots + v_R)$ is multiplied by. The second line of the input contains $N$ positive integers $v_1, \cdots, v_N$ - the starting array. The last line holds the positive integers $R_1, \cdots, R_Q$.

Output Format

On each of the $Q$ lines output the minimum cost for the corresponding query.

4 1 5
4 1 2 3
2

25

4 1 6
4 1 2 3
2

29

Hint

Explanation of the examples

Example 1: It is optimal to not swap any elements. The cost is then $(4 + 1) \times 5 = 25$.

Example 2: We can first swap $4$ with $1$ and then $4$ with $2$:

4 1 2 3

1 4 2 3

1 2 4 3

The costs of the swaps are $4 + 1 = 5$ and $4 + 2 = 6$. Therefore, the total cost is

Constraints

• $1 \le Q, R_i \le N$
• $1 \le v_i, A \le 10^6$

Subtasks