AT_pakencamp_2025_day2_b Ants Sequence

パ研王国には、パケンアリと呼ばれるアリが生息している。パケンアリは長さ $ M $ の細長い巣を作り、この巣は左端を座標 $ 0 $ 、右端を座標 $ M $ とする数直線として表される。 生物学者のパケン氏は、パケンアリに以下の習性があることを発見した。 - パケンアリは、数直線上を今向いている方向に $ 1 $ 秒あたり $ 1 $ の速さで進む。 - $ 2 $ 匹のパケンアリがある時刻に同じ座標に到達したとき、 $ 2 $ 匹のアリは互いにすれ違うことなく即座に進行方向を反転させる。なお、制約より、 $ 3 $ 匹以上のパケンアリが同時に同じ座標に到達することはないことが保証される。 - 各パケンアリは、巣の左端（座標 $ 0 $ ）か右端（座標 $ M $ ）に到達した場合も、即座に進行方向を反転させる。 今、パケン氏は $ Q $ 個の問題を考えている。 $ i $ ( $ 1 \leq i \leq Q $ ) 番目の問題では整数 $ l_i $ と $ r_i $ が与えられ、以下のような内容である。 - 座標 $ 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 $ 個の問題すべてに対し、解答を求めよ。

入力は以下の形式で標準入力から与えられる。 > $ 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 $ 点) $ 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 $ 点) 追加の制約はない ### Sample Explanation 1 $ 1 $ 番目の問題について、すべての $ i $ について座標 $ A_i $ にいたパケンアリが座標 $ B_i $ にいるような最小の $ t $ は存在しません。よって、答えは `-1` となります。 $ 2 $ 番目の問題について、 $ 4 $ 秒後に、座標 $ 1 $ にいたアリは座標 $ 5 $ に、座標 $ 4 $ にいたアリは座標 $ 8 $ に移動し、条件を満たします。これが最小の $ t $ であることが示せるため、答えは `4` となります。 $ 3 $ 番目の問題について、 $ 7 $ 秒後に、座標 $ 10 $ にいたアリは座標 $ 17 $ に、座標 $ 15 $ にいたアリは座標 $ M $ で進行方向を反転させることによって座標 $ 18 $ に移動し、条件を満たします。これが最小の $ t $ であることが示せるため、答えは `7` となります。 ### Constraints - $ 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) $ - 入力はすべて整数である。