時間制限 : sec, メモリ制限 : KB
English / Japanese  

RSQ and RAQ

数列 A = {a1, a2,..., an} に対し、次の2つの操作を行うプログラムを作成せよ。

  • add(s, t, x): as, as+1,...,atxを加算する。
  • getSum(s, t): as, as+1,...,atの合計値を出力する。

ただし、ai (i = 1, 2,...,n)は、0 で初期化されているものとする。

入力

n q
query1
query2
:
queryq

1行目にAの要素数n, クエリの数qが与えられる。続くq行に i 番目のクエリ queryi が与えられる。queryi は以下のいずれかの形式で与えられる。

0 s t x

または

1 s t

各クエリの最初の数字は、クエリの種類を示し、'0'がadd(s, t, x)、'1'がgetSum(s, t)を表す。

出力

getSumクエリについて、合計値を1行に出力せよ。

制約

  • 1 ≤ n ≤ 100000
  • 1 ≤ q ≤ 100000
  • 1 ≤ s ≤ t ≤ n
  • 0 ≤ x ≤ 1000

入力例 1

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

出力例 1

4
8

入力例 2

4 3
1 1 4
0 1 4 1
1 1 4

出力例 1

0
4