B - ライオン

あなたは動物園に来てライオンを見ている。 この動物園にはn個のライオンのオリがある。 あなたはライオンが全部で何頭いるのか知りたくなったのだが、 一人で数えるのは大変だ。 そこで近くにいた動物園の来園者m人に協力してもらうことにした。

ライオンのオリは、それぞれ1番からn番までの数字がついており、 順番に並んでいる。 一つのオリには0頭以上x頭以下のライオンがいる。

m人の来園者でi番目の人(1 ≤ i ≤ m)には l_i番から r_i番までの 両端を含むすべてのオリのライオンの数の総和を数えてもらった。

この情報を元に、1からn 各オリの中のライオンの数を求めることにした。

入力形式

入力は以下の形式で与えられる

n x m
l_1 r_1 s_1
...
l_m r_m s_m

1行目は3つの整数n x mで、 それぞれオリの数、一つのオリの中のライオンの最大の数、 数えるのに協力した人の数である。 2行目から続くm行は各行3つの整数で、 それぞれi番目の人が数えた結果 l_i r_is_iである。 l_i番からr_i番までのオリのライオンを数えたら 合計s_i頭いたことを表している。

出力形式

数えてもらった結果が全て正しいとして、 1からnの 各オリの中のライオンの数を空白区切りのn個の整数で出力せよ。 そのような答が複数あるときは、 ライオンの数の合計が最大になるものをどれでも良いので一つ出力せよ。 条件を満たすライオンの配置が一つもないときは-1を出力せよ。

制約

• 1 ≤ n ≤ 6
• 1 ≤ x ≤ 10
• 1 ≤ m ≤ 10
• 1 ≤ l_i ≤ r_i ≤ n
• 0 ≤ s_i ≤ 60
• 入力値はすべて整数である。

入出力例

入力例 1

3 5 1
1 2 5

出力例 1

2 3 5

その他"4 1 5"や"0 5 5"なども正しい出力である。

入力例 2

4 5 2
1 3 15
3 4 3

出力例 2

-1

条件を満たすライオンの配置が一つもないときは-1を出力せよ。