29214번 - Водохранилище Пумбы 다국어

Пумба очень запасливый. В связи с возможной засухой, он решил запастись водой. У Пумбы есть $n$ деревянных пронумерованных тазиков. Объем кадого тазика равен $m$ литров. Запасаться водой Пумба будет на протяжении $k$ дней. В каждый день заготовки Пумба может сделать ровно одно из следующих действий:

• долить $c_i$ литров воды во все тазики с номерами от $l_i$ до $r_i$ включительно. При этом если в тазик не поместится $c_i$ литров, Пумба его полностью заполнит водой.
• спросить у Тимона суммарное количество литров воды в тазиках с номерами от $l_i$ до $r_i$ включительно.

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

В первой строке находятся три целых числа $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$).

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