Blinker's XOR World

In this problem, Blinker wakes up one day to find himself reduced to a point in a 2D world. Moreover, he is marked with a strange value initially 0. This world contains N non‐intersecting (and non-tangent) shapes – each shape is either a circle or a convex polygon – and every shape has an associated weight.

Whenever Blinker crosses a shape’s boundary (i.e. when he enters or exits the shape, but not when the path is tangent to the boundary), his current mark is xor-ed with the weight of that shape. Note that if he crosses the same shape more than once during his journey, each crossing will xor the current value with the shape’s weight.

We are given information over M days. On each day, one of the following events may occur:

• An update event where the weight of a shape is changed.
• A query event where Blinker moves from one point to another. It is guaranteed that the starting and ending points will not lie exactly on any boundary.

Your task is to determine Blinker’s mark after each query event. Note that because the shapes do not intersect or touch, the total effect of moving from point A to point B is simply the xor of the weights of those shapes for which the containment status of A and B differ.

All formulas are given in LaTeX format. For example, the number of shapes is denoted as $N$, and the number of days as $M$. The initial mark is $0$, and for every shape that the point changes its containment status, Blinker’s mark is updated by xoring with its weight.

inputFormat

The input begins with a line containing two integers $N$ and $M$, denoting the number of shapes and the number of events respectively.

Then $N$ lines follow, each describing a shape. Each shape is either a circle or a convex polygon:

• If the shape is a circle, the line will be in the format: CIRCLE cx cy r w, where (cx, cy) is the center, r is the radius, and w is its weight.
• If the shape is a convex polygon, the line begins with: POLYGON k (where k is the number of vertices), followed by k pairs of integers representing the vertices in order, and finally an integer w representing its weight.

After the shapes, there are $M$ lines describing the events. Each event is either:

• A query event of the form: Q ax ay bx by where $(ax,ay)$ is the starting point and $(bx,by)$ is the destination.
• An update event of the form: U id new_w where id indicates the 1-indexed shape to be updated and new_w is its new weight.

It is guaranteed that the starting and ending points of every query do not lie exactly on any shape boundary.

outputFormat

For each query event, output a single integer on a new line representing Blinker’s mark after completing that move.

sample

2 3
CIRCLE 0 0 5 10
POLYGON 4 -1 -1 -1 1 1 1 1 -1 5
Q -10 0 10 0
U 1 7
Q -4 0 0 0

0
5

</p>