{"problem":{"name":"Rolling Hash","description":{"content":"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 de","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc171_d"},"statements":[{"statement_type":"Markdown","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$.\n\n## Constraints\n\n*   $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.\n\n## Input\n\nThe 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$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc171_d","tags":[],"sample_group":[["3 2 3 3\n1 1\n1 2\n2 3","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$."],["2 1 3 3\n1 1\n2 3\n1 3","No\n\nNo sequence satisfies the condition."],["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","Yes"]],"created_at":"2026-03-03 11:01:13"}}