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$.
• 所有的输入都是整数。