{"problem":{"name":"Substring Comparison","description":{"content":"For an integer sequence $X=(X_1,X_2,\\dots,X_n)$, let $X[L,R]$ denote the integer sequence $(X_L,X_{L+1},\\dots,X_{R})$. You are given integers $N$ and $M$, and $M$ quadruples of integers $(A_i,B_i,C_i,","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"arc165_d"},"statements":[{"statement_type":"Markdown","content":"For an integer sequence $X=(X_1,X_2,\\dots,X_n)$, let $X[L,R]$ denote the integer sequence $(X_L,X_{L+1},\\dots,X_{R})$.\nYou are given integers $N$ and $M$, and $M$ quadruples of integers $(A_i,B_i,C_i,D_i)$.\nDetermine if there is an integer sequence $X$ of length $N$ that satisfies the following condition for every $i=1,2,\\dots,M$:\n\n*   $X[A_i,B_i]$ is lexicographically smaller than $X[C_i,D_i]$.\n\nWhat is lexicographical order on sequences?A sequence $S = (S_1,S_2,\\ldots,S_{|S|})$ is **lexicographically smaller** than $T = (T_1,T_2,\\ldots,T_{|T|})$ when 1. or 2. below holds. Here, $|S|$ and $|T|$ denotes the lengths of $S$ and $T$, respectively.\n\n1.  $|S| \\lt |T|$ and $(S_1,S_2,\\ldots,S_{|S|}) = (T_1,T_2,\\ldots,T_{|S|})$.\n2.  There is an integer $1 \\leq i \\leq \\min\\lbrace |S|, |T| \\rbrace$ that satisfy both of the following:\n    *   $(S_1,S_2,\\ldots,S_{i-1}) = (T_1,T_2,\\ldots,T_{i-1})$.\n    *   $S_i$ is smaller than $T_i$ (as a number).\n\n## Constraints\n\n*   $2 \\leq N \\leq 2000$\n*   $1 \\leq M \\leq 2000$\n*   $1 \\leq A_i \\leq B_i \\leq N$\n*   $1 \\leq C_i \\leq D_i \\leq N$\n*   All input values are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$\n$A_1$ $B_1$ $C_1$ $D_1$\n$A_2$ $B_2$ $C_2$ $D_2$\n$\\vdots$\n$A_M$ $B_M$ $C_M$ $D_M$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"arc165_d","tags":[],"sample_group":[["4 2\n1 3 3 4\n4 4 1 2","Yes\n\nFor example, $X=(1,1,2,1)$ satisfies the condition."],["3 2\n1 2 2 3\n2 2 1 1","No\n\nNo integer sequence $X$ satisfies the condition."],["15 20\n2 5 6 14\n11 14 10 10\n13 15 6 10\n8 10 3 8\n7 8 1 9\n2 8 14 15\n14 14 5 12\n6 10 9 9\n1 4 10 14\n5 14 6 7\n8 10 5 8\n8 10 11 15\n4 8 4 11\n7 9 1 4\n8 10 3 3\n11 13 8 14\n6 13 4 15\n4 7 6 11\n2 5 1 2\n8 14 6 8","No"]],"created_at":"2026-03-03 11:01:13"}}