Ряды Ошского базара
Ошский базар (Жайма-базар) — один из старейших базаров Центральной Азии: здесь торговали ещё во времена Великого шёлкового пути. Вдоль главного прохода в один ряд стоят n прилавков, пронумерованных от 1 до n. У прилавка i установлена цена a[i] сомов за килограмм товара.

Жайма-базар в Оше. Фото: Bgag, CC0, Wikimedia Commons
Нургуль работает аналитиком в администрации базара. В течение дня к ней поступают q сообщений трёх видов:
1 l r x— продавцы прилавков сlпоr(включительно) одновременно меняют цены наxсомов (еслиx < 0, цены снижаются; цена может стать и отрицательной — это означает, что продавец доплачивает за вывоз товара);2 l r x— администрация устанавливает на прилавках сlпоrединую ценуx;3 l r— нужно сообщить сумму цен на прилавках сlпоrи наибольшую из этих цен.
Помогите Нургуль ответить на все сообщения третьего вида.
Входные данные
В первой строке — два целых числа n и q (1 ≤ n, q ≤ 300 000).
Во второй строке — n целых чисел a[1], …, a[n] (0 ≤ a[i] ≤ 10⁹).
В каждой из следующих q строк — одно сообщение в указанном формате (1 ≤ l ≤ r ≤ n). Для сообщений первого вида |x| ≤ 10⁴, для второго вида 0 ≤ x ≤ 10⁹.
Выходные данные
Для каждого сообщения третьего вида выведите в отдельной строке два числа: сумму и максимум цен на отрезке.
Пример 1
Вход:
6 6
5 3 8 1 4 2
3 2 5
1 1 3 2
3 1 6
2 3 6 7
1 4 5 -10
3 1 6
Выход:
16 8
29 10
20 7
Пояснение
После второго сообщения цены равны 7 5 10 1 4 2, после четвёртого — 7 5 7 7 7 7, после пятого — 7 5 7 −3 −3 7.
Система оценивания
| Подзадача | Баллы | Дополнительные ограничения |
|---|---|---|
| 1 | 20 | n, q ≤ 3000 |
| 2 | 25 | нет сообщений второго вида |
| 3 | 55 | без дополнительных ограничений |
Баллы за подзадачу начисляются, только если пройдены все её тесты.
Примечание
Объём входных данных велик: используйте быстрый ввод-вывод. Сумма может не поместиться в 32-битный тип.
Комментарии