Description

Give you one sequence and some command and you solve it! There are 2 kinds of command:

     1, a L R val: this means you should add val to all elements in [L,R]

     2, b L R: this means you should tell me the sum of all elements in [L,R]

warning: sequence index counts from 1.

Input

Multi testcase. First line contain 2 integer n,m (n,m<=100000)which means the length of the sequence and the number of command second line contain n initial values(<=1000) of the sequence. Then m lines, each line will be a command. ( the added value will also <=1000)

Output

First output the case number(see the sample) then the sums of all query.

Sample

Input

4 4
1 2 3 4
a 1 1 2
b 1 3
a 2 3 2
b 2 4
4 4
1 2 3 4
a 1 1 2
b 1 3
a 2 3 2
b 2 4

Output

case #1:
8
13
case #2:
8
13

Source: dd