CF978G.Petya's Exams

Petya studies at university. The current academic year finishes with $n$ special days. Petya needs to pass $m$ exams in those special days. The special days in this problem are numbered from $1$ to $n$.

There are three values about each exam:

• $s_i$ — the day, when questions for the $i$-th exam will be published,
• $d_i$ — the day of the $i$-th exam ($s_i \lt d_i$),
• $c_i$ — number of days Petya needs to prepare for the $i$-th exam. For the $i$-th exam Petya should prepare in days between $s_i$ and $d_i-1$, inclusive.

There are three types of activities for Petya in each day: to spend a day doing nothing (taking a rest), to spend a day passing exactly one exam or to spend a day preparing for exactly one exam. So he can't pass/prepare for multiple exams in a day. He can't mix his activities in a day. If he is preparing for the $i$-th exam in day $j$, then $s_i \le j \lt d_i$.

It is allowed to have breaks in a preparation to an exam and to alternate preparations for different exams in consecutive days. So preparation for an exam is not required to be done in consecutive days.

Find the schedule for Petya to prepare for all exams and pass them, or report that it is impossible.

佩佳在大学学习。当前学年以 $n$ 个特殊日子结束。佩佳需要在这 $n$ 个特殊日子中通过 $m$ 门考试。本题中的特殊日子编号为 $1$ 到 $n$。

每门考试有三个相关参数：

• $s_i$ —— 第 $i$ 门考试的考题公布日；
• $d_i$ —— 第 $i$ 门考试的考试日（满足 $s_i \lt d_i$）；
• $c_i$ —— 佩佳为第 $i$ 门考试所需准备的天数。佩佳必须在区间 $[s_i,\, d_i-1]$（含端点）内的某 $c_i$ 天中完成对该门考试的准备。

佩佳每天只能从事以下三种活动之一：

• 完全休息（不进行任何与考试相关的活动）；
• 恰好参加一门考试；
• 恰好为一门考试做准备。

因此，他不能在同一天参加多门考试或为多门考试做准备，也不能在同一天混合进行多种活动。若佩佳在第 $j$ 天为第 $i$ 门考试做准备，则必须满足 $s_i \le j \lt d_i$。

允许为同一门考试的准备过程存在间断，并允许在连续的若干天中交替为不同考试做准备。换言之，对某门考试的准备不要求连续进行。

请为佩佳制定一个时间表，使其能成功完成所有考试的准备并全部通过；若不可能实现，请报告无解。

The first line contains two integers $n$ and $m$ $(2 \le n \le 100, 1 \le m \le n)$ — the number of days and the number of exams.

Each of the following $m$ lines contains three integers $s_i$, $d_i$, $c_i$ $(1 \le s_i \lt d_i \le n, 1 \le c_i \le n)$ — the day, when questions for the $i$-th exam will be given, the day of the $i$-th exam, number of days Petya needs to prepare for the $i$-th exam.

Guaranteed, that all the exams will be in different days. Questions for different exams can be given in the same day. It is possible that, in the day of some exam, the questions for other exams are given.

第一行包含两个整数 $n$ 和 $m$（$2 \le n \le 100$，$1 \le m \le n$）—— 分别表示天数和考试门数。

接下来的 $m$ 行中，每行包含三个整数 $s_i$、$d_i$、$c_i$（$1 \le s_i \lt d_i \le n$，$1 \le c_i \le n$）—— 分别表示第 $i$ 门考试的题目发放日、考试日，以及 Petya 为第 $i$ 门考试所需准备的天数。

保证所有考试均安排在不同的日期。不同考试的题目可能在同一天发放。有可能在某门考试的当天，其他考试的题目也被发放。

If Petya can not prepare and pass all the exams, print -1. In case of positive answer, print $n$ integers, where the $j$-th number is:

• $(m + 1)$, if the $j$-th day is a day of some exam (recall that in each day no more than one exam is conducted),

• zero, if in the $j$-th day Petya will have a rest,

• $i$ ($1 \le i \le m$), if Petya will prepare for the $i$-th exam in the day $j$ (the total number of days Petya prepares for each exam should be strictly equal to the number of days needed to prepare for it).

  Assume that the exams are numbered in order of appearing in the input, starting from $1$.

  If there are multiple schedules, print any of them.

如果佩佳无法完成并参加所有考试，则输出 -1。否则，输出 $n$ 个整数，其中第 $j$ 个数为：

• $(m + 1)$，若第 $j$ 天举行某场考试（注意：每天最多只举行一场考试）；

• $0$，若第 $j$ 天佩佳休息；

• $i$（$1 \le i \le m$），若佩佳在第 $j$ 天为第 $i$ 场考试做准备（佩佳为每场考试准备的总天数必须严格等于该考试所需的准备天数）。

  假设考试按输入中出现的顺序编号，从 $1$ 开始。

  若存在多种可行的时间安排，输出任意一种即可。

In the first example Petya can, for example, prepare for exam $1$ in the first day, prepare for exam $2$ in the second day, pass exam $1$ in the third day, relax in the fourth day, and pass exam $2$ in the fifth day. So, he can prepare and pass all exams.

In the second example, there are three days and two exams. So, Petya can prepare in only one day (because in two other days he should pass exams). Then Petya can not prepare and pass all exams.

在第一个例子中，Petya 可以（例如）在第一天准备考试 $1$，第二天准备考试 $2$，第三天参加考试 $1$，第四天休息，第五天参加考试 $2$。因此，他能够完成所有考试的准备和参加。

在第二个例子中，共有三天和两场考试。因此，Petya 只能在一天中进行准备（因为在另外两天他必须参加考试）。于是，Petya 无法完成所有考试的准备和参加。