← 返回题目列表

AtCoder · abc277_h

Ex. 约束和

中文机器翻译题面 查看原题

分数: 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 满足所有条件。