{"problem":{"name":"Ex - Constrained Sums","description":{"content":"Determine whether there is a sequence of $N$ integers $X = (X_1, X_2, \\ldots ,X_N)$ that satisfies all of the following conditions, and construct one such sequence if it exists.   *   $0 \\leq X_i \\le","description_type":"Markdown"},"platform":"AtCoder","limit":{"time_limit":4000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"abc277_h"},"statements":[{"statement_type":"Markdown","content":"Determine whether there is a sequence of $N$ integers $X = (X_1, X_2, \\ldots ,X_N)$ that satisfies all of the following conditions, and construct one such sequence if it exists.  \n\n*   $0 \\leq X_i \\leq M$ for every $1 \\leq i \\leq N$.  \n    \n*   $L_i \\leq X_{A_i} + X_{B_i} \\leq R_i$ for every $1 \\leq i \\leq Q$.\n\n## Constraints\n\n*   $1 \\leq N \\leq 10000$\n*   $1 \\leq M \\leq 100$\n*   $1 \\leq Q \\leq 10000$\n*   $1 \\leq A_i, B_i \\leq N$\n*   $0 \\leq L_i \\leq R_i \\leq 2 \\times M$\n*   All values in the input are integers.\n\n## Input\n\nThe input is given from Standard Input in the following format:\n\n$N$ $M$ $Q$\n$A_1$ $B_1$ $L_1$ $R_1$\n$A_2$ $B_2$ $L_2$ $R_2$\n$\\vdots$\n$A_Q$ $B_Q$ $L_Q$ $R_Q$\n\n[samples]","is_translate":false,"language":"English"}],"meta":{"iden":"abc277_h","tags":[],"sample_group":[["4 5 3\n1 3 5 7\n1 4 1 2\n2 2 3 8","2 4 3 0\n\nFor $X = (2,4,3,0)$, we have $X_1 + X_3 = 5$, $X_1 + X_4 = 2$, and $X_2 + X_2 = 8$, so all conditions are satisfied. There are other sequences, such as $X = (0,2,5,2)$ and $X = (1,3,4,1)$, that satisfy all conditions, and those will also be accepted."],["3 7 3\n1 2 3 4\n3 1 9 12\n2 3 2 4","\\-1\n\nNo sequence $X$ satisfies all conditions."]],"created_at":"2026-03-03 11:01:13"}}