Description

Xiao Cong and Xiao Xu are good friends. Since Xiao Cong pulled 1 UR and 2 SR in an 11-roll, Xiao Xu felt that Xiao Cong is very lucky, so he gave him a problem to test his luck.

Xiao Xu first drew $N$ points on the plane, denoted as $P_1, P_2, ..., P_N$.

He connected these $N$ points in order, that is, he connected $(P_1, P_2), (P_2, P_3), ..., (P_{N-1}, P_N)$ to obtain $N-1$ line segments.

Then, each time Xiao Xu drew a line on the plane and asked how many segments this line intersects. In particular, intersection at a segment endpoint counts as intersecting, and if the line completely covers a segment, it also counts as intersecting. Such a question is obviously easy for Xiao Cong; he can give the correct answer by intuition alone thanks to his luck.

To further test Xiao Cong’s luck, Xiao Xu increased the difficulty: in addition to each query, he would occasionally insert a new point $P$ between $P_i$ and $P_{i+1}$, then relabel all points in order; that is, the indices of points after $P_i$ increase by one, and point $P$ becomes the new point $P_{i+1}$.

In particular, point $P$ can also be inserted before the first point or after the last point.

Xiao Cong is still able to answer easily, so Xiao Xu raised the difficulty again:

After each insertion or query, Xiao Xu recorded all the resulting segments and regarded them as a historical version. Historical version $T$ denotes the state after the $T$-th operation.

The insertion operation was changed to: based on a certain historical version $T$, insert a point $P$ to obtain a new historical version.

The query was changed to: for a historical version $T$, given a line, ask how many segments this line will intersect.

Although Xiao Cong has great luck, he is helpless in the face of such a problem. He turns to you, a participant of CTSC, to help him solve it.

Input Format

The first line contains three integers $N, M, C$, denoting the initial number of points, the total number of operations, and whether the data are encrypted.

If $C=1$, it means the data are encrypted. In each query operation, $X_0, Y_0, X, Y$ and in each insertion operation, $X, Y$ are encrypted; you need to XOR them with last_ans to obtain the correct data, where last_ans is the answer to the previous query. Initially, last_ans $= 0$.

The next $N$ lines each contain two integers; on the $i$-th line, the two integers denote the coordinates of $P_i$.

The next $M$ lines describe Xiao Xu’s $M$ operations. The result after the $i$-th operation (1-indexed) is historical version $i$.

For each operation, there is first a letter indicating the operation type.

• If the letter is 'H', this is a query operation. Then five integers $T, X_0, Y_0, X, Y$ follow, meaning that under historical version $T$, Xiao Xu gives a line passing through $(X_0, Y_0)$ with direction $(X, Y)$, and Xiao Cong must answer how many segments it intersects.
• If the letter is 'Z', this is an insertion operation. Then four numbers $T, i, X, Y$ follow, meaning that based on historical version $T$, Xiao Xu inserts a point with coordinates $(X, Y)$ after $P_i$. In particular, if $i=0$, it means the point is inserted before $P_1$.

Output Format

For each query operation, output one line with one integer representing the correct answer Xiao Cong should give.

2 3 0
0 0
1 1
H 0 1 0 -1 1
H 1 0 1 1 1
H 2 -1 -1 1 1

1
0
1

Hint

Sample explanation 1:

For the third query, the line completely covers a segment, and Xiao Xu considers this as intersecting as well.

Constraints and notes:

All operations satisfy that in each query operation, $T$ is less than or equal to the current number of operations, and all input numbers are integers.

There are the following 4 special testdata groups, which are pairwise disjoint:

1. For 10% of the testdata, $1 \le N, M \le 1000$.
2. For 15% of the testdata, for the $i$-th operation, $T = i - 1$.
3. For 15% of the testdata, $C=0$ and there are no modification operations.
4. For 15% of the testdata, for query operations, $Y=0$ (this refers to the decrypted data), i.e., the given line is parallel to the $x$-axis.

The above testdata also guarantee $1 \le N, M \le 5 \times 10^4$.

For 100% of the testdata, $1 \le N, M \le 10^5$, all coordinates are within $[-10^8, 10^8]$, and within each dataset the sum of answers over all queries does not exceed $10^6$. The number of insertion operations does not exceed $5 \times 10^4$. Note that these segments may intersect each other.

Translated by ChatGPT 5