← 返回题目列表

Codeforces · 978/G

G. Petya 的考试

中文机器翻译题面 查看原题

Petya 在大学学习。本学年以 $$$n$$$ 特殊日子结束。在那些特殊的日子里,Petya 需要通过 $$$m$$$ 考试。此问题中的特殊日期从 $$$1$$$ 到 $$$n$$$ 编号。

每项考试有三个值:

- $$$s_i$$$ — 第 $$$i$$$ 考试的问题将发布的那一天,
- $$$d_i$$$ — 第 $$$i$$$ 次考试的日期 ($$$s_i < d_i$$$),
- $$$c_i$$$ — Petya 需要准备第 $$$i$$$ 次考试的天数。对于第 $$$i$$$ 次考试,Petya 应在 $$$s_i$$$ 和 $$$d_i-1$$$(含)之间准备几天。

Petya 每天有三种活动:花一天什么都不做(休息)、花一天只通过一场考试或花一天准备一场考试。所以他无法在一天内通过/准备多次考试。他不能在一天内混合他的活动。如果他正在准备 $$$j$$$ 天的第 $$$i$$$ 次考试,则 $$$s_i \le j < d_i$$$。

允许在考试准备过程中休息,并在连续几天内交替准备不同的考试。因此,考试准备不需要在连续几天内完成。

找到 Petya 准备所有考试并通过考试的时间表,否则报告不可能。

输入

第一行包含两个整数 $$$n$$$ 和 $$$m$$$ $$$(2 \le n \le 100, 1 \le m \le n)$$$ — 天数和考试次数。

以下 $$$m$$$ 行中的每一行都包含三个整数 $$$s_i$$$, $$$d_i$$$, $$$c_i$$$ $$$(1 \le s_i < d_i \le n, 1 \le c_i \le n)$$$ — 第 $$$i$$$ 考试的试题将给出的日期,考试日期第 $$$i$$$ 次考试,Petya 需要准备第 $$$i$$$ 次考试的天数。

保证所有考试都将在不同的日子进行。不同考试的题目可以在同一天给出。某些考试的当天可能会给出其他考试的题目。

输出

如果 Petya 无法准备并通过所有考试,请打印 -1。如果答案是肯定的,则打印 $$$n$$$ 整数,其中第 $$$j$$$ 个数字是:

- $$$(m + 1)$$$,如果第 $$$j$$$ 天是某次考试的一天(回想一下,每天进行的考试不超过一次),
- 零,如果在第 $$$j$$$ 天 Petya 会休息,
- $$$i$$$ ($$$1 \le i \le m$$$),如果 Petya 将准备 $$$j$$$ 当天的第 $$$i$$$ 次考试(Petya 为每项考试准备的总天数应严格等于准备该考试所需的天数)。假设考试按输入中出现的顺序编号,从$$$1$$$。如果有多个时间表,请打印其中任何一个。

示例

输入 #1

5 2
1 3 1
1 5 1

输出 #1

1 2 3 0 3

输入 #2

3 2
1 3 1
1 2 1

输出 #2

-1

输入 #3

10 3
4 7 2
1 10 3
8 9 1

输出 #3

2 2 2 1 1 0 4 3 4 4

注意

在第一个示例中,Petya 可以在第一天准备考试 $$$1$$$,在第二天准备考试 $$$2$$$,在第三天通过考试 $$$1$$$,在第四天放松,并在第五天通过考试 $$$2$$$。因此,他可以准备并通过所有考试。

在第二个示例中,有三天两次考试。所以,Petya 只需要一天的时间就可以准备(因为另外两天他就应该通过考试)。那么 Petya 就无法准备并通过所有考试。