题目描述

在一个并不算太遥远的村庄里，有 N 位农夫，每人都养了一头奶牛当宠物。村里的街道首尾相连，形成一个长度为 L 的环。为了方便描述，村民把这条环形街道按等距位置编号为 0 到 L-1，就像钟表表盘一样。

第 i 位农夫的房子位于坐标 P_i，并且满足：

0 <= P_0 < P_1 < ... < P_{N-1} < L

某一天，所有奶牛突然同时发狂。每头奶牛都会沿街道以每分钟 1 个单位的速度奔跑，方向可能是：

• 顺时针（坐标增加方向），记为 1
• 逆时针（坐标减少方向），记为 -1

更特殊的是：如果两头迎面跑来的疯牛相遇，那么它们会立刻同时掉头，并继续以相同速度往反方向跑。这个“相遇并掉头”的过程耗时恰好为 0 分钟。

农夫们记录下了每头牛的初始方向 D_i，然后提出了 Q 个询问：

第 C_j 位农夫的牛，在 T_j 分钟后会位于哪里？

请你实现函数 solve，返回所有询问的答案。

---

实现要求

你需要实现如下函数：

std::vector<int> solve(
    int L,
    std::vector<int> P,
    std::vector<int> D,
    std::vector<int> C,
    std::vector<int> T
);

参数含义如下：

• L：环形街道的长度
• P：按升序给出的所有房屋位置
• D：每头牛的初始方向，取值只能为 1 或 -1
• C：所有询问中涉及的牛的编号
• T：所有询问中的时间

函数需要返回一个向量，按询问顺序给出答案。也就是说，返回值的第 j 个元素应当是：

• 第 C_j 头牛在 T_j 分钟后所在的位置

---

约束条件

• 2 <= N <= 10^6
• 1 <= Q <= 10^6
• N <= L <= 10^9
• 0 <= P_0 < P_1 < ... < P_{N-1} < L
• D_i ∈ {1, -1}
• 0 <= C_j < N
• 0 <= T_j <= 10^9

---

子任务

原题共有 10 个子任务（含样例子任务），整理如下：

子任务	分值	需要通过的前置子任务	N	Q	额外限制
0		-	-		样例
1	5		= 2	<= 3 × 10^3	无
2	15		<= 100		L <= 10^2，T_j <= 10^4
3	10		<= 3 × 10^3		所有 T_j 都能被 L 整除
4				<= 10^5	无
5	15	0-4		<= 3 × 10^3
6	10	3	<= 10^6	<= 10^5	所有 T_j 都能被 L 整除
7	15	4			所有 T_j < L
8	10	0-7			无
9		0-8		<= 10^6	所有 T_j < L

只有当某个子任务及其要求的前置子任务全部通过时，才能获得该子任务的分数。

---

本地评测器

输入格式

• 第 1 行：两个整数 N, L，分别表示农夫数量和街道长度
• 第 2 行：P_0 P_1 ... P_{N-1}，表示所有房屋的位置
• 第 3 行：D_0 D_1 ... D_{N-1}，表示所有牛的初始方向
• 第 4 行：整数 Q，表示询问个数
• 第 5 行到第 4 + Q 行：每行两个整数 C_j, T_j，表示一个询问

输出格式

• 第 i 行：solve 返回值中的第 i 个元素

---

样例 1

输入

3 6
0 2 5
-1 1 1
3
0 2
2 1
1 5

输出

1
5
4

---

样例 2

输入

3 12461
5049 6138 6513
1 -1 -1
3
1 178432
0 1414122
2 24922

输出

9027
484
5049

---

样例 1 说明

下面描述样例 1 中的运动过程：

• 初始时三头牛分别位于位置 0, 2, 5
• 第 1 分钟进行到一半时，编号 0 和编号 2 的牛相遇，并立刻掉头
• 正好在第 2 分钟结束时，编号 1 和编号 2 的牛在坐标 4 相遇，因此它们会在第 3 分钟朝相反方向继续移动

---