G. Сессия Пети
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Сессия Пети продлится $$$n$$$ дней и за это время ему нужно сдать $$$m$$$ экзаменов. Дни сессии пронумерованы от $$$1$$$ до $$$n$$$.

Про каждый экзамен известно три величины:

  • $$$s_i$$$ — день, когда выдадут билеты для $$$i$$$-го экзамена.
  • $$$d_i$$$ — день, когда состоится $$$i$$$-й экзамен ($$$s_i < d_i$$$).
  • $$$c_i$$$ — сколько дней нужно Пете, чтобы подготовиться к $$$i$$$-му экзамену. К $$$i$$$-му экзамену Петя может готовиться только в дни с номерами от $$$s_i$$$ до $$$d_i-1$$$, включительно.

В каждый из дней сессии Петя будет либо весь день отдыхать, либо весь день сдавать один экзамен, либо весь день готовится к одному из экзаменов, для которого уже выданы билеты. Смешивать виды активностей в один день Петя не может. Если в день $$$j$$$ Петя готовится к экзамену $$$i$$$, то $$$s_i \le j < d_i$$$.

Петя может иметь перерывы между днями подготовки к одному экзамену, он может чередовать по дням подготовку к разным экзаменам. Таким образом, подготовка к одному экзамену не обязательно должна осуществляться в последовательные дни.

Определите расписание подготовки Пети, в соответствии с которым, он успешно сможет подготовиться ко всем экзаменам и сдать их, либо сообщите, что это невозможно.

Входные данные

В первой строке следуют два целых числа $$$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$$$-й экзамен, а также количество дней, которые нужны Пете, чтобы подготовиться к $$$i$$$-му экзамену.

Гарантируется, что все экзамены состоятся в разные дни. Билеты для разных экзаменов могут быть выданы в один и тот же день. В день экзамена могут быть выданы билеты для одного или нескольких других экзаменов, которые Петя сможет узнать, но начать готовиться он сможет начать только в следующий день, так как в текущий сдаёт экзамен.

Выходные данные

Если Петя не сможет подготовиться и сдать все экзамены, выведите -1.

В случае положительного ответа выведите $$$n$$$ целых чисел, где $$$j$$$-е число равно:

  • $$$(m + 1)$$$, если в $$$j$$$-й день проводится экзамен (напомним, что в каждый день сессии проводится не более одного экзамена),
  • нулю, если в $$$j$$$-й день Петя будет отдыхать,
  • равно $$$i$$$ ($$$1 \le i \le m$$$), если в $$$j$$$-й день Петя будет готовиться к $$$i$$$-му экзамену (суммарное количество дней подготовки к каждому экзамену согласно расписанию должно быть в точности равно количеству дней, необходимых для подготовки к нему).

Экзамены нумеруются в том же порядке, в котором встречаются во входных данных, начиная с $$$1$$$.

Если возможных ответов (расписаний) несколько, то выведите любой из них.

Примеры
Входные данные
5 2
1 3 1
1 5 1
Выходные данные
1 2 3 0 3
Входные данные
3 2
1 3 1
1 2 1
Выходные данные
-1
Входные данные
10 3
4 7 2
1 10 3
8 9 1
Выходные данные
2 2 2 1 1 0 4 3 4 4
Примечание

В первом примере Петя может, например, готовиться к экзамену $$$1$$$ в первый день, готовиться к экзамену $$$2$$$ во второй день, в третий день сдать экзамен $$$1$$$, в четвертый день отдыхать, а в пятый день сдать экзамен $$$2$$$. Таким образом, он сумеет подготовиться и сдать все экзамены.

Во втором примере сессия длится три дня и состоится два экзамена. Таким образом, на подготовку остаётся всего один день (так как два других дня заняты сдачей экзаменов). Поэтому Петя не сможет сдать все экзамены.