约束求和

题目描述

判断是否存在满足以下所有条件的 $N$ 项整数序列 $X = (X_1, X_2, \ldots, X_N)$,若存在则构造一个这样的序列。

• 对于每个 $1 \le i \le N$,$0 \le X_i \le M$。
• 对于每个 $1 \le i \le Q$,$L_i \le X_{A_i} + X_{B_i} \le R_i$。

输入格式

输入按以下格式从标准输入给出:

$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。

样例

4 5 3
1 3 5 7
1 4 1 2
2 2 3 8

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)$,它们也会被接受。

3 7 3
1 2 3 4
3 1 9 12
2 3 2 4

-1

不存在满足所有条件的序列 $X$。

数据范围

• $1 \le N \le 10000$
• $1 \le M \le 100$
• $1 \le Q \le 10000$
• $1 \le A_i, B_i \le N$
• $0 \le L_i \le R_i \le 2 \times M$
• 输入中的所有值均为整数。

提示

答案不唯一,输出任意合法解即可。