У Фафы есть массив A из n положительных чисел, определим функцию f(A) как 
. Он хочет обработать q запросов двух типов:
- 1 l r x — найти максимальное возможное значение f(A), если к одному из элементов отрезка [l, r] предварительно добавить x. Вы можете выбирать, к какому элементу добавить x.
- 2 l r x — прибавить ко всем элементам на отрезке [l, r] число x.
Обратите внимание, что запросы типа 1 не изменяют массив.
Выходные данные
Для каждого запроса типа 1 выведите ответ на него.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 1 1 1 1
5
1 2 4 1
2 2 3 1
2 4 4 2
2 3 4 1
1 3 3 2
|
2
8
|
|
2
|
5
1 2 3 4 5
4
1 2 4 2
2 2 4 1
2 3 4 1
1 2 4 2
|
6
10
|