AT_arc042_d [ARC042D] あまり

[problemUrl]: https://atcoder.jp/contests/arc042/tasks/arc042_d $ 4 $ つの整数 $ X,\ P,\ A,\ B\ (1\ ≦\ X\ が与えられます。ただし、P $ は素数です。 $ X^i\ (A\ ≦\ i\ ≦\ B) $ を $ P $ で割った余りの最小値を求めてください。 この問題の入力は得点に影響しない入力例 $ 1 $ を除いて、[このC++プログラム](/img/arc/042/adafrrg/generator.cpp)を用いて生成しました。擬似乱数生成器の初期化に用いられるプログラムの第 $ 1 $ 引数は $ 1 $ 以上 $ 10,000 $ 以下の整数を用いました。[このファイル](/img/arc/042/adafrrg/input.txt)の $ i $ 行目 $ (1\ ≦\ i\ ≦\ 10,000) $ は、入力生成プログラムの第 $ 1 $ 引数が $ i $ であるときの出力と一致します。すなわち、与えられるテストケースは入力例 $ 1 $ を除いて、このファイルのいずれかの行と一致します。

入力は以下の形式で標準入力から与えられる。 > $ X $ $ P $ $ A $ $ B $ - $ 1 $ 行目には、$ 4 $ つの整数 $ X,\ P,\ A,\ B\ (1\ ≦\ X\ が空白区切りで与えられる。ただし、P $ は素数である。

$ X^i\ (A\ ≦\ i\ ≦\ B) $ を $ P $ で割った余りの最小値を $ 1 $ 行に出力せよ。

### Sample Explanation 1 $ X^i\ (A\ ≦\ i\ ≦\ B) $ を $ P $ で割った余りは $ 8,\ 5,\ 10,\ 9,\ 7,\ 3,\ 6 $ であるので、最小値は $ 3 $ である。 この入力は入力生成プログラムを用いて作られたものではないので、得られる得点に影響しない。 ### Sample Explanation 2 この入力は入力生成プログラムの第 $ 1 $ 引数に $ 1 $ を与えて生成した。 ### Sample Explanation 3 この入力は入力生成プログラムの第 $ 1 $ 引数に $ 3 $ を与えて生成した。 ### Sample Explanation 4 この入力は入力生成プログラムの第 $ 1 $ 引数に $ 25 $ を与えて生成した。