(А. Богданов) Проводится вычислительный эксперимент для определения необходимого количества самокатов на разных парковках города в начальный момент времени. Всего есть M парковок с номерами от 1 до М. Поступило всего N заявок на аренду самокатов. В каждой заявке указано время начала аренды в минутах от начала суток, продолжительность аренды, а также номера парковок старта и финиша. Будем считать, что заряда самоката хватает на весь день и самокат может быть арендован со следующей минуты после окончания предыдущей аренды.
Определите, начиная с какого момента (в минутах от начала эксперимента) было арендовано максимальное количество самокатов, и номер парковки, на которой нужно установить максимальное количество самокатов.
Входные данные представлены в файле 26-123.txt следующим образом. Первая строка входного файла содержит два натуральных числа, записанных через пробел: M (1 ≤ M ≤ 100) -- количество парковок, и N (1 ≤ N ≤ 106) -- количество заявок. Каждая из N последующих строк описывает содержит четыре целых числа: время начала аренды в минутах от начала суток, длительность аренды в минутах, номер парковки старта и номер парковки финиша.
В ответе запишите два числа: сначала время (в минутах от начала эксперимента), когда впервые началась аренда максимального количества самокатов, затем -- номер парковки, на которой нужно установить максимальное количество самокатов.
Пример входного файла:
2 3
1 4 2 2
3 6 1 1
5 9 1 2
При таких исходных данных нужно три самоката: два в начале размещаются на парковке 1 и один -- на парковке 2. Одновременно в аренде находятся максимум два самоката (с 3-й по 8-ю минуту включительно). Ответ: 3 1.