До пятидесятилетия известного писателя Берляева осталось несколько дней. По этому поводу в местной библиотеке решили организовать выставку сочинений известного фантаста. Также было решено, что необходимо выбрать все книги, изданные автором за какой-то интервал времени. Понятно, что если книги будут очень сильно различаться по размерам, то посетителям это не понравится. Поэтому, посовещавшись, организаторы пришли к мнению, что высота самой низкой и самой высокой книг, отобранных для экспозиции, должны отличаться не более чем на k миллиметров.
В библиотеке имеется n томов произведений Берляева, расположенных в хронологическом порядке выпуска в свет. Про каждую книгу известна ее высота в миллиметрах hi. Поскольку юбиляр является очень уважаемым в городе человеком, то организаторы хотят представить на выставке наибольшее число его книг, а также узнать, какие при этом периоды творчества писателя они смогут охватить. Помогите организаторам справиться с этой нелегкой задачей.
Выходные данные
В первую строку выходных данных выведите через пробел два числа a и b. Число a означает наибольшее количество книг, которое организаторы смогут представить на выставке, а число b — количество интервалов времени таких, что в каждый из них писатель Берляев издал a книг, и самая высокая из этих книг превосходит самую низкую не более чем на k миллиметров.
В последующие b строк выведите по два целых числа через пробел — номер первого и последнего тома каждого из искомых периодов творчества Берляева.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
14 12 10
|
2 2
1 2
2 3
|
|
2
|
2 0
10 10
|
2 1
1 2
|
|
3
|
4 5
8 19 10 13
|
2 1
3 4
|