품바의 물 저장고

품바는 매우 알뜰하다. 가뭄이 올지도 모른다고 생각해서 물을 비축하기로 했다. 품바에게는 번호가 매겨진 나무 대야 $n$개가 있다. 각 대야의 용량은 $m$리터이다. 품바는 $k$일 동안 물을 비축한다. 매일 품바는 다음 중 정확히 한 가지 행동만 한다.

• 번호가 $l_i$부터 $r_i$까지인 대야에 물을 $c_i$리터씩 붓는다(양 끝 포함). 대야에 $c_i$리터가 다 들어가지 않으면 품바는 그 대야를 가득 채운다.
• 번호가 $l_i$부터 $r_i$까지인 대야에 든 물의 총량을 티몬에게 묻는다(양 끝 포함).

티몬은 매우 게을러서, 품바의 질문에 답하는 일을 당신에게 맡겼다. 비축을 시작하기 전에 $i$번째 대야에는 이미 $a_i$리터의 물이 들어 있다.

첫째 줄에 정수 $n$, $m$, $k$가 주어진다. $n$은 대야의 개수, $m$은 대야 하나의 용량, $k$는 품바가 물을 비축하는 날수이다 ($1 \le n \le 200000$, $1 \le m \le 10^9$, $1 \le k \le 200000$).

둘째 줄에는 비축하기 전 각 대야의 물의 양 $a_i$가 $n$개 주어진다 ($0 \le a_i \le m$).

이어지는 $k$개의 줄은 날마다 품바의 행동을 나타낸다. 물을 붓는 날이면 줄의 첫 수는 1이고, 이어서 정수 $l_i$, $r_i$, $c_i$가 주어진다 ($1 \le l_i \le r_i \le n$, $1 \le c_i \le 10^9$). 물의 총량을 묻는 날이면 줄의 첫 수는 2이고, 이어서 정수 $l_i$, $r_i$가 주어진다 ($1 \le l_i \le r_i \le n$).

품바의 질문마다 답을 한 줄에 하나씩, 질문이 주어진 순서대로 출력한다.