G. Лучшее среднее при изменениях

То же, что в предыдущей задаче, но добавляется операция: прибавить $x$ ко всем элементам отрезка.

Наблюдение про длины 2 и 3 остаётся верным — оно не зависит от значений. Значит нужны те же два массива $P$ и $T$, но теперь они должны переживать прибавление на отрезке.

В первой строке $n$ и $q$ ($2 \le n \le 10^5$, $1 \le q \le 10^5$). Во второй — $n$ чисел $a_i$ ($1 \le a_i \le 10^9$). Далее $q$ строк: 1 l r x — прибавить $x$ на отрезке ($1 \le x \le 10^9$), или 2 l r ($l < r$) — наибольшее среднее подотрезка длины не меньше двух внутри $[l, r]$.

Для каждого запроса второго типа выведите ответ на отдельной строке.