Codeforces Round 481 (Div. 3) |
---|
Закончено |
Сессия Пети продлится n дней и за это время ему нужно сдать m экзаменов. Дни сессии пронумерованы от 1 до n.
Про каждый экзамен известно три величины:
В каждый из дней сессии Петя будет либо весь день отдыхать, либо весь день сдавать один экзамен, либо весь день готовится к одному из экзаменов, для которого уже выданы билеты. Смешивать виды активностей в один день Петя не может. Если в день j Петя готовится к экзамену i, то si≤j<di.
Петя может иметь перерывы между днями подготовки к одному экзамену, он может чередовать по дням подготовку к разным экзаменам. Таким образом, подготовка к одному экзамену не обязательно должна осуществляться в последовательные дни.
Определите расписание подготовки Пети, в соответствии с которым, он успешно сможет подготовиться ко всем экзаменам и сдать их, либо сообщите, что это невозможно.
В первой строке следуют два целых числа n и m (2≤n≤100,1≤m≤n) — количество дней сессии и количество экзаменов.
В следующих m строках следуют по три целых числа si, di, ci (1≤si<di≤n,1≤ci≤n) — день, когда будут выданы билеты для i-го экзамена, день, когда состоится i-й экзамен, а также количество дней, которые нужны Пете, чтобы подготовиться к i-му экзамену.
Гарантируется, что все экзамены состоятся в разные дни. Билеты для разных экзаменов могут быть выданы в один и тот же день. В день экзамена могут быть выданы билеты для одного или нескольких других экзаменов, которые Петя сможет узнать, но начать готовиться он сможет начать только в следующий день, так как в текущий сдаёт экзамен.
Если Петя не сможет подготовиться и сдать все экзамены, выведите -1.
В случае положительного ответа выведите n целых чисел, где j-е число равно:
Экзамены нумеруются в том же порядке, в котором встречаются во входных данных, начиная с 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. Таким образом, он сумеет подготовиться и сдать все экзамены.
Во втором примере сессия длится три дня и состоится два экзамена. Таким образом, на подготовку остаётся всего один день (так как два других дня заняты сдачей экзаменов). Поэтому Петя не сможет сдать все экзамены.
Название |
---|