eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

38 попугаев

38 попугаев

Лимит времени 2 секунды
Лимит использования памяти 128 MiB

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

Все что от Вас требуется, это найти длину самого большого попугая на определенном отрезке (так как не все попугаи хотят участвовать в этой увлекательной идее), а также количество таких попугаев (чтобы им можно было выбрать одного из них).

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

В первой строке находится число N (1N10^9) – количество попугаев. Длины всех попугаев изначально равны десяти сантиметрам. Во второй строке находится число M (1M10^5) – количество запросов. Каждый запрос состоит из трех чисел – x, l, r. Если значение x равно единице, то Вам необходимо вывести два числа в отдельной строке – максимальная длина попугаев на отрезке [l; r] и количество попугаев с этой длиной на этом же отрезке, гарантируется, что этот отрезок будет являться подотрезком исходного. Если значение x равно двум, то длина попугая с номером l изменилась и теперь она равна r. Гарантируется, что попугай с номером l существует, а число r никогда не превысит значения 2·10^9.

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

Для каждого запроса с номером один выведите два числа – ответ на запрос.

Пример

Входные данные #1
5
5
2 3 12
1 1 5
1 1 2
2 3 9
1 1 5
Выходные данные #1
12 1
10 2
10 4
Автор Александр Бурков
Источник Дистанционная Летняя Компьютерная Школа - лето 2013 года