{"problem":{"name":"Jigsaw","description":{"content":"We have $N$ irregular jigsaw pieces. Each piece is composed of three rectangular parts of width $1$ and various heights joined together. More specifically: *   The $i$\\-th piece is a part of height $","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"agc017_e"},"statements":[{"statement_type":"Markdown","content":"We have $N$ irregular jigsaw pieces. Each piece is composed of three rectangular parts of width $1$ and various heights joined together. More specifically:\n\n*   The $i$\\-th piece is a part of height $H$, with another part of height $A_i$ joined to the left, and yet another part of height $B_i$ joined to the right, as shown below. Here, the bottom sides of the left and right parts are respectively at $C_i$ and $D_i$ units length above the bottom side of the center part.\n\n![image](https://atcoder.jp/img/agc017/2b6cd7f4500d3621bc18de407f167522.png)\nSnuke is arranging these pieces on a square table of side $10^{100}$. Here, the following conditions must be held:\n\n*   All pieces must be put on the table.\n*   The entire bottom side of the center part of each piece must touch the front side of the table.\n*   The entire bottom side of the non-center parts of each piece must either touch the front side of the table, or touch the top side of a part of some other piece.\n*   The pieces must not be rotated or flipped.\n\nDetermine whether such an arrangement is possible.\n\n## Constraints\n\n*   $1 \\leq N \\leq 100000$\n*   $1 \\leq H \\leq 200$\n*   $1 \\leq A_i \\leq H$\n*   $1 \\leq B_i \\leq H$\n*   $0 \\leq C_i \\leq H - A_i$\n*   $0 \\leq D_i \\leq H - B_i$\n*   All input values are integers.\n\n## Input\n\nInput is given from Standard Input in the following format:\n\n$N$ $H$\n$A_1$ $B_1$ $C_1$ $D_1$\n$A_2$ $B_2$ $C_2$ $D_2$\n:\n$A_N$ $B_N$ $C_N$ $D_N$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"agc017_e","tags":[],"sample_group":[["3 4\n1 1 0 0\n2 2 0 1\n3 3 1 0","YES\n\nThe figure below shows a possible arrangement.\n![image](https://atcoder.jp/img/agc017/27db184b6924d4cec5077a54b505706a.png)"],["4 2\n1 1 0 1\n1 1 0 1\n1 1 0 1\n1 1 0 1","NO"],["10 4\n1 1 0 3\n2 3 2 0\n1 2 3 0\n2 1 0 0\n3 2 0 2\n1 1 3 0\n3 2 0 0\n1 3 2 0\n1 1 1 3\n2 3 0 0","YES"]],"created_at":"2026-03-03 11:01:13"}}