Сессия Пети продлится \(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\).
Петя может иметь перерывы между днями подготовки к одному экзамену, он может чередовать по дням подготовку к разным экзаменам. Таким образом, подготовка к одному экзамену не обязательно должна осуществляться в последовательные дни.
Определите расписание подготовки Пети, в соответствии с которым, он успешно сможет подготовиться ко всем экзаменам и сдать их, либо сообщите, что это невозможно.
Выходные данные
Если Петя не сможет подготовиться и сдать все экзамены, выведите -1.
В случае положительного ответа выведите \(n\) целых чисел, где \(j\)-е число равно:
- \((m + 1)\), если в \(j\)-й день проводится экзамен (напомним, что в каждый день сессии проводится не более одного экзамена),
- нулю, если в \(j\)-й день Петя будет отдыхать,
- равно \(i\) (\(1 \le i \le m\)), если в \(j\)-й день Петя будет готовиться к \(i\)-му экзамену (суммарное количество дней подготовки к каждому экзамену согласно расписанию должно быть в точности равно количеству дней, необходимых для подготовки к нему).
Экзамены нумеруются в том же порядке, в котором встречаются во входных данных, начиная с \(1\).
Если возможных ответов (расписаний) несколько, то выведите любой из них.
Примечание
В первом примере Петя может, например, готовиться к экзамену \(1\) в первый день, готовиться к экзамену \(2\) во второй день, в третий день сдать экзамен \(1\), в четвертый день отдыхать, а в пятый день сдать экзамен \(2\). Таким образом, он сумеет подготовиться и сдать все экзамены.
Во втором примере сессия длится три дня и состоится два экзамена. Таким образом, на подготовку остаётся всего один день (так как два других дня заняты сдачей экзаменов). Поэтому Петя не сможет сдать все экзамены.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5 2
1 3 1
1 5 1
|
1 2 3 0 3
|
|
2
|
3 2
1 3 1
1 2 1
|
-1
|
|
3
|
10 3
4 7 2
1 10 3
8 9 1
|
2 2 2 1 1 0 4 3 4 4
|