AT_arc171_d [ARC171D] Rolling Hash

给定整数 $P,B$ 满足 $P$ 是质数，$1\le B\le P-1$。 对于序列 $X=(x_1,x_2,\cdots,x_n)$，定义 $\operatorname{hash}(X)$ 的值为 $$\operatorname{hash}(X)=\left(\sum_{i=1}^nx_iB^{n-i}\right)\bmod P$$ 给定 $M$ 对整数 $(L_i,R_i)(1\le i\le M)$，请问是否存在长度为 $N$ 的序列 $A=(A_1,A_2,\cdots,A_N)$ 满足： - 对每一个 $i(1\le i\le M)$，都有 $$\operatorname{hash}((A_{L_i},A_{L_i+1},\cdots,A_{R_i}))\not=0$$

第一行四个整数 $P,B,N,M$，接下来 $M$ 行每行两个整数 $L_i,R_i$。

若存在 $A$ 满足要求输出 `Yes`，否则输出 `No`。 ### 样例 1 解释 序列 $A=(2,0,4)$ 满足要求。其中 - $\operatorname{hash}((A_1))=2$ - $\operatorname{hash}((A_1,A_2))=1$ - $\operatorname{hash}((A_2,A_3))=1$

- $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$ - $(L_i, R_i) \neq (L_j, R_j)$ if $i \neq j$. - 所有的输入都是整数。