← 返回题目列表

AtCoder · kupc2013_b

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

第一行是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。