题目描述

Gorkovich 先生是这次奥林匹克竞赛的一名监考员。他的工作不仅是看管考场，还要给部分参赛选手分发题目。

可以把竞赛所在的建筑看成一条很长的走廊。走廊上有 N 个房间，第 i 个房间里有 a_i 名学生。第 i 个房间和第 i+1 个房间之间的距离为 b_i 米。

Gorkovich 一共会拿到 M 份题目，需要把它们分发出去。他从自己监考的房间 k 出发。

每当他到达一个房间时，如果这个房间里的学生还没有从他手中拿到题目，他就会给这个房间里的所有学生分发题目。若当前房间学生人数大于或等于他手中剩余的题目数量，那么他会把剩余题目全部发完，然后返回自己的监考房间。

Gorkovich 非常懒，因此他希望自己走过的总路程尽可能短。

不过，竞赛组织工作经常临时变动。组委会会不断通知 Gorkovich，他应该在哪个房间监考。总共有 Q 次通知，第 i 次通知给出一个房间编号 k_i。

对于每次通知，请求出：如果 Gorkovich 从房间 k_i 出发，分发完 M 份题目并回到房间 k_i，所需最短路程的一半。

任务

请编写程序 lazy，实现两个函数：

void init(int M, std::vector<int> a, std::vector<int> b);
int message(int k);

你的程序会与评测程序一起编译。

接口说明

init

void init(int M, std::vector<int> a, std::vector<int> b);

该函数会在开始时被评测程序调用一次。

参数含义：

• M：需要分发的题目数量；
• a：长度为 N 的数组，依次表示 a_1, a_2, ..., a_N；
• b：长度为 N-1 的数组，依次表示 b_1, b_2, ..., b_{N-1}。

message

int message(int k);

该函数会在每次通知后被调用一次。

参数 k 表示 Gorkovich 当前监考的房间编号。函数应返回一个整数：从房间 k 出发，分发完 M 份题目并返回房间 k 的最短路程的一半。

房间编号使用题面中的编号，即从 1 到 N。

你需要提交文件 lazy.cpp，其中包含函数 init 和 message。你的文件可以包含其他辅助代码和函数，但：

• 不应包含 main 函数；
• 不应从标准输入读入；
• 不应向标准输出输出。

数据范围

• 1 ≤ Q ≤ N ≤ 2 × 10^6
• 1 ≤ M ≤ 2 × 10^9
• 1 ≤ a_i, b_i ≤ 10^3
• M ≤ a_1 + a_2 + ... + a_N

子任务

子任务	分值	N	Q	附加限制
1	0	-		样例测试
2	11	≤ 10^4	= 1	-
3	17	≤ 5 × 10^5	≤ 10
4	13	≤ 2 × 10^6
5	18	≤ 2 × 10^5
6	12	≤ 5 × 10^5
7	29	≤ 2 × 10^6

只有通过某个子任务中的所有测试，才能获得该子任务的分数。

样例交互

评测程序调用：

init(10, {2, 7, 1, 1, 1, 7, 5}, {2, 7, 3, 1, 2, 9});

表示：

• 每个房间的学生人数为 2, 7, 1, 1, 1, 7, 5；
• 相邻房间间距为 2, 7, 3, 1, 2, 9；
• 需要分发 10 份题目。

随后：

message(4)

应返回：

6

一种最优路线为：

4 -> 5 -> 6 -> 5 -> 4 -> 3 -> 4

总路程为：

1 + 2 + 2 + 1 + 3 + 3 = 12

所以返回其一半 6。

又例如：

message(7)

应返回：

9

最优路线为：

7 -> 6 -> 7

总路程为 9 + 9 = 18，所以返回 9。

本地测试

原题提供本地测试文件 Lgrader.cpp。将它与自己的 lazy.cpp 放在同一目录下，只编译 Lgrader.cpp 即可进行测试。

本地测试程序会从标准输入读取如下数据：

1. 第一行：两个正整数 N, M；
2. 第二行：N 个正整数 a_1, a_2, ..., a_N；
3. 第三行：N-1 个正整数 b_1, b_2, ..., b_{N-1}；
4. 第四行：一个正整数 Q；
5. 最后一行：Q 个正整数 k_1, k_2, ..., k_Q。

本地测试程序会输出所有询问的答案。

@下发文件