AT_arc171_d [ARC171D] Rolling Hash

[problemUrl]: https://atcoder.jp/contests/arc171/tasks/arc171_d 非負整数 $ P,\ B $ が与えられます。$ P $ は素数で、$ 1\ \leq\ B\ \leq\ P-1 $ です。 非負整数列 $ X=(x_1,x_2,\dots,x_n) $ に対して $ X $ のハッシュ値 $ \mathrm{hash}(X) $ を次のように定義します。 $ \displaystyle\ \mathrm{hash}(X)\ =\ \left(\sum_{i=1}^n\ x_i\ B^{n-i}\right)\ \bmod\ P $ $ M $ 個の整数対 $ (L_1,\ R_1),\ (L_2,\ R_2),\ \dots,\ (L_M,\ R_M) $ が与えられます。 次の条件を満たす長さ $ N $ の非負整数列 $ A=(A_1,\ A_2,\ \dots,\ A_N) $ は存在しますか？ - すべての $ i $ $ (1\ \leq\ i\ \leq\ M) $ について次の条件が成り立つ。 - $ A $ の $ L_i $ 番目から $ R_i $ 番目までの要素を取り出して出来る数列 $ (A_{L_i},\ A_{L_i\ +\ 1},\ \dots,\ A_{R_i}) $ を $ s $ とおいたとき、$ \mathrm{hash}(s)\ \neq\ 0 $ である。

入力は以下の形式で標準入力から与えられる。 > $ P $ $ B $ $ N $ $ M $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_M $ $ R_M $

問題文の条件を満たす数列が存在すれば `Yes` を、存在しなければ `No` を出力せよ。

### 制約 - $ 2\ \leq\ P\ \leq\ 10^9 $ - $ P $ は素数 - $ 1\ \leq\ B\ \leq\ P\ -\ 1 $ - $ 1\ \leq\ N\ \leq\ 16 $ - $ 1\ \leq\ M\ \leq\ \frac{N(N+1)}{2} $ - $ 1\ \leq\ L_i\ \leq\ R_i\ \leq\ N $ - $ i\ \neq\ j $ ならば $ (L_i,\ R_i)\ \neq\ (L_j,\ R_j) $ - 入力される値はすべて整数 ### Sample Explanation 1 数列 $ A\ =\ (2,\ 0,\ 4) $ は $ \mathrm{hash}((A_1))\ =\ 2,\ \mathrm{hash}((A_1,\ A_2))\ =\ 1,\ \mathrm{hash}((A_2,\ A_3))\ =\ 1 $ であるため問題文の条件を満たす数列です。 ### Sample Explanation 2 問題文の条件を満たす数列は存在しません。