[ABC277Ex] Constrained Sums

你需要构造一个长度为 $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}$。

[problemUrl]: https://atcoder.jp/contests/abc277/tasks/abc277_h 以下の条件すべてを満たす長さ $ 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` を出力せよ。

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 $ は存在しません。