Description

You are given a integer sequence with length N. We name this sequence as A[];

I defined 2 kinds of operation on A[]. Here they are:

Add L R : for every L Q L R : query the value of A[L]+A[L+1]+...+A[R]

At first, the elements in A[] are all 0.

Input

several test case. first line ,2 integers N and O, means the length of the sequence and the commands. O lines follow. Each line represent an operation. specifically 1<=N,O<=100000 and 0<=L<=R<N

Output

for every case, output "Case #%d:" first. see the example for detail. then the query value.

Sample

Input

5 5
Add 0 4
Q 0 1
Q 0 0
Q 1 4
Q 3 4
5 3
Q 0 4
Add 0 3
Q 2 3

Output

Case #1:
1
0
10
7
Case #2:
0
5

Source: dd