eolymp
bolt
Try our new interface for solving problems
Problems

38 попугаев

38 попугаев

Time limit 2 seconds
Memory limit 128 MiB

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

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

Input data

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

Output data

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

Examples

Input example #1
5
5
2 3 12
1 1 5
1 1 2
2 3 9
1 1 5
Output example #1
12 1
10 2
10 4
Author Alexandr Burkov
Source Distance Summer Computer School - Summer 2013