BGC TRUST IUPC 2012

Problem J

Bulky process of bulk reduction

Do you know how bulky a process of bulk reduction can be? Let me tell you a story. Then maybe you will understand that for a fat person, it is too tough to lose weight.

Motu City is very famous for its inhabitants. None of them weighs less than 200kg. They want to lose their weights but they don’t know how to do it. One day one of the inhabitants Mr. A1 woke up and thought- “Why don’t I use my bicycle to lose weight!” He immediately went out with his cycle and rode it for 1 mile. Then he saw his friend Mr. A2 there, and proposed him to be his companion. Then they together rode for another mile and met Mr. A3 and in this way they went for 25 miles ride. So A1 rode for 25 miles, A2 for 24 miles, A3 for 23 miles, A4 for 22 miles and A25 for 1 mile. Given how much calorie will one lose riding a particular mile of the city, you have to tell me how much calorie they lose together. Note that, because of rainy or sunny weather calorie losing will vary from day to day. So you have to keep track of all the information to answer the queries properly.

Input

First line of the input file contains a positive integer denoting the number of test cases, T (<= 10).

First line of each test case contains two positive integers N (<= 100,000) length of the city and Q (<=100,000) number of operations. Initially for each mile one loses 100 calorie.

Hence follows Q operations. Operations can be of two kinds:

· change i j u : Update calorie requirement of ith mile, (i+1)st mile, (i+2)nd mile … jth mile by u. That is this portion of the road will cost u calorie more than previous. Note that, u can be negative number so it may cost less too. (1 <= i <= j <= n, -1000 <= u <= 1000). After the operation some mile may cost less than zero that is cycling that mile one will gain calorie instead of losing!

· query i j : How much calorie will be lost in total by (j-i+1) cyclists? For example, “query 2 4” means, one cyclist will travel 2nd mile of the city, then two cyclists will travel 3rd mile and three cyclists will travel 4th mile. So in total they will lose Calorie(2) + 2*Calorie(3) + 3*Calorie(4) calories, where Calorie(x) = the amount of calorie one loses riding cycle at xth mile of the city. Answer to the queries should be printed in separate lines.

Please go through the sample input output for the details.

Output

For each test case print “Case x:” first, where x is the test case number. Then in separate lines output the answer to the second kind of operations in the same order as it appeared in input. Do not put blank line between test cases.

Sample Input	Output for Sample Input
1 5 5 query 1 3 change 2 3 4 query 1 3 query 2 3 query 3 3	Case 1: 600 620 312 104

Problemsetter: Md. Mahbubul Hasan

Special Thanks: Abu Obaida