\begin{problem}{Водохранилище Пумбы}{water.in}{water.out}{4 секунды}{}

%Автор задачи: Виталий Демьянюк
%Автор условия: Виталий Демьянюк

Пумба очень запасливый. В связи с возможной засухой, он решил запастись водой. У Пумбы есть $n$ деревянных пронумерованных тазиков.
Объем кадого тазика равен $m$ литров. Запасаться водой Пумба будет на протяжении $k$ дней. 
В каждый день заготовки Пумба может сделать ровно одно из следующих действий: 
\begin{itemize}
\item долить $c_i$ литров воды во все тазики с номерами от $l_i$ до $r_i$ включительно. 
При этом если в тазик не поместится $c_i$ литров, Пумба его полностью заполнит водой.
\item спросить у Тимона суммарное количество литров воды в тазиках с номерами от $l_i$ до $r_i$ включительно. 
\end{itemize}

Тимон очень ленивый, поэтому он поручил вам отвечать на вопросы Пумбы. Перед заготовкой в $i$-м тазике уже содержалось $a_i$ 
литров воды.

\InputFile

В первой строке находятся три целых числа $n$, $m$, $k$~--- количество тазиков, объем одного тазика и количество дней, на протяжении которых 
Пумба будет запасаться водой ($1 \le n \le 200000$, $1 \le m \le 10^9$, $1 \le k \le 200000$). 

Во второй строке содержатся $n$ чисел $a_i$~--- объем воды в каждом тазике перед заготовкой ($0 \le a_i \le m$).

Каждая из $k$ следующих строк содержит несколько целых чисел, описывающих действие Пумбы в соответствующий день.

Если в $i$-й день Пумба доливает воду, первое число $i$-й строки будет равно одному. За ним будут идти три целых 
числа $l_i$, $r_i$, $c_i$~--- 
границы отрезка номеров тазиков, куда Пумба будет доливать воду и объем 
доливаемой воды ($1 \le l_i \le r_i \le n$, $1 \le c_i \le 10^9$).

Если же в $i$-й день Пумба спрашивет суммарный объем воды в тазиках с номерами от $l_i$ до $r_i$ включительно, 
первое число $i$-й строки 
будет равно двум. За ним будут следовать два целых числа $l_i$ и $r_i$ соответственно ($1 \le l_i \le r_i \le n$).

\OutputFile
На каждый вопрос Пумбы выведите ответ в отдельной строке. Ответы выведите в том порядке, в котором следуют запросы.

\Examples
\begin{example}%
\exmp{
3 3 7
1 2 1
1 1 2 1
2 1 3
1 2 3 1
2 1 3
2 1 1
2 2 2
2 3 3
}{
6
7
2
3
2
}%
\end{example}
\end{problem}
