Банк

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

Завдання

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

Input

У першому рядку вхідного файлу записано два цілих числа $N$ та $M$ ($2\le N,M\le 50000$) — кількість годин, на які доступний прогноз, та сумарну кількість операцій двох типів: уточнень прогнозу та запитів аналітиків.

У другому рядку міститься $N$ цілих чисел: $i$-те число $A_i$ ($–10^8\le A_i\le 10^8$) задає початковий прогноз на $i$-ту годину (додатні значення відповідають прибутку, від’ємні — збиткам).

Наступні $M$ рядків описують операції. Першим числом у кожному рядку записано тип операції: 1, якщо це уточнення прогнозу, або 2, якщо це запит аналітика.

• У випадку операції уточнення прогнозу далі в рядку йдуть три цілих числа $L$, $R$, $X$ ($1\le L\le R\le N$, $–10^3\le X\le 10^3$, $X\ne 0$) — межі відрізка з прогнозом, на якому (включно з кінцями) треба додати до всіх значень прогнозу величину $X$.

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

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

Output

У вихідний файл для кожного запиту аналітика в окремому рядку виведіть два цілих числа $L_M$ та $R_M$ — кінці відрізка (включно), на якому досягається максимальне середнє значення прибутку (має справджуватися співвідношення $L\le L_M<R_M\le R$, де $L$, $R$ — межі відповідного запиту). Якщо таких відрізків є кілька — виведіть будь-який з них.

Examples

Scoring

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

1. ($15$ балів): $2\le N,M\le 100$;

2. ($50$ балів): $2\le N,M\le 3000$;