Вы — ассистент режиссера новой музыкальной постановки. В сценарии постановки присутствует n музыкальных партий, каждую из которых должен исполнить ровно один актер. После кастинга режиссер выбрал m актеров, которые смогут принять участие в постановке. Ваша задача — распределить партии между актерами. Однако, существует несколько ограничений.
Во-первых, каждый актер обладает своим вокальным диапазоном, и не все партии ему подходят. Формально, каждому актеру сопоставляются два целых числа ci и di (ci ≤ di) — частота самой низкой и самой высокой ноты, которую актер способен спеть. Каждой партии также сопоставляются два целых числа — aj и bj (aj ≤ bj) — частота самой низкой и самой высокой ноты, которые присутствуют в партии. i-й актер способен исполнить j-ю партию тогда и только тогда, когда ci ≤ aj ≤ bj ≤ di, т.е. каждая нота партии попадает в вокальный диапазон актера.
Кроме этого, согласно контракту, i-й актер имеет право исполнить не более ki партий. При этом разрешается не назначать некоторым актерам ни одной партии (тогда они поучаствуют в массовых сценах).
Репетиции начинаются через два часа, и вам нужно срочно справиться с распределением!
Выходные данные
Если существует распределение, удовлетворяющее всем требованиям, в первой строке выведите одно слово «YES» (без кавычек).
В следующей строке выведите n целых чисел через пробел. i-е число должно быть равно номеру актера, который исполнит i-ю партию. Если существует несколько корректных распределений, выведите любое.
Если распределения не существует, выведите одно слово «NO» (без кавычек).
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 3
2 4
3 5
2
1 4 2
2 5 1
|
YES
1 1 2
|
|
2
|
3
1 3
2 4
3 5
2
1 3 2
2 5 1
|
NO
|