{"raw_statement":[{"iden":"problem statement","content":"You are given non-negative integers $P$ and $B$. Here, $P$ is prime, and $1 \\leq B \\leq P-1$.  \nFor a sequence of non-negative integers $X=(x_1,x_2,\\dots,x_n)$, the hash value $\\mathrm{hash}(X)$ is defined as follows.\n\n$\\displaystyle \\mathrm{hash}(X) = \\left(\\sum_{i=1}^n x_i B^{n-i}\\right) \\bmod P$\n\nYou are given $M$ pairs of integers $(L_1, R_1), (L_2, R_2), \\dots, (L_M, R_M)$.  \nIs there a sequence of non-negative integers $A=(A_1, A_2, \\dots, A_N)$ of length $N$ that satisfies the condition below?\n\n*   For all $i$ $(1 \\leq i \\leq M)$, the following condition holds:\n    *   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$."},{"iden":"constraints","content":"*   $2 \\leq P \\leq 10^9$\n*   $P$ is prime.\n*   $1 \\leq B \\leq P - 1$\n*   $1 \\leq N \\leq 16$\n*   $1 \\leq M \\leq \\frac{N(N+1)}{2}$\n*   $1 \\leq L_i \\leq R_i \\leq N$\n*   $(L_i, R_i) \\neq (L_j, R_j)$ if $i \\neq j$.\n*   All input values are integers."},{"iden":"input","content":"The input is given from Standard Input in the following format:\n\n$P$ $B$ $N$ $M$\n$L_1$ $R_1$\n$L_2$ $R_2$\n$\\vdots$\n$L_M$ $R_M$"},{"iden":"sample input 1","content":"3 2 3 3\n1 1\n1 2\n2 3"},{"iden":"sample output 1","content":"Yes\n\nThe 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$."},{"iden":"sample input 2","content":"2 1 3 3\n1 1\n2 3\n1 3"},{"iden":"sample output 2","content":"No\n\nNo sequence satisfies the condition."},{"iden":"sample input 3","content":"998244353 986061415 6 11\n1 5\n2 2\n2 5\n2 6\n3 4\n3 5\n3 6\n4 4\n4 5\n4 6\n5 6"},{"iden":"sample output 3","content":"Yes"}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}