JOI-kun 居住在 IOI 之国，这个国家以其巨大的湖泊而闻名。今天，湖边将举行一场集邮拉力赛。

湖周围有 $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-kun 携带了许多邮戳卡参加集邮拉力赛。每张邮戳卡有两个空格，左侧和右侧，可以用来盖邮戳。每个空格最多只能盖一个邮戳。最初，所有的邮戳卡都是空白的。

JOI-kun 的集邮拉力赛过程如下：

1. 首先，他选择 $2N$ 个地点中的一个作为起点并前往该处。如果他选择地点 $i$ ($1 \le i \le 2N$)，他必须支付 $C_i$ 的参与费用。
2. 接下来，他可以指示赛事组织者交换相邻的邮戳站。具体来说，他可以交换道路 $2N$ 和道路 $1$ 上的邮戳站，或者交换道路 $i-1$ 和道路 $i$ 上的邮戳站（对于任意 $2 \le i \le 2N$）。每次交换的费用为 $X$，JOI-kun 可以发出任意多次交换指令，也可以不进行交换。交换在指令发出后立即执行。然而，为了防止作弊，不允许交换跨越 JOI-kun 所选起点的邮戳站。也就是说，如果他从地点 $1$ 出发，则禁止交换道路 $2N$ 和道路 $1$ 上的邮戳站。如果他从地点 $i$ ($2 \le i \le 2N$) 出发，则禁止交换道路 $i-1$ 和道路 $i$ 上的邮戳站。
3. 此后，JOI-kun 从他选择的地点出发，顺时针移动，依次访问 $2N$ 个邮戳站。在访问邮戳站时，他可以根据需要多次将邮戳盖在邮戳卡上。他也可以在同一个邮戳站将邮戳同时盖在同一张卡的左侧和右侧空格上。但是，对于每张邮戳卡，他必须始终先盖左侧空格，再盖右侧空格；也就是说，如果该邮戳卡的左侧空格仍为空，则他不能盖右侧空格。

JOI-kun 希望收集多种不同类型的、在两个空格上都盖有邮戳的邮戳卡。设盖有邮戳的卡片 $(a, b)$ 为左侧盖有颜色 $a$ 的邮戳、右侧盖有颜色 $b$ 的邮戳的卡片。两张盖有邮戳的卡片 $(a_1, b_1)$ 和 $(a_2, b_2)$ 被视为同一种类型，当且仅当 $a_1 = a_2$ 且 $b_1 = b_2$。由于共有 $N$ 种颜色的邮戳，总共有 $N^2$ 种可能的盖有邮戳的卡片类型。

你需要回答 $Q$ 个查询来帮助 JOI-kun。第 $q$ 个查询 ($1 \le q \le Q$) 如下：

• JOI-kun 在拉力赛结束时收集至少 $K_q$ 种类型的盖有邮戳的卡片所需的最低总成本是多少？可以证明，在给定的约束条件下，通过支付足够高的成本，JOI-kun 总能收集到至少 $K_q$ 种类型的盖有邮戳的卡片。

给定关于邮戳颜色、参与费用、交换费用和查询的信息，编写一个程序来回答 JOI-kun 的 $Q$ 个查询。

输入格式

从标准输入读取以下数据。

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

输出格式

向标准输出写入 $Q$ 行，其中第 $q$ 行 ($1 \le q \le Q$) 包含收集至少 $K_q$ 种类型的盖有邮戳的卡片所需的最低总成本。

数据范围

• $2 \le N \le 500\,000$。
• $1 \le X \le 500\,000$。
• $(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 500\,000$。
• $1 \le K_q \le N^2$ ($1 \le q \le Q$)。
• 给定值均为整数。

子任务

1. (5 分) $N \le 4$。
2. (20 分) $N \le 5000, Q = 1, K_1 = N^2$。
3. (20 分) $N \le 5000, Q = 1$。
4. (19 分) $N \le 5000$。
5. (21 分) $Q = 1$。
6. (15 分) 无附加约束。

样例

样例输入 1

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

样例输出 1

3
4

样例输入 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

样例输入 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