问题陈述

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

• 对于每个 $1 \leq i \leq N$，有 $0 \leq X_i \leq M$。

• 对于每个 $1 \leq i \leq Q$，有 $L_i \leq X_{A_i} + X_{B_i} \leq R_i$。

约束条件

• $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$ 满足所有条件。