题目背景

本题测试点极大，评测时可能需要等待较长时间加载测试点。

题目描述

在湖泊周围，有 $2N$ 个均匀分布的地点，按顺时针方向编号为 $1$ 到 $2N$。此外，还有 $2N$ 条单向道路连接相邻的地点。道路 $i$（$1 \leq i \leq 2N - 1$）从地点 $i$ 通往地点 $i+1$，而道路 $2N$ 从地点 $2N$ 通往地点 $1$。每条道路的中点处设有一个印章台。

共有 $N$ 种颜色的印章，编号为 $1$ 到 $N$。在道路 $i$（$1 \leq i \leq 2N$）的印章台上可以获得的印章颜色为 $A_i$。对于每种颜色 $j$（$1 \leq j \leq N$），恰好有 $2$ 个印章台提供该颜色的印章。

JOI 君携带了多张集章卡参加比赛。每张集章卡有左、右两个空格，可以加盖印章。每个空格最多加盖一枚印章。初始时，所有集章卡均为空白。

JOI 君参加集章拉力赛的流程如下：

1. 首先，选择 $2N$ 个地点中的一个作为起点，并移动至该地点。若选择地点 $i$（$1 \leq i \leq 2N$），则需要支付参与费用 $C_i$。
2. 接着，他可以指令主办方交换相邻的印章台。具体来说，可以交换道路 $2N$ 和 $1$ 的印章台，或者交换道路 $i-1$ 和 $i$ 的印章台（$2 \leq i \leq 2N$）。每次交换需花费 $X$，JOI 君可以执行任意多次的交换（包括零次）。交换操作会在指令下达后立即执行。但为了防止作弊，不允许交换跨越 JOI 君所选起点的印章台。即：
   • 若起点为地点 $1$，则禁止交换道路 $2N$ 和 $1$ 的印章台。
   • 若起点为地点 $i$（$2 \leq i \leq 2N$），则禁止交换道路 $i-1$ 和 $i$ 的印章台。
3. 此后，JOI 君从所选起点出发，按顺时针方向依次访问 $2N$ 个印章台。访问印章台时，他可以任意次地在该台为集章卡盖章。同一张卡可以在同一台同时加盖左、右两格。但每张集章卡必须先在左空格盖章，之后才能在右空格盖章，即若某卡的左空格未盖章，则不能在该卡的右空格盖章。

JOI 君想要收集尽可能多不同类型的已盖章卡。定义盖章卡 $(a, b)$ 为左空格为颜色 $a$、右空格为颜色 $b$ 的集章卡。

当且仅当 $a_1 = a_2$ 且 $b_1 = b_2$ 时，盖章卡 $(a_1, b_1)$ 和 $(a_2, b_2)$ 被视为同一种类型。

由于共有 $N$ 种颜色，因此总共有 $N^2$ 种可能的盖章卡类型。

有 $Q$ 个查询。第 $q$ 个查询（$1 \leq q \leq Q$）的内容如下：

• 若要使得 JOI 君在拉力赛结束时收集到至少 $K_q$ 种类型的盖章卡，所需的最小总成本是多少？

可以证明，在给定的约束条件下，JOI 君总能通过足够大的成本收集到至少 $K_q$ 种类型的盖章卡。

编程回答 JOI 君的 $Q$ 个查询。

输入格式

$N$ $X$
$A_1$ $A_2$ $\cdots$ $A_{2N}$
$C_1$ $C_2$ $\cdots$ $C_{2N}$
$Q$
$K_1$
$K_2$
$\vdots$
$K_Q$

输出格式

输出 $Q$ 行，其中第 $q$ 行（$1 \leq q \leq Q$）包含收集至少 $K_q$ 种类型盖章卡所需的最小总成本。

3 2
1 2 2 3 1 3
6 1 4 5 4 7
2
8
9

3
4

8 1
1 2 6 1 6 3 8 4 5 5 3 4 7 2 7 8
4 5 3 6 2 9 1 4 6 3 8 5 2 9 4 7
1
64

7

9 4
4 3 5 3 8 1 5 8 1 7 6 2 4 9 6 9 2 7
12 9 4 8 7 1 20 5 8 7 4 13 5 9 10 3 7 8
6
39
81
73
79
64
52

1
18
3
10
1
1

提示

样例 $1$ 解释

考虑 JOI 君选择地点 $2$ 作为起点，并指令交换道路 $3$ 和 $4$ 上印章台的情况：

• JOI 君支付的总成本为 $C_2 + X \times 1 = 3$。
• JOI 君按道路 $2\to 3\to 4\to 5\to 6\to 1$ 的顺序访问印章台，各台可获得的印章颜色依次为 $2,3,2,1,3,1$。
• JOI 君可收集的双空格盖章卡类型数为 $8$ 种。 ◦ 例如，要获得左格为颜色 $3$、右格为颜色 $1$ 的盖章卡，JOI 君可在道路 $3$ 的台加盖左格，在道路 $1$ 的台加盖右格。 ◦ 但需注意，无法获得左格为颜色 $1$、右格为颜色 $2$ 的盖章卡。

由于无法以 $2$ 或更低的成本获得 $8$ 种及以上类型的盖章卡，输出的第一行应为 $3$。

此外，若 JOI 君选择地点 $3$ 作为起点且不进行任何印章台交换，他可获得 $9$ 种类型的盖章卡：

• 此时 JOI 君支付的总成本为 $C_3 + X \times 0 = 4$。由于无法以 $3$ 或更低的成本获得 $9$ 种及以上类型的盖章卡，输出的第二行应为 $4$。

该样例满足子任务 $1,4,6$ 的限制。

样例 $2$ 解释

考虑 JOI 君选择地点 $10$ 作为起点，并按以下顺序交换印章台：

1. 交换道路 $15$ 和 $16$ 的印章台；
2. 交换道路 $2$ 和 $3$ 的印章台；
3. 交换道路 $16$ 和 $1$ 的印章台；
4. 交换道路 $1$ 和 $2$ 的印章台。

此时 JOI 君可获得 $64$ 种类型的盖章卡，支付的总成本为 $C_{10} + X \times 4 = 7$。

该样例满足子任务 $2\sim 6$ 的限制。

样例 $3$ 解释

该样例满足子任务 $4,6$ 的限制。

数据范围

• $2 \leq N \leq 500\,000$。
• $1 \leq X \leq 500\,000$。
• $(A_1, A_2, \ldots, A_{2N})$ 是 $(1, 1, 2, 2, \ldots, N, N)$ 的一个排列。
• $1 \leq C_i \leq 10^{18}$（$1 \leq i \leq 2N$）。
• $1 \leq Q \leq 500\,000$。
• $1 \leq K_q \leq N^2$（$1 \leq q \leq Q$）。
• 所有输入值为整数。

子任务

• $\text{Subtask 1 (5 pts)}$：$N \leq 4$。
• $\text{Subtask 2 (20 pts)}$：$N \leq 5000$，$Q = 1$，$K_1 = N^2$。
• $\text{Subtask 3 (20 pts)}$：$N \leq 5000$，$Q = 1$。
• $\text{Subtask 4 (19 pts)}$：$N \leq 5000$。
• $\text{Subtask 5 (21 pts)}$：$Q = 1$。
• $\text{Subtask 6 (15 pts)}$：无额外限制。