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

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

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

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

1. 首先，选择 $2N$ 个地点中的一个作为起点，并移动至该地点。若选择地点 $i$（$1\le i\le 2N$），则需要支付参与费用 $C_i$。
2. 接着，他可以指令主办方交换相邻的印章台。具体来说，可以交换道路 $2N$ 和 $1$ 的印章台，或者交换道路 $i-1$ 和 $i$ 的印章台（$2\le i\le 2N$）。每次交换需花费 $X$，JOI 君可以执行任意多次的交换（包括零次）。交换操作会在指令下达后立即执行。但为了防止作弊，不允许交换跨越 JOI 君所选起点的印章台。即：
   • 若起点为地点 $1$，则禁止交换道路 $2N$ 和 $1$ 的印章台。
   • 若起点为地点 $i$（$2\le i\le 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\le q\le 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$
• $⋮$
• $K_Q$

输出格式

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

输入 #1

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

输出 #1

3
4

explanation

考虑 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

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

输出 #2

7

explanation

考虑 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

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

输出 #3

1
18
3
10
1
1

explanation

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

数据范围

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

子任务

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