Fallen Leaves

問題文

$N$ 枚のタイルが一列に並んだ道があり、タイルには順に $1$ 番から $N$ 番まで番号が付けられています。
はじめ、$i$ 番のタイルの上には $A_i$ 枚の落ち葉があります。

$Q$ 個のクエリが与えられるので、順に処理してください。
クエリは以下の $3$ 種類あります。

• タイプ $1$ : 1 i で与えられる。 $i$ 番のタイルの上の落ち葉を全て $i+1$ 番のタイルの上に移動する。
• タイプ $2$ : 2 i で与えられる。 $i$ 番のタイルの上の落ち葉を全て $i-1$ 番のタイルの上に移動する。
• タイプ $3$ : 3 L R で与えられる。 $L$ 番から $R$ 番までのタイルの上に現在ある落ち葉の合計枚数を出力する。

制約

• $1\leq N\leq 2\times 10^5$
• $0\leq A_i\leq 10^9$
• $1\leq Q\leq 2\times 10^5$
• タイプ $1$ のクエリについて、$1\leq i\leq N-1$
• タイプ $2$ のクエリについて、$2\leq i\leq N$
• タイプ $3$ のクエリについて、$1\leq L\leq R \leq N$
• クエリの中にタイプ $3$ が少なくとも $1$ つ含まれる
• 入力される値はすべて整数

入力

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

各クエリは以下のいずれかの形式で与えられる。

出力

タイプ $3$ のクエリの個数を $M$ として、$M$ 行出力せよ。
$k$ 行目には $k$ 番目のタイプ $3$ のクエリについての答えを出力せよ。

サンプル 1

入力

5
1 2 0 3 2
7
3 2 4
1 1
3 2 4
2 4
2 3
1 3
3 3 4

出力

5
6
0

はじめ、各タイル上の落ち葉の枚数は、$(1,2,0,3,2)$ です。
クエリごとに、以下のようになります。

• $2$ 番から $4$ 番までのタイル上には $2+0+3=5$ 枚の落ち葉がある。
• $1$ 番のタイル上にある $1$ 枚を $2$ 番の上に移動し、落ち葉の枚数が $(0,3,0,3,2)$ となる。
• $2$ 番から $4$ 番までのタイル上には $3+0+3=6$ 枚の落ち葉がある。
• $4$ 番のタイル上にある $3$ 枚を $3$ 番の上に移動し、落ち葉の枚数が $(0,3,3,0,2)$ となる。
• $3$ 番のタイル上にある $3$ 枚を $2$ 番の上に移動し、落ち葉の枚数が $(0,6,0,0,2)$ となる。
• $3$ 番のタイル上にある $0$ 枚を $4$ 番の上に移動し、落ち葉の枚数が $(0,6,0,0,2)$ となる。
• $3$ 番から $4$ 番までのタイル上には $0+0=0$ 枚の落ち葉がある。

サンプル 2

入力

5
1000000000 1000000000 1000000000 1000000000 1000000000
1
3 1 5

出力

5000000000

答えは $32$ bit 整数に収まらないことがあります。

サンプル 3

入力

12
48271 9036 175204 68012 329587 1405 76294 508913 21760 93482 6517 284106
12
3 2 9
1 3
2 8
3 3 8
2 5
1 10
3 5 11
1 4
2 7
3 4 4
1 6
3 1 12

出力

1190211
1159415
708371
0
1622587