配点 : 100 点
問題文
称为帕肯蚂蚁的蚂蚁生活在帕肯王国。帕肯阿里很长 创建一个又长又细的嵌套 M ,该嵌套将协调左端。 0,坐标右边缘 它用 M 表示为数轴。
生物学家Paken先生发现Paken蚂蚁有以下习性。
- Paken Ari 朝您当前在数轴上面对的方向移动。 以 1 每秒 1 的速度前进。
- 2 当两只帕肯蚁在某一时刻到达同一坐标时,2 蚂蚁们立即改变方向,没有互相经过。此外,由于条件限制,3 保证不会有超过一只帕肯蚂蚁同时到达同一坐标。
- 每只帕肯蚂蚁都位于巢穴的左边缘(坐标 0)或右边缘(坐标 M),行进方向立即反转。
现在,Phaken 先生 我正在考虑 Q 问题。i (1 \leq i \leq Q) 为整数 给出 l_i 和 将其放在 r_i 并具有以下内容。 帕肯·阿里 (Paken Ari) 上
- 座標 A_{l_i}, A_{l_i+1}, \dots, A_{r_i} 帕肯·阿里托 1 将它们一一面向右放置。t 秒后,原始坐标 A_j (l_i \leq j \leq r_i中的所有蚂蚁同时设置它们的坐标。 一个非负整数,如 B_j 判断 t 的最小值是否存在,如果存在,则求最小值。 查找所有
Q 问题的答案。
制約
- 1 \le N, M, Q \le 4 \times {10}^5
- 0 < A_i < M \ (1 \le i \le N)
- A_i \neq A_j \ (i \neq j)
- 0 \le B_j \le M \ (1 \le j \le N)
- 1 \le l_i \le r_i \le N \ (1 \le i \le Q)
- 所有输入均为整数。
小課題
- (4 点) N,M \leq 1000,Q \leq 10
- (8 点) N \leq 1000,Q \leq 10
- (26 点) Q \leq 10
- (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)
- (20 点) N,M,Q \leq {10}^5
- (12 点)无附加约束
入力
输入将以以下形式通过标准输入给出。
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 \vdots l_Q r_Q
出力
Q 行。
当
i (1 \leq i \leq Q) 行包含
作为第i 问题的答案,最小
将 t 作为整数打印。如果这样的话
对于第 t 不存在,则
输出 -1 。
入力例 1
4 20 3 1 4 10 15 5 8 17 18 1 4 1 2 3 4
出力例 1
-1 4 7
1 个问题,所有
坐标关于 i 位于 A_i 的 Paken Ari 有坐标
最小的,例如 B_i 最小的这样 t 不存在。因此,答案是
对于第 -1 。
2 个问题,4 秒后,坐标 1 处的蚂蚁有坐标 5 ,坐标
前往 4 处的蚂蚁有坐标 8 并满足条件。这是最小的
由于可以证明 t ,所以答案是
通过使用 4 。
3 个问题,7 秒后,坐标 10 处的蚂蚁有坐标 17 ,坐标
前往 15 处的蚂蚁有坐标 M 反转行进方向进行协调 18 并满足条件。这是最小的
由于可以证明 t ,所以答案是
通过使用 7 。