Банк
Олимбанк периодически обновляет свои прогнозы почасовой прибыли на будущее. Аналитики банка изучают различные временные промежутки, для которых доступен почасовой прогноз. Их интересует максимальное среднее значение прибыли за определённый промежуток времени, то есть отрезок, состоящий из двух или более часов, который полностью находится в пределах заданного промежутка и имеет наибольшее среднее арифметическое значений прибыли. Разные аналитики могут интересоваться разными временными промежутками.
Задача
Напишите программу, которая, используя данные о почасовом прогнозе прибыли Олимбанка и обновления к этому прогнозу, отвечает на запросы аналитиков о максимальной среднечасовой прибыли на заданных временных промежутках.
Входные данные
Первая строка содержит два целых числа N и M — количество часов, на которые доступен прогноз, и общее количество операций двух типов: запросов аналитиков и обновлений прогноза. Вторая строка содержит N целых чисел: i-е число A[i] (–10^8 ≤ A[i] ≤ 10^8) задаёт начальный прогноз на i-й час (положительные значения означают прибыль, отрицательные — убытки). Следующие M строк описывают операции. Первое число в каждой строке указывает тип операции: 1, если это обновление прогноза, или 2, если это запрос аналитика.
• В случае обновления прогноза далее в строке следуют три целых числа L, R, X (1 ≤ L ≤ R ≤ N, –10^3 ≤ X ≤ 10^3, X ≠ 0) — границы отрезка прогноза, на котором (включительно с концами) нужно изменить все значения прогноза на величину X.
• В случае запроса аналитика далее в строке следуют два целых числа L, R (1 ≤ L < R ≤ N) — границы отрезка запроса (включительно с концами).
Гарантируется, что во входных данных есть хотя бы один запрос аналитика.
Выходные данные
Для каждого запроса аналитика выведите в отдельной строке два целых числа L[M] и R[M] — концы отрезка (включительно), на котором достигается максимальное среднее значение прибыли (должно выполняться условие L ≤ L[M] < R[M] ≤ R, где L, R — границы соответствующего запроса). Если таких отрезков несколько, выведите любой из них.
Примеры
Оценивание
Выполняются следующие дополнительные условия:
2 ≤ N, M ≤ 100 — 15% тестов;
2 ≤ N, M ≤ 1000 — 35% тестов;
2 ≤ N, M ≤ 60000 — 50% тестов.