P5843 [SCOI2012] Blinker’s Nightmare

One day, Blinker woke up and found that he had become a point in a two-dimensional world, and was marked with a strange value. This world consists of $N$ shapes whose boundaries do not intersect (and do not touch). The shapes include only circles and convex polygons. Each shape also has a weight. Each time Blinker enters or leaves a shape (passing while tangent does not count), Blinker’s marked value will be XORed with that weight. Now, we have recorded Blinker’s information for $M$ days in this world. Each day, one of two things may happen: the weight of some shape is changed to a certain value; or Blinker moves from one point to another point. We assume that Blinker’s marked value before his first departure is $0$, and we want to know his marked value after he arrives at the destination each time.

The first line contains $2$ numbers, $N$ and $M$, representing the number of shapes in this world and the number of recorded days. Next, there are $N$ lines, each describing a shape. If a line starts with the character `C`, it means the shape is a circle. It is followed by three real numbers $x$, $y$, $r$ and an integer $v$, representing the circle’s $x$ coordinate, $y$ coordinate, radius, and the value of this shape. If a line starts with the character `P`, it means the shape is a convex polygon. It is followed by an integer $L$, the number of vertices of the convex polygon, then $L$ pairs of real numbers $x_0$,$y_0$,$x_1$,$y_1$ $\cdots$, representing the coordinates of the $L$ points. The last number on this line is an integer $v$, representing the value of this shape. It is guaranteed that the points of the convex polygon are given in clockwise order. Next, there are $M$ lines, each describing one day’s record. If a line starts with the character `Q`, it means Blinker traveled on that day. It is followed by four real numbers $x_0,y_0,x_1,y_1$, representing the coordinates of the starting point and the destination. If a line starts with the character `C`, it means the value of a shape changed on that day. It is followed by two numbers $i$ and $v$, meaning that the value of the $i$-th shape in the input becomes $v$.

For each of Blinker’s travels, output his marked value after he arrives at the destination. Obviously, this value is independent of Blinker’s path.

**Sample Explanation**  The sample world looks like the figure above: On day 1, Binker’s initial marked value is $0$. He may go from $A$ to $B$ along a straight line, or he may go around the circle to reach $B$. His marked value finally remains $0$ in both cases. (Assuming he goes from $A$ to $B$ along the straight line, he crosses the boundary $4$ times, and Binker’s marked value changes as $1,3,1,0$.) On day 2, Binker’s initial marked value is $0$. He reaches point $C$ by some method that does not pass through any shape boundary (that is, Binker teleports or blinks), and then goes from $C$ to $D$ along some path. At this time, his marked value becomes $2$. On day 3, the circle’s weight becomes $1005$. On day 4, Binker’s initial marked value is $2$. He returns to $C$ again, and again goes from $C$ to $D$. At this time, his marked value becomes $0$ again. **Constraints** - For $30\%$ of the testdata, $1 \le M \le 10.00$, and the total number of polygon vertices plus the number of circles is at most $1000$. - For $100\%$ of the testdata, $1 \le N \le 10^5$, $1 \le M \le 10^5$, and the number of vertices in a single convex polygon is at most $34$. The shapes do not intersect each other, and Blinker’s starting point and destination are not on any shape boundary. Translated by ChatGPT 5