The QianJin Teaching Building

Time Limit: 10000 ms Memory Limit: 65536 KiB

Problem Description

  When you try to solve this problem, I think there is only at most one month left for our footmen(FM2008)staying at our Alma Mater. I think these four years is the happiest and most important time in all my life. I learned to study and met so many sincere friends in our school especially in our ACM team. It is too simple that just say “THX” to express my sincere thank, but I must say “Thank you “for you all. I send my particular thank to Doctor Wu for you help and care to me and the whole ACM team. Huicpc3-15, my teammate at footmen, is the most important bosom friend in my life. We are classmates in the Mathematics and Applied Mathematics 05-1.We took part in the Mathematical Modeling Contest together, and participated in ACM Contest as teammates. We surmounted the difficulties, suffered the defeat and enjoyed the glad of success together. Together we tasted the joys and sorrows of life. But it is always true that pleasant hours fly past, and it is time to part. I can’t help to run back to the time when we studied in the Qianjing teaching building for our examinations and learned the knowledge about algorithm and programming.
As we all know the numbers of seats in the classrooms are not always same. When the examination week comes, there will be these cases that it is too large for a class but there is no small classroom which is enough for them. So many seats are left unused but we can’t use. So every time we went to the Qianjin teaching building to study, it is a hard time to find a free classroom. I really like if the seats in one classroom can be moved to another one, although it is impossible in our school now. In this case, we can move the superfluous seats in one classroom to another one. How wonderful the idea is! To make it easier, we just consider the classrooms in one floor. Suppose one floor is a rectangle and is divided into grids, and every grid is a classroom. And it is true that the rooms on each row or column will not exceed 1000(This is enough for all the students in our school!).Every time you can move one seat from or to one room. 

Input

  In the first line of the input, there is an integer T (1 ≤ T ≤ 10), corresponding to the number of test cases. For each test case, the first line is an integer Q (1 < Q < 100,000), corresponding to the queries of the case, following by Q queries. There are 4 kinds of queries: A x y m means put m seats to the room on the position (x, y). D x y m means move away m seats from the room on the position (x, y), if there are less than m seats in that room, move away all of them. M x1 y1 x2 y2 m means move m seats from the room on (x1, y1) to the room on (x2,y2), if less than m seats at that room on (x1, y1), move away all of them. S x1 y1 x2 y2 query the total seats in the rooms contained by the rectangle used (x1, y1), (x2, y2) as the two points. You can suppose that there is one seats in each room at first and 0 ≤ x1, y1, x2, y2, x, y < 1000,0 ≤ m < 100. 

Output

  For each case, output "Case X:" where X is the index of the test case.
For each "S" query, just print out the total number of seats in the room on that area.

Sample Input

2
3
S 1 1 2 2
A 1 1 3
S 1 1 1 1
4
S 1 1 1 1
D 1 1 2
S 1 1 1 2
M 1 1 2 2 100

Sample Output

Case 1:
4
4
Case 2:
1
1

Hint

 

Source

2009湖南大学校赛