В деякому місті є мережа ресторанів, які мають загалом \textbf{N} практично однакових залів. Адміністрації поступило \textbf{K} заявок на проведення у передсвятковий день корпоративних заходів. У кожній заявці вказано час початку та закінчення (від \textbf{00:00} до \textbf{23:59}). Для проведення одного заходу потрбно цілком одну залу (яку конкретно, значення не має). Після закінчення заходу потрібно не менше півгодини для підготовки до наступного заходу в цій залі. Потрібно задовільнити якомога більшу кількість заявок. Якщо можна задовільнити всі, то при цьому слід використовувати найменшу кількість залів. \InputFile У першому рядку містяться числа \textbf{N} і \textbf{K} (\textbf{1} <= \textbf{N}\textit{, }\textbf{K} <= \textbf{100}). У кожному з наступних \textbf{K} рядків міститься час початку і завершення заявки у форматі \textbf{ЧЧ:ММ-ЧЧ:ММ}. Час заврешення кожної заявки хоча б на хвилину більше часу її початку. \OutputFile У першому рядку виведіть два числа --- кількість заявок \textbf{P}, які вдалось задовольнити, і кількість залів \textbf{Q}, які прийшлось задіяти. У кожному з наступних \textbf{P} рядків виведіть по два числа --- порядковий номер заявки (якою вона стояла у вхідному файлі) і номер зали. Якщо задача має декілька розв'язків, то виведіть довільний з них.