問題文

以下の条件すべてを満たす長さ $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$

制約

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

出力

問題文中の条件すべてを満たす整数列が存在する場合、そのうちの $1$ つの $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$ は存在しません。