题目描述

以下の条件すべてを満たす長さ $N$ の整数列 $X\ =\ (X_1,\ X_2,\ \ldots\ ,X_N)$ が存在するか判定し、存在する場合 $1$ 通り構成してください。

• すべての $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$

输入格式

入力は以下の形式で標準入力から与えられる。

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

输出格式

問題文中の条件すべてを満たす整数列が存在する場合、そのうちの $1$ つの $X_1,\ X_2,\ \ldots,\ X_N$ を空白区切りで出力せよ。存在しない場合は -1 を出力せよ。

题目大意

你需要构造一个长度为 $n$ 的序列 $x$，满足下列条件：

• $\forall i\in [1,n]$，$0\le x_i\le M$。

• $\forall i\in [1,Q]$，$L_{i}\le x_{a_i}+x_{b_i}\le R_{i}$。

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

2 4 3 0

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

-1

提示

制約

• $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$
• 入力はすべて整数

Sample Explanation 1

$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)$ などもすべての条件を満たすため、これらを出力しても正解となります。

Sample Explanation 2

すべての条件を満たす数列 $X$ は存在しません。