配点: 100 点
JOI 您居住的 IOI 国家以其大湖而闻名。今天,湖边将举行集章比赛。
湖周围均匀分布 2N 点按顺时针方向排列 它们的编号最大为 1 减去 2N 。 另外,连接相邻点。 2N 书 有一条路径 一方通行 。 路 i (1\leqq i \leqq 2N-1) 是一个点 i 来点 i+1 是通往 2N 是一个点 这是通往 2N 来点 1 的道路。 在每条路的中间 1 安装了两个印章架。
邮票有 1 减去 N 最多 N 有颜色,有道路 i (1\leqq i \leqq 2N) 中间安装的印台上可印的印章颜色 A_i 。 每个 j (1\leqq j \leqq N),颜色 可以盖印 j 的印台就在 2 有一个。
JOI 你决定带着很多印章卡参加印章拉力赛。 每张邮票卡都有一个左、右 2 将打印一个框架,您可以在其中放置印记。 1 印章最多可以放置在一框中。 1 您可以按两次。 最初,任何邮票卡上都没有贴邮票。 JOI君在印章拉力赛上的行动如下。
- 首先作为起点 选择 2N 点之一并移动到该点。点 当您选择 i (1\leqq i \leqq 2N)作为起点时,JOI将支付参加印章拉力赛的费用。 C_i 。
- 接下来,JOI 可以指示运营公司更换安装在邻近道路上的盖章站。换句话说,路 更换 2N,1 中安装的印台或i (2\leqq i \leqq 2N) 您可以指示更换 i-1,i 中安装的印台。 JOI 发出指示时所付出的成本是 1 每次 X 在, 任意次数 您可以发出指令。也可以根本不发出任何指令。每次发出指令时都会立即执行更换印台。 然而,为了防止欺诈,无法交换跨越 JOI 选择的起点的印台。也就是说,JOI君以这个点为起点。 如果选择 1 ,则道路 更换安装在 2N,1 的印台 如果选择 i (2\leqq i \leqq 2N),路径 禁止更换安装在 i-1,i 的印台。
- 之后,JOI 从起点开始,顺时针移动。 按顺序访问2N 盖章站,返回起点后结束盖章集会。当JOI参观盖章摊位时,他可以在自己的盖章卡上盖上任意次数的印章。在同一个印台上 也可以在 1 印章卡的左侧和右侧盖章。但每张印章卡必须按左右顺序加盖印章。换句话说,您不能在左边空白的印章卡的右边盖章。
JOI 你想收集尽可能多类型的印章卡,左右框上都印有印章。 左边的颜色 a,右侧颜色 印有 b 的印章卡为印章卡。 令其表示为 (a,b) 。 这时,印章卡 (a_1, b_1) 和 按字典顺序比较 (a_2, b_2) 是a_1=a_2 和 b_1=b_2 ,只有这样,才被认为是同一类型。
N 因为有彩色邮票,所有左右框都有邮票的邮票卡 N^2 请注意,有不同的类型。
你是 JOI,可以帮助你制定策略。 您需要回答Q 问题。 q 個目 (1\leqq q \leqq Q) 的问题如下。
- 盖章活动结束后,将发放左右框均贴有盖章的盖章卡。 K_q 拥有多种类型必须支付的最低总成本是多少?注意,在这个问题的约束下,通过支付足够大的费用,就可以得到一张左右框都有印章的印章卡。 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\leqq q \leqq Q)是一张印章卡,在印章拉力赛结束时左右框上都印有印章。 K_q 输出为了拥有多种类型而必须支付的总成本的最小值。 这是一种
制約
- 2 \leqq N \leqq 500\,000.
- 1 \leqq X \leqq 500\,000.
- (A_1, A_2, \dots, A_{2N}) 是 您也可以写 (1, 1, 2, 2, \dots, N, N) 。
- 1 \leqq C_i \leqq 10^{18} (1 \leqq i \leqq 2N).
- 1 \leqq Q \leqq 500\,000.
- 1 \leqq K_q \leqq N^2 (1\leqq q \leqq Q).
- 所有输入值都是整数。
小課題
- (5 点) N\leqq 4.
- (20 点) N\leqq 5000,Q = 1,K_1=N^2.
- (20 点) N\leqq 5000,Q = 1.
- (19 点) N\leqq 5000.
- (21 点) Q = 1.
- (15 点)没有额外的限制。
入力例 1
3 2 1 2 2 3 1 3 6 1 4 5 4 7 2 8 9
出力例 1
3 4
JOI你是起点 2 并 安装在 3 的印章架和路径 考虑您指示更换安装在 4 处的印台的情况。 这时,
- JOI 您支付的总费用是 C_2+X\times 1 = 3 。
- JOI 你就是路 2,3,4,5,6,1 按顺序访问印台,并按顺序更改每个印台可盖印的印章颜色。 2, 3, 2, 1, 3, 1 变为。
- JOI 左右框都有印章的印章卡是 8 类型。
- 例如左边的颜色 3 印章,右侧有色 要获得印有 1 的印章卡,您必须前往 3 在印章卡的左侧, 使用 1 在印章卡右侧盖上每个印章。
- 左侧颜色 请注意,您不能只获得印有 1 印章,右侧有色 要获得印有 2 的印章卡。
2 成本低于 8 由于不可能获得超过一种类型的印章卡,1 在线 3 。 你只需要砍掉
另外,JOI君也以这个点为起点。 如果您选择 3 并且不指示更换印台,9 您可以获得不同类型的印章卡。 此时JOI所付出的总成本为 C_3 + X\times 0 = 4 。
3 成本低于 9 由于不可能获得超过一种类型的印章卡,2 在线 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
点作为起点 考虑选择 10 并指示按以下顺序更换印台的情况。 与安装在
- 道 15 的印章架和路径 考虑您指示更换安装在 16 中的印台交换
- 道 2 的印章架和路径 考虑您指示更换安装在 3 中的印台交换
- 道 16 的印章架和路径 考虑您指示更换安装在 1 中的印台交换
- 道 1 的印章架和路径 考虑您指示更换安装在 2 中的印台交换
此时 64 你可以获得不同类型的印章卡,总共需要支付的费用为 编号至 C_{10}+X\times 4=7 。
此输入示例是一个小作业。 2,3,4,5,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
此输入示例是一个小作业。 4,6 满足约束。