Excited Database

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\le i,j\le n$.
Then $q$ operations or queries will be given in turn.

You should maintain the database for two type of operations:
$\cdot$ $1~L~R$: for each element $A[i][j]$ which satisfy $L\le i+j\le R$, increase the value to $A[i][j]+1$, where $2\le L\le R\le 2n$.
$\cdot$ $2~L~R$: for each element $A[i][j]$ which satisfy $L\le i-j\le R$, increase the value to $A[i][j]+1$, where $1-n\le L\le R\le n-1$.
Meanwhile, you should answer the queries:
$\cdot$ $3~x_1~x_2~y_1~y_2$: count the value of elements $A[i][j]$ which satisfy $x_1\le i\le x_2$ and $y_1\le j\le y_2$, where $1\le x_1<x_2\le n$ and $1\le y_1<y_2\le n$.

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~x_1~x_2~y_1~y_2"$.

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$.

For each test case, you should output answers to queries printed one per line.

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

Case #1:
3
4
11
10
Case #2:
10
6
8
22
26
12
38
13
32
44
23
30
49
33
67
53

2015 ACM/ICPC Asia Regional Shenyang Online