你在动物园里看着狮子。 在这个动物园里 有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
第一行是3个整数n x m笼子数量,一笼子最多可容纳狮子数量, 这是配合计数的人数。 从第 2 行继续m每行是三个整数, 每个 由第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。