AT_pakencamp_2025_day2_b Ants Sequence

在“パ研王国”中，生息着一种被称为パケンアリ的蚂蚁。パケンアリ会建造一条长度为 $M$ 的细长巢穴，这个巢穴可以看作是数轴上的一条线段，左端点为坐标 $0$，右端点为坐标 $M$。 生物学家パケン氏发现了パケンアリ的以下习性： - パケンアリ会以每秒 $1$ 的速度，沿着当前方向在数轴上前进。 - 若有两只パケンアリ在某一时刻到达同一坐标，则这两只パケンアリ会立即同时改变前进方向（调头），而不会互相错过。根据题意，保证不会有三只及以上的パケンアリ在同一时刻碰头。 - 每只パケンアリ抵达巢穴左端（坐标 $0$）或右端（坐标 $M$）时，也会立即改变前进方向。 现在，パケン氏考虑了 $Q$ 个问题。对于第 $i$ 个问题（$1 \leq i \leq Q$），给定整数 $l_i$ 和 $r_i$，具体如下： - 在坐标 $A_{l_i}, A_{l_i+1}, \dots, A_{r_i}$ 上，分别各自放上一只右向的パケンアリ。请判定是否存在一个非负整数 $t$，使得经过 $t$ 秒后，原来在坐标 $A_j$（$l_i \leq j \leq r_i$）的所有蚂蚁，都会恰好同时位于 $B_j$，若存在则求出最小的 $t$。 对于全部 $Q$ 个问题，请分别求出答案。

输入以如下格式，通过标准输入读入。 > $N$ $M$ $Q$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$ $l_1$ $r_1$ $l_2$ $r_2$ $...$ $l_Q$ $r_Q$

输出 $Q$ 行，第 $i$ 行输出第 $i$ 个问题满足条件的最小 $t$ 值。如果不存在满足条件的 $t$，则输出 `-1`。

### 子任务 1. （4 分）$N, M \leq 1000, Q \leq 10$ 2. （8 分）$N \leq 1000, Q \leq 10$ 3. （26 分）$Q \leq 10$ 4. （30 分）$N, M, Q \leq 10^5$，$A_i < A_{i+1}$（$1 \leq i < N$），$B_j \leq B_{j+1}$（$1 \leq j < N$） 5. （20 分）$N, M, Q \leq 10^5$ 6. （12 分）没有额外限制 ### 样例解释 1 对于第 $1$ 个问题，所有 $i$ 对应的，在坐标 $A_i$ 的パケンアリ无法同时到达坐标 $B_i$，因此答案为 `-1`。 对于第 $2$ 个问题，经过 $4$ 秒后，原本位于坐标 $1$ 的蚂蚁会来到坐标 $5$，原本位于 $4$ 的蚂蚁会到达 $8$，刚好满足条件。因此答案是 $4$。 对于第 $3$ 个问题，经过 $7$ 秒后，原本在坐标 $10$ 的蚂蚁会到达 $17$，原本在 $15$ 的蚂蚁会在 $M$ 反转后到达 $18$，刚好满足条件。因此答案是 $7$。 ### 数据范围与限制 - $1 \le N, M, Q \leq 4 \times 10^5$ - $0 < A_i < M \ (1 \leq i \leq N)$ - $A_i \neq A_j \quad (i \neq j)$ - $0 \leq B_j \leq M \ (1 \leq j \leq N)$ - $1 \le l_i \le r_i \le N \ (1 \leq i \leq Q)$ - 输入均为整数。 由 ChatGPT 5 翻译