{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePetya 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$$$.\u003c/p\u003e\u003cp\u003eThere are three values about each exam:\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$s_i$$$ — the day, when questions for the $$$i$$$-th exam will be published, \u003c/li\u003e\u003cli\u003e $$$d_i$$$ — the day of the $$$i$$$-th exam ($$$s_i \u0026lt; d_i$$$), \u003c/li\u003e\u003cli\u003e $$$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. \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eThere 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\u0027t pass/prepare for multiple exams in a day. He can\u0027t mix his activities in a day. If he is preparing for the $$$i$$$-th exam in day $$$j$$$, then $$$s_i \\le j \u0026lt; d_i$$$.\u003c/p\u003e\u003cp\u003eIt 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.\u003c/p\u003e\u003cp\u003eFind the schedule for Petya to prepare for all exams and pass them, or report that it is impossible.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe 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.\u003c/p\u003e\u003cp\u003eEach of the following $$$m$$$ lines contains three integers $$$s_i$$$, $$$d_i$$$, $$$c_i$$$ $$$(1 \\le s_i \u0026lt; 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. \u003c/p\u003e\u003cp\u003eGuaranteed, 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.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eIf Petya can not prepare and pass all the exams, print \u003cspan class\u003d\"tex-font-style-tt\"\u003e-1\u003c/span\u003e. In case of positive answer, print $$$n$$$ integers, where the $$$j$$$-th number is:\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$(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), \u003c/li\u003e\u003cli\u003e zero, if in the $$$j$$$-th day Petya will have a rest, \u003c/li\u003e\u003cli\u003e $$$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 \u003cspan class\u003d\"tex-font-style-bf\"\u003estrictly\u003c/span\u003e equal to the number of days needed to prepare for it).\u003cp\u003eAssume that the exams are numbered in order of appearing in the input, starting from $$$1$$$.\u003c/p\u003e\u003cp\u003eIf there are multiple schedules, print any of them.\u003c/p\u003e\u003c/li\u003e\u003c/ul\u003e"}},{"title":"Examples","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5 2\n1 3 1\n1 5 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 2 3 0 3 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3 2\n1 3 1\n1 2 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e10 3\n4 7 2\n1 10 3\n8 9 1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e2 2 2 1 1 0 4 3 4 4 \n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003eIn 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.\u003c/p\u003e\u003cp\u003eIn 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.\u003c/p\u003e"}}]}