Migrated from Lutece 209 Matrix

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

Given an $n\times n$ matrix $A$, whose elements are either $0$ or $1$. $A_{ij}$ means the number in the $i_{th}$ row and $j_{th}$ column. Initially we have $A_{ij} = 0$ ($1\leq i, j\leq n$).

We can change the matrix in the following way. Given a rectangle whose upper-left corner is $(x_1, y_1)$ and lower-right corner is $(x_2, y_2)$, we change all the elements in the rectangle by using not operation (if it is a $0$ then change it into $1$ otherwise change it into $0$). To maintain the information of the matrix, you are asked to write a program to receive and execute two kinds of instructions.

1. C x1 y1 x2 y2 ($1\leq x_1\leq x_2\leq n$, $1\leq y_1\leq y_2\leq n$) changes the matrix by using the rectangle whose upper-left corner is $(x_1, y_1)$ and lower-right corner is $(x_2, y_2)$.
2. Q x y ($1\leq x, y\leq n$) querys $A_{xy}$.

Input

The first line of the input is an integer $X$ ($X\leq 10$) representing the number of test cases. The following $X$ blocks each represents a test case.

The first line of each block contains two numbers $N$ and $T$ ($2\leq N\leq 1000$, $1\leq T\leq 50000$) representing the size of the matrix and the number of the instructions. The following $T$ lines each represents an instruction having the format Q x y or C x1 y1 x2 y2, which has been described above.

Output

For each querying output one line, which has an integer representing $A_{xy}$.

There is a blank line after every test case.

Samples

1
2 10
C 2 1 2 2
Q 2 2
C 2 1 2 1
Q 1 1
C 1 1 2 1
C 1 2 1 2
C 1 1 2 2
Q 1 1
C 1 1 2 1
Q 2 1

1
0
0
1

Note

The data used in this problem is unofficial data prepared by standy. So any mistake here does not imply mistake in the offcial judge data.

Resources

POJ Monthly,Lou Tiancheng