描述

给定一个 $N \times N$ 矩阵 $A$，其元素为 $0$ 或 $1$。$A[i, j]$ 表示第 $i$ 行和第 $j$ 列中的数字。最初我们有 $A[i, j] = 0$ （$1 \leq i, j \leq N$）。

我们可以通过以下方式更改矩阵。给定一个左上角为 $（x1, y1）$ 且右下角为 $（x2, y2）$ 的矩形，我们使用 “not” 作更改矩形中的所有元素（如果它是 $'0'$ ，则将其更改为 $'1'$ ，否则将其更改为 $'0'$）。为了维护矩阵的信息，系统会要求您编写一个程序来接收和执行两种指令。

1. $C\ x1\ y1\ x2\ y2$ （$1 \leq x1 \leq x2 \leq n$，$1 \leq y1 \leq y2 \leq n$） 使用左上角为 $（x1, y1）$ 和右下角为 $（x2, y2）$ 的矩形更改矩阵。

2. $Q\ x\ y$ （$1 \leq x, y \leq n$） 查询 $A[x, y]$。

输入

输入的第一行是一个整数 $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$” 的指令，如上所述。

输出

对于每个查询，输出一行，该行具有一个表示 $A[x, y]$ 的整数。

每两个连续测试用例之间有一条空行。

输入数据 1

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

1
0
0
1

源于

$POJ 月刊，娄天成$