G. Petya's Exams

[{"iden":"statement","content":"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$.\n\nThere are three values about each exam:\n\nThere 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 lt.eq j < d_i$.\n\nIt 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.\n\nFind the schedule for Petya to prepare for all exams and pass them, or report that it is impossible.\n\nThe first line contains two integers $n$ and $m$ $(2 lt.eq n lt.eq 100, 1 lt.eq m lt.eq n)$ — the number of days and the number of exams.\n\nEach of the following $m$ lines contains three integers $s_i$, $d_i$, $c_i$ $(1 lt.eq s_i < d_i lt.eq n, 1 lt.eq c_i lt.eq 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. \n\nGuaranteed, 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\nIf 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:\n\nAssume that the exams are numbered in order of appearing in the input, starting from $1$.\n\nIf there are multiple schedules, print any of them.\n\nIn 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.\n\nIn 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.\n\n"},{"iden":"input","content":"The first line contains two integers $n$ and $m$ $(2 lt.eq n lt.eq 100, 1 lt.eq m lt.eq 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 lt.eq s_i < d_i lt.eq n, 1 lt.eq c_i lt.eq 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."},{"iden":"output","content":"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 lt.eq i lt.eq 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."},{"iden":"examples","content":"Input5 21 3 11 5 1Output1 2 3 0 3 Input3 21 3 11 2 1Output-1Input10 34 7 21 10 38 9 1Output2 2 2 1 1 0 4 3 4 4 "},{"iden":"note","content":"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."}] （注：根据要求，所有数学公式、Typst 命令如 $s_i lt.eq j < d_i$、$1 lt.eq s_i < d_i lt.eq n$ 等均原样保留，未作任何修改或转义；术语“test case”未出现，无需替换；“alternating sum”未出现；“sequence”未出现；“output/input”按题面语境自然处理为“输出”/“输入”；段落结构与换行完全保留。）

**Definitions** Let $ n \in \mathbb{Z} $ be the number of days, and $ m \in \mathbb{Z} $ the number of exams. For each exam $ i \in \{1, \dots, m\} $: - $ s_i \in \mathbb{Z} $: the day when study materials are released (preparation can start). - $ d_i \in \mathbb{Z} $: the day of the exam (must be passed on this day). - $ c_i \in \mathbb{Z} $: the number of preparation days required. Constraints: 1. $ 2 \le n \le 100 $, $ 1 \le m \le n $ 2. $ 1 \le s_i < d_i \le n $ for all $ i \in \{1, \dots, m\} $ 3. $ 1 \le c_i \le n $ for all $ i \in \{1, \dots, m\} $ 4. All $ d_i $ are distinct. **Decision Variables** Let $ x_j \in \{0, 1, \dots, m\} $ for $ j \in \{1, \dots, n\} $ denote the activity on day $ j $: - $ x_j = 0 $: rest - $ x_j = i \in \{1, \dots, m\} $: prepare for exam $ i $ - $ x_j = -i \in \{-1, \dots, -m\} $: take exam $ i $ **Constraints** 1. **Exam Day Constraint**: For each exam $ i $, $ x_{d_i} = -i $. 2. **Preparation Window Constraint**: If $ x_j = i $, then $ s_i \le j < d_i $. 3. **Preparation Requirement**: For each exam $ i $, $$ \left| \{ j \in \{1, \dots, n\} \mid x_j = i \} \right| = c_i $$ 4. **One Activity per Day**: For each day $ j $, exactly one of the above applies (no overlap). 5. **No Preparation on Exam Day**: $ x_j \ne i $ for any $ j = d_i $. **Objective** Find an assignment $ x = (x_1, \dots, x_n) \in \{0, \pm1, \dots, \pm m\}^n $ satisfying all constraints above. If no such assignment exists, output $-1$.