#P5604. Poj2155 Matrix二维线段树

    ID: 4605 传统题 1000ms 512MiB 尝试: 2 已通过: 1 难度: 5 上传者: 标签>CF1800普及+/提高-二维线段树异或抵消

Poj2155 Matrix二维线段树

Description

给出一个 N×NN\times N 的矩形,有两种操作:

  • 改变矩形内每个元素的值,11 变 00,00 变 11。
  • 查询某个位置的值。

Format

Input

输入的第一行是一个整数 XX(X≤10X \leq 10),表示测试用例的数目。

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

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

接下来的 TT 行每行包含一个指令,指令格式为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