Loading [MathJax]/jax/output/HTML-CSS/fonts/TeX/fontdata.js

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

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

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

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

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

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

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

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

В первой строке следуют два целых числа n и m (2n100,1mn) — количество дней сессии и количество экзаменов.

В следующих m строках следуют по три целых числа si, di, ci (1si<din,1cin) — день, когда будут выданы билеты для i-го экзамена, день, когда состоится i-й экзамен, а также количество дней, которые нужны Пете, чтобы подготовиться к i-му экзамену.

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

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

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

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

  • (m+1), если в j-й день проводится экзамен (напомним, что в каждый день сессии проводится не более одного экзамена),
  • нулю, если в j-й день Петя будет отдыхать,
  • равно i (1im), если в 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. Таким образом, он сумеет подготовиться и сдать все экзамены.

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