Глеб — известный спортивный программист из Иннополиса. Он планирует поехать на N сборов по программированию в ближайшем будущем. Каждые сборы будут проходить в другой стране. И для въезда в каждую из этих стран Глебу нужно получать визу.
Для каждой поездки Глебу известны три числа: номер первого дня поездки si, продолжительность поездки в днях leni и количество дней ti, которое консульство соответствующей страны тратит на оформление визы. Глеб имеет P (1 ≤ P ≤ 2) действующих паспортов и может решать, в какой паспорт проставлять какую визу.
В каждую поездку Глеб улетает рано утром для si и возвращается поздно вечером дня si + leni - 1.
Чтобы подать паспорт на визу в день d, Глебу нужно быть в Иннополисе в середине соответствующего дня. Поэтому он не может подавать на визу, пока он в другой поездке, включая ее первый и последний день. Если поездка начинается на следующий день после окончания предыдущей, Глеб не может подать на визу между ними. Самое раннее, когда Глеб может подать на визу — это день номер 1.
После подачи на визу страны i в день d Глеб получит паспорт назад в середине дня d + ti. Консультсва используют службы доставки, поэтому он может получить свой паспорт, даже если находится в поездке в этот день. Но Глеб может подать паспорт на другую визу в день получения паспорта, но только если в этот день он находится в Иннополисе в этот день.
Глеб не может начать поездку в день si, если он не имеет визы соответствующей страны утром дня si. И паспорт с нужной визой не должен в этот день находится в консульстве другой страны.
Помогите Глебу решить, какие визы ему нужно получать в какой паспорт и в какой день подавать на каждую из виз.
В первой строке входных данных находятся два целых числа N (1 ≤ N ≤ 22) и P (1 ≤ P ≤ 2): количество поездок и количество паспортов у Глеба соответственно.
Следующие N строк описывают поездки Глеба. Каждая строка описания содержит три положительных целых числа si, leni, ti (1 ≤ si, leni, ti ≤ 109): первый день поездки, продолжительность поездки и количество дней, которое требуется для получения соответствующей визы. Гарантируется, что никакие две поездки не пересекаются.
Если невозможно получить все визы во-время, просто выведите "NO" без кавычек.
В другом случае в первой строке выведите "YES", а затем N строк, соответствующих поездкам. Для каждой поездки выведите сначала номер паспорта, в который Глеб будет проставлять соответствующую визу, а затем номер дня, в который следует подавать на эту визу. Дни нумеруются с 1, начиная с первого дня, когда Глеб может подать на визу. Паспорта нумеруются от 1 до P.
Если существует несколько решений, то выведите любое из них.
2 1
3 1 1
6 1 1
YES
1 1
1 4
3 1
13 2 2
7 3 1
19 3 4
YES
1 10
1 1
1 2
7 2
15 1 1
14 1 1
18 1 1
21 1 1
9 4 6
22 2 5
5 4 3
YES
2 13
1 1
1 16
1 19
1 2
2 16
2 1
3 1
7 3 1
13 2 3
19 3 4
NO
Примеры с ответом "YES" изображены ниже.
На рисунке каждая ячейка ленты соответствует одному дню. Прямоугольники представляют поездки (каждая поездка начинается утром и заканчивается вечером). Прямоугольники с угловыми краями представляют оформления виз. Каждая подача начинается в середине дня и заканчивается ti дней спустя. Поездка и получение визы в соответствующую страну обозначены одним и тем же цветом.
В примерах с двумя паспортами, оформления виз и поездка написанные сверху делаются с помощью первого паспорта, а написанные снизу делаются с помощью второго паспорта.
Example 1:
Example 2:
Example 3:
