Score: $600$ points

问题陈述

给定非负整数 $P$ 和 $B$。这里，$P$ 是素数，$1 \leq B \leq P-1$。 对于非负整数序列 $X=(x_1,x_2,\dots,x_n)$，哈希值 $\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)$，以下条件成立：
  • 令 $s$ 是通过取 $A$ 的第 $L_i$ 个到第 $R_i$ 个元素得到的序列 $(A_{L_i}, A_{L_i + 1}, \dots, A_{R_i})$。那么，$\mathrm{hash}(s) \neq 0$。

以上为大语言模型 kimi 翻译，仅供参考。

Problem Statement

You are given non-negative integers $P$ and $B$. Here, $P$ is prime, and $1 \leq B \leq P-1$.
For a sequence of non-negative integers $X=(x_1,x_2,\dots,x_n)$, the hash value $\mathrm{hash}(X)$ is defined as follows.

$\displaystyle \mathrm{hash}(X) = \left(\sum_{i=1}^n x_i B^{n-i}\right) \bmod P$

You are given $M$ pairs of integers $(L_1, R_1), (L_2, R_2), \dots, (L_M, R_M)$.
Is there a sequence of non-negative integers $A=(A_1, A_2, \dots, A_N)$ of length $N$ that satisfies the condition below?

• For all $i$ $(1 \leq i \leq M)$, the following condition holds:
  • Let $s$ be the sequence $(A_{L_i}, A_{L_i + 1}, \dots, A_{R_i})$ obtained by taking the $L_i$-th to the $R_i$-th elements of $A$. Then, $\mathrm{hash}(s) \neq 0$.

Constraints

• $2 \leq P \leq 10^9$
• $P$ is prime.
• $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$.
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$P$ $B$ $N$ $M$

$L_1$ $R_1$

$L_2$ $R_2$

$\vdots$

$L_M$ $R_M$

Output

If there is a sequence that satisfies the condition in the problem statement, print Yes; otherwise, print No.

Sample Input 1

3 2 3 3
1 1
1 2
2 3

Sample Output 1

Yes

The sequence $A = (2, 0, 4)$ satisfies the condition because $\mathrm{hash}((A_1)) = 2, \mathrm{hash}((A_1, A_2)) = 1, \mathrm{hash}((A_2, A_3)) = 1$.

Sample Input 2

2 1 3 3
1 1
2 3
1 3

Sample Output 2

No

No sequence satisfies the condition.

Sample Input 3

998244353 986061415 6 11
1 5
2 2
2 5
2 6
3 4
3 5
3 6
4 4
4 5
4 6
5 6

Sample Output 3

Yes