Pumba's Water Reservoir

Pumba is very thrifty. Worried about a possible drought, he decided to stock up on water. Pumba has $n$ numbered wooden basins. The volume of each basin is $m$ liters. Pumba will stock water over $k$ days. On each day, Pumba performs exactly one of the following actions:

• Adds $c_i$ liters of water to every basin with numbers from $l_i$ to $r_i$ inclusive. If a basin cannot hold $c_i$ liters, Pumba fills it completely.
• Asks Timon for the total amount of water in the basins with numbers from $l_i$ to $r_i$ inclusive.

Timon is very lazy, so he has assigned you to answer Pumba's questions. Before stocking begins, the $i$-th basin already contains $a_i$ liters of water.

The first line contains three integers $n$, $m$, $k$: the number of basins, the volume of one basin, and the number of days Pumba will stock water ($1 \le n \le 200000$, $1 \le m \le 10^9$, $1 \le k \le 200000$).

The second line contains $n$ integers $a_i$, the amount of water in each basin before stocking ($0 \le a_i \le m$).

Each of the next $k$ lines describes Pumba's action on that day. If on day $i$ Pumba adds water, the first number of the line is 1, followed by three integers $l_i$, $r_i$, $c_i$ ($1 \le l_i \le r_i \le n$, $1 \le c_i \le 10^9$). If on day $i$ Pumba asks for the total, the first number of the line is 2, followed by two integers $l_i$ and $r_i$ ($1 \le l_i \le r_i \le n$).

For each of Pumba's questions, print the answer on its own line, in the order the questions are given.