Problem Description
She says that any Pavarotti among the nightingales will serenade his mate while she sits on her eggs.
She says that any excited database can answer the queries efficiently.
You are given the two dimensional database as a matrix A with n rows and n columns. In the beginning, A[i][j]=0 for all 1≤i,j≤n.
Then q operations or queries will be given in turn.
You should maintain the database for two type of operations:
⋅ 1 L R: for each element A[i][j] which satisfy L≤i+j≤R, increase the value to A[i][j]+1, where 2≤L≤R≤2n.
⋅ 2 L R: for each element A[i][j] which satisfy L≤i−j≤R, increase the value to A[i][j]+1, where 1−n≤L≤R≤n−1.
Meanwhile, you should answer the queries:
⋅ 3 x1 x2 y1 y2: count the value of elements A[i][j] which satisfy x1≤i≤x2 and y1≤j≤y2, where 1≤x1<x2≤n and 1≤y1<y2≤n.
Input
The input contains several test cases. The first line of the input is a single integer t which is the number of test cases. Then t test cases follow.
Each test case contains several lines. The first line contains the integer n and q.
The i-th line of the next q lines contains an operation ‘‘1 L R" or ‘‘2 L R", or a query ‘‘3 x1 x2 y1 y2".
The sum of n for all test cases would not be larger than 200000 and the sum of q would not be larger than 50000.
Output
For each test case, you should output answers to queries printed one per line.
Sample Input
2
6 6
2 0 1
3 1 4 3 5
3 2 5 2 3
1 5 7
3 1 4 3 5
3 2 5 2 3
6 26
2 -4 -1
3 1 4 2 5
3 3 6 4 6
1 4 7
3 2 5 2 3
3 1 4 2 5
2 -3 -1
3 1 4 3 5
1 3 5
1 2 3
3 2 5 2 3
3 1 4 2 5
3 3 6 4 6
2 0 4
3 1 4 3 5
3 1 4 2 5
1 9 11
2 1 2
3 2 5 2 3
3 3 6 4 6
2 -2 2
1 7 12
3 1 4 3 5
3 2 5 2 3
3 1 4 2 5
3 3 6 4 6
Sample Output
Case #1:
3
4
11
10
Case #2:
10
6
8
22
26
12
38
13
32
44
23
30
49
33
67
53
