Description

给出一个 $N\times N$ 的矩形，有两种操作：

• 改变矩形内每个元素的值，$1$ 变 $0$，$0$ 变 $1$。
• 查询某个位置的值。

Format

Input

输入的第一行是一个整数 $X$（$X \leq 10$），表示测试用例的数目。

接下来的 $X$个块是每个测试用例。

每个块的第一行包含两个数字 $N,T(2 \leq N \leq 1000,1 \leq T \leq 50000$），表示矩阵的大小和指令的数量。

接下来的 $T$ 行每行包含一个指令，指令格式为Q x y 或 C x1 y1 x2 y2，如题目描述。

Output

多组数据，对于每组数据，输出询问的结果，两组数据之间输出一个空格。

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