G. Гирлянда
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Новогодняя гирлянда после включения загорается на $$$A$$$ минут, потом гаснет на $$$A$$$ минут, потом опять загорается на $$$A$$$ минут, гаснет на $$$A$$$, и так до бесконечности. Параметр $$$A$$$ задаётся пользователем перед первым включением гирлянды и может быть любым натуральным числом.

Детишки расстроятся, если во время праздников, которые начинаются в момент времени $$$0$$$ и заканчиваются в момент времени $$$T$$$, гирлянда будет гореть меньше половины времени.

В гости к детишкам на праздники приезжает дедушка, который не любит горящие гирлянды. Вам известны интервалы времени, в которые он будет присутствовать дома. Найдите такое значение параметра $$$A$$$ и время включения гирлянды, которые позволят минимизировать длительность времени нахождения дедушки дома с включенной гирляндой и при этом не приведут к расстройству детишек. Учтите, что включить гирлянду можно в любой целочисленный момент времени, в том числе до наступления праздников, но выключить её после включения уже нельзя.

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

Первая строка содержит длительность новогодних праздников $$$T$$$ ($$$1 \le T \le 5000$$$) в минутах и количество интервалов $$$N$$$ ($$$0 \le N \le T/2$$$).

В следующих $$$N$$$ строках заданы интервалы времени, в которые дедушка будет присутствовать дома, — начало интервала $$$L_i$$$ и конец интервала $$$R_i$$$ ($$$0 \le L_i \lt R_i \le T$$$). Интервалы не пересекаются и упорядочены по возрастанию времени начала ($$$R_i \lt L_{i+1}$$$).

Все числа во входных данных целые.

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

Выведите три числа: минимальную длительность времени, которую дедушка вынужден будет провести дома с включённой гирляндой, искомое значение параметра $$$A$$$ и момент времени включения гирлянды.

Если существует несколько решений, выведите решение с минимальным значением $$$A$$$. Если и таких решений существует несколько, выведите решение с самым поздним временем включения гирлянды.

Примеры
Входные данные
10 2
1 4
7 10
Выходные данные
2 1 0
Входные данные
8 2
1 3
5 7
Выходные данные
0 2 -1
Входные данные
6 1
0 4
Выходные данные
1 3 3
Входные данные
5 1
0 5
Выходные данные
3 1 0
Входные данные
4 0
Выходные данные
0 1 1