Problem Description

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.

Input Format

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$.

Output Format

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.

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

Hint

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