Comet OJ

C1384 [SCOI2012]Blinker的噩梦

内存限制：256 MB 时间限制：1000 ms

题目描述

一天 Blinker 醒来，发现自己成为了一个二维世界的点，而且被标记上了一个奇怪的值。这个世界是由 $N$ 个边界互不相交（且不相切）的图形组成，这里图形仅包括圆和凸多边形。每个图形还有一个权值。每次 Blinker 走进或走出某个图形时（相切时经过不算），Blinker 的标记值就会被异或上那个值。现在，我们记录了 Blinker 在这个世界的M天的信息。每天可能发生两种事情，一种是某个图形的权值更改为某个值；另一种是 Blinker 从某个点走到另一个点。我们假设 Blinker 首次出发前的标记值为 $0$，我们希望知道他每次到达目的地后的标记值。

输入格式

输入的第一行包含 $2$ 个数，$N$ 和 $M$，分别表示这个世界的图形数和记录的天数。接下来有 $N$ 行，每行表示一个图形。如果一行以字符 $C$ 开头，表示这个图形是一个圆，后面紧跟着三个实数 $x, y, r$ 和一个整数 $v$，分别表示圆的 $x$ 坐标，$y$ 坐标和圆的半径以及该图形对应的值。如果一行以字符 $P$ 开头，表示这个图形是凸多边形，后面紧跟着一个整数 $L$，表示凸多边形的点数，然后后面有 $L$ 对实数 $x_0,y_0,x_1,y_1…$，表示 $L$ 个点的坐标，这一行最后一个数是一个整数 $v$，表示这个图形对应的值，保证凸多边形上的点按照顺时针给出。接下来有 $M$ 行，每行表示一天的记录信息。

如果一行以字符 $Q$ 开头，表示这一天 Blinker 出行了，接下来有 $x_0,y_0,x_1,y_1$ 四个实数，分别表示出发点的坐标和目的地的坐标。

如果一行以字符 $C$ 开头，表示这一天某个图形的值改变了，接下来有两个 $i$ 和 $v$，表示输入中第 $i$ 个出现的图形的值变成 $v$。

输出

对于 Blinker 的每个出行输出他到达目的地后的标记值，很显然这个值与 Blinker 的路径无关。

样例

样例输入 1

2 4
C 0 0 2 1
P 4 -1 -1 -1 1 1 1 1 -1 2
Q -2 -2 2 2
Q -1.5 0 0.0 0.0
C 1 1005
Q -1.5 0 0.0 0.0

样例输出 1

0
2
0

提示

对于 $30\%$ 的数据，保证：

$1 \le M \le 10.0$，凸多边形的点数加上圆的个数小于等于 $1000$。

剩余数据中，保证：

存在一组无图形值变动的数据；

存在一组无凸多边形的数据；

对于 $100%$ 的数据，保证：

$1 \le N \le 100000，1 \le M \le 100000$，单个凸多边形的点数小于等于 $34$。图形互不相交，且 Blinker 的出发点和目的地不在图形的边界。