C. Реформа образования
ограничение по времени на тест
1 second
ограничение по памяти на тест
256 megabytes
ввод
stdin
вывод
stdout

Недавно в Берляндии была проведена очередная образовательная реформа. Суть ее состоит в следующем.

Теперь учебный год состоит из n дней. Каждый день ученики занимаются ровно одним из m предметов, причем каждому предмету отводится не более одного дня. После завершения занятий по i-ому предмету школьники получают домашнее задание, содержащее не менее ai и не более bi упражнений. Кроме того, для каждого предмета определяется специальная характеристика — сложность (ci). Школа имеет право самостоятельно составлять расписание занятий, однако при этом должны быть выполнены следующие условия:

  • предметы в расписании должны располагаться в порядке строгого возрастания сложности;
  • каждый день, за исключением первого, задание должно содержать либо в k раз больше, либо на k больше упражнений, чем в предыдущий (более формально: пусть xi — количество упражнений в домашнем задании в i-ый день, тогда для каждого i (1 < i ≤ n) должно выполняться либо xi = k + xi - 1, либо xi = k·xi - 1);
  • суммарное число упражнений во всех заданиях должно быть максимально возможным.

Все ограничения устанавливаются для каждой школы отдельно.

Оказалось, что ai и bi во многих случаях достигают 1016 (однако, поскольку министр образования Берляндии славится своей любовью к полумерам, величина bi - ai не превосходит 100). Случилось так и в Берляндской школе №256. Тем не менее, Вам — как директору этой школы — все равно придется составить расписание для следующего учебного года...

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

В первой строке записаны три целых числа n, m, k (1 ≤ n ≤ m ≤ 50, 1 ≤ k ≤ 100) — количество дней в учебном году, количество предметов и параметр k соответственно. В каждой из следующих m строк содержится описание одного предмета: три целых числа ai, bi, ci (1 ≤ ai ≤ bi ≤ 1016, bi - ai ≤ 100, 1 ≤ ci ≤ 100) — два ограничения на количество упражнений по i-ому предмету и сложность i-ого предмета соответственно. Различные предметы могут иметь одинаковую сложность. Предметы пронумерованы целыми числами от 1 до m.

Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать поток cin или спецификатор %I64d.

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

Если не существует ни одного корректного расписания, выведите единственное слово «NO» (без кавычек). В противном случае первая строка должна содержать слово «YES» (без кавычек), а следующие n строк — любое расписание, удовлетворяющее всем требованиям. В i + 1-ой строке следует вывести два натуральных числа: номер предмета, которым необходимо заниматься в i-ый день, и количество упражнений в домашнем задании по этому предмету. В расписании должно быть ровно n предметов.

Примеры
Входные данные
4 5 2
1 10 1
1 10 2
1 10 3
1 20 4
1 100 5
Выходные данные
YES
2 8
3 10
4 20
5 40
Входные данные
3 4 3
1 3 1
2 4 4
2 3 3
2 2 2
Выходные данные
NO