1396 - 惑星ヤナイヅの資源

問題

人類はついに知的生命体の存在する惑星ヤナイヅを発見した。惑星ヤナイヅでは科学が進歩していたので、次第に我々との共同研究が盛んにおこなわれるようになった。

惑星ヤナイヅではベコという虫が重要な資源とみなされている。ベコは幼虫からう化して成虫になる。ベコの生息域ではベコの幼虫が群れて生息している群生がいくつもあり、そのような群生が一列に並んでいる。惑星ヤナイヅのバイオテクノロジーを使うと、群生に対して以下のような操作ができる。

• 指定した範囲のすべての群生に、同じ数の幼虫を追加する。
• 指定した範囲のすべての群生で、指定した数の幼虫を成虫にう化させ、う化した幼虫の数の合計を求める。このとき、う化させる幼虫の数を一つだけ指定できる。

２つ目の操作では、指定した数よりも幼虫の数が少ない群生については、その群生にいるすべての幼虫をう化させる。たとえば、群生１に幼虫が３匹、群生２に幼虫が２匹いる場合、群生１から２の範囲に対してう化させる数３を指定すると、群生１からは３匹、群生２からは２匹を成虫にすることになる。このときにう化した幼虫の数の合計は５匹である。

今回の共同研究では、我々人類がベコの幼虫に対するこれらの操作のシミュレーションを担当することとなった。ここは我々の科学の力を示すときである。

各群生に存在する幼虫の情報が与えられたとき、それらに対する操作をシミュレーションするプログラムを作成せよ。

入力

入力は以下の形式で与えられる。

$N$
$c_1$
$c_2$
:
$c_N$
$M$
$manip_1$
$manip_2$
:
$manip_M$

１行目に群生の数$N$ ($1 \leq N \leq 100,000$)が与えられる。続く$N$行に、各群生にいる幼虫の数$c_i$ ($0 \leq c_i \leq 100,000$)が与えられる。

  続く１行に、操作の数$M$ ($1 \leq M \leq 100,000$)が与えられる。続く$M$行に操作の内容が与えられる。各操作の内容は次のいずれかである。

1 $a$ $b$ $d$

または

2 $a$ $b$ $d$

先頭の数字が1のとき、指定した範囲$a$から$b$ ($1 \leq a \leq b \leq N$)の群生に対して、幼虫を$d$匹($1 \leq d \leq 1,000$)追加する。先頭の数字が2のとき、指定した範囲$a$から$b$ ($1 \leq a \leq b \leq N$)の群生に対して、幼虫を$d$匹($1 \leq d \leq 1,000$)だけ成虫にう化させる操作を表す。このとき、実際にう化した幼虫の合計を出力する。また、先頭の数字が2である操作は必ずひとつ以上与えられるものとする。

出力

幼虫をう化させる操作ごとに、実際にう化した幼虫の合計を１行に出力する。

入出力例

入力例

3
1
2
3
3
2 1 3 2
1 1 2 5
2 2 3 3

出力例

5
4