Олімбанк прогнозує свої погодинні прибутки на майбутнє, час від часу уточнюючи інформацію. Аналітики банку досліджують різні проміжки часу, для яких доступний погодинний прогноз. Для кожного такого проміжку часу аналітиків цікавить, яким є найбільше середньогодинне значення прибутку на цьому проміжку, тобто відрізок часу у дві або більше годин, який повністю лежить у межах заданого проміжку, такий, що середнє арифметичне значень прибутку на даному відрізку є якомога більшим. Крім того, різних аналітиків цікавлять різні проміжки часу.

Завдання

Напишіть програму, яка за інформацією про погодинний прогноз на прибутки Олімбанку та за уточненнями до цього прогнозу відповідає на запити аналітиків банку щодо максимального середньогодинного прибутку на заданих проміжках часу.

Вхідні дані

У першому рядку вхідих даних записано два цілих числа N та M — кількість годин, на які доступний прогноз, та сумарну кількість операцій двох типів: запитів аналітиків та уточнень прогнозу. У другому рядку міститься N цілих чисел: i-те число Ai(–108 ≤ Ai ≤ 108) задає початковий прогноз на i-ту годину (додатні значення відповідають прибутку, від’ємні — видаткам). Наступні M рядків описують операції. Першим числом у кожному рядку записано тип операції: 1, якщо це уточнення прогнозу, або 2, якщо це запит аналітика.

• У випадку операції уточнення прогнозу далі в рядку йдуть три цілих числа L, R, X ( 1 ≤ L ≤ R ≤ N, –103 ≤ X ≤ 103, X ≠ 0)  —  границі відрізка з прогнозом, на якому (включно з кінцями) треба змінити всі значення прогнозу на величину X.

• У випадку запиту аналітика далі в рядку йдуть два цілих числа L, R( 1  ≤  L  <  R  ≤  N)  — границі відрізка запиту (включно з кінцями).

Гарантується, що у вхідних даних є хоча б один запит аналітика.

Вихідні дані

Для кожного запиту аналітика в окремому рядку виведіть два цілих числа LM та RM —  кінці відрізка (включно), на якому досягається максимальне середнє значення прибутку (має справджуватися співвідношення L ≤ LM < RM ≤ R, де L, R — границі відповідного запиту). Якщо таких відрізків є кілька, виведіть будь-який із них.

Оцінювання

Виконуються такі додаткові умови:

1. 2 ≤ N, M ≤ 100 —  15% тестів;

2. 2 ≤ N, M ≤ 1000 —  35% тестів;

3. 2 ≤ N, M ≤ 60000  —  50% тестів.