分数: 600 点
问题陈述
判断是否存在序列 N 整数 X = (X_1, X_2, \ldots ,X_N) 满足以下所有条件,并构建一个这样的序列(如果存在)。
- 0 \leq X_i \leq M 对于每个 1 \leq i \leq N.
- L_i \leq X_{A_i} + X_{B_i} \leq R_i 对于每个 1 \leq i \leq Q.
约束
- 1 \leq N \leq 10000
- 1 \leq M \leq 100
- 1 \leq Q \leq 10000
- 1 \leq A_i, B_i \leq N
- 0 \leq L_i \leq R_i \leq 2 \times M
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M Q A_1 B_1 L_1 R_1 A_2 B_2 L_2 R_2 \vdots A_Q B_Q L_Q R_Q
输出
如果存在满足问题陈述中所有条件的整数序列,则打印元素
一个这样的序列的 X_1, X_2, \ldots, X_N ,用空格分隔。否则,打印 -1.
示例输入 1
4 5 3 1 3 5 7 1 4 1 2 2 2 3 8
示例输出 1
2 4 3 0
对于 X = (2,4,3,0),我们有 X_1 + X_3 = 5, X_1 + X_4 = 2,和 X_2 + X_2 = 8,因此满足所有条件。还有其他顺序,例如 X = (0,2,5,2) 和 X = (1,3,4,1),满足所有条件,这些也将被接受。
示例输入 2
3 7 3 1 2 3 4 3 1 9 12 2 3 2 4
示例输出 2
-1
无序列 X 满足所有条件。