Migrated from Lutece 47 Blinker的噩梦

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

一天Blinker醒来，发现自己成为了一个二维世界的点，而且被标记上了一个奇怪的值。

这个世界是由$N$个边界互不相交（且不相切）的图形组成，这里图形仅包括圆和凸多边形。每个图形还有一个权值。每次Blinker走进或走出某个图形时（相切时经过不算），Blinker的标记值就会被异或上那个值。

现在，我们记录了Blinker在这个世界的$M$天的信息。每天可能发生两种事情，一种是某个图形的权值更改为某个值；另一种是Blinker从某个点走到另一个点。

我们假设Blinker首次出发前的标记值为$0$，我们希望知道他每次到达目的地后的标记值。

Input

输入的第一行包含$2$个数，$N$和$M$，分别表示这个世界的图形数和记录的天数。

接下来有$N$行，每行表示一个图形。

• 如果一行以字符C开头，表示这个图形是一个圆，后面紧跟着三个实数$x$,$y$,$r$和一个整数$v$，分别表示圆的$x$坐标，$y$坐标和圆的半径以及该图形对应的值。
• 如果一行以字符P开头，表示这个图形是凸多边形，后面紧跟着一个整数$L$，表示凸多边形的点数，然后后面有$L$对实数$x_0$,$y_0$,$x_1$,$y_1\cdots x_{L-1}$, $y_{L-1}$，表示$L$个点的坐标，这一行最后一个数是一个整数$v$，表示这个图形对应的值，保证凸多边形上的点按照顺时针给出。

接下来有$M$行，每行表示一天的记录信息。

• 如果一行以字符$Q$开头，表示这一天Blinker出行了，接下来有$x_0$,$y_0$,$x_1$,$y_1$四个实数，分别表示出发点的坐标和目的地的坐标。
• 如果一行以字符$C$开头，表示这一天某个图形的值改变了，接下来有两个$i$和$v$，表示输入中第$i$个出现的图形的值变成$v$。

$1\leq N\leq 100000$,$1 \leq M \leq 100000$。

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

Output

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

Samples

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

0 
2 
0

Note

样例的世界形如上图：

• 第一天Blinker的初始标记值为$0$，从可能从$A$沿直线走到$B$，或者他绕过圆走到$B$，他的标记值最终都保持不变为$0$（假如沿直线从$A$走到$B$，共穿过$4$次边界，Blinker的标记值变化过程为 $1\rightarrow 3\rightarrow 1\rightarrow 0$）。
• 第二天Blinker的初始标记值为$0$，他通过某种不经过图形边界的方法到达了$C$点（即blink，瞬间移动或闪烁），然后从$C$沿某种路径走到$D$，这时他的标记值变为$2$ 。
• 第三天圆的权值变为$1005$。
• 第四天Blinker的初始标记值为$2$，他再次回到$C$，并再次从$C$走到$D$，这时他的标记值又变回$0$。

Resources

SCOI2012