Cong and Xu are good friends. Ever since Cong achieved a "1UR2SR" streak, Xu has felt that Cong is exceptionally lucky, so Xu decided to pose a problem to test Cong's luck.

Xu first draws $N$ points on a plane, denoted as $P_1, P_2, \dots, P_N$. Xu connects these $N$ points in sequence, i.e., connecting $(P_1, P_2), (P_2, P_3), \dots, (P_{N-1}, P_N)$, resulting in $N-1$ line segments.

Afterward, for each operation, Xu draws a line on the plane and asks Cong how many line segments this line intersects. Specifically, intersections at the endpoints of a line segment count as intersections, and a line completely covering a line segment also counts as an intersection.

This problem is naturally not difficult for Cong, who can provide the correct answer using his intuition.

Xu wants to test just how lucky Cong is, so he increases the difficulty: In addition to each query, Xu occasionally inserts a new point $P$ between $P_i$ and $P_{i+1}$, and then re-labels all points in order. That is, the indices of points after $P_i$ increase by one, and point $P$ becomes the new $P_{i+1}$. Specifically, a point $P$ can also be inserted before the first point or after the last point.

The incredibly lucky Cong is still able to provide the answer easily, so Xu further increases the difficulty: After each insertion or query, Xu records all the line segments after the operation, calling it a historical version. Historical version $T$ refers to the historical version obtained after the $T$-th operation.

The insertion operation is modified to be based on a certain historical version $T$, where a point $P$ is inserted to obtain a new historical version. After a query operation, the new historical version is the historical version $T$ that was queried.

Xu's query to Cong is modified to: for a historical version $T$, given a line, ask how many line segments this line intersects.

Although Cong is very lucky, he is at a loss when faced with such a problem. He has turned to you, who are participating in CTSC, to help him solve it.

Input

The input file is shallot.in.

The first line contains three integers $N, M, C$, representing the initial number of points, the total number of operations, and whether the data is encrypted. If $C = 1$, it means the data is encrypted. In this case, $X_0, Y_0, X, Y$ in query operations and $X, Y$ in insertion operations 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, where the $i$-th line represents the $x$ and $y$ coordinates of $P_i$.

The next $M$ lines represent Xu's $M$ operations. The result after the $i$-th operation (labeled starting from 1) is historical version $i$.

For each operation, there is first a letter representing the type of operation: If the letter is 'H', it represents a query operation: it is followed by five integers $T, X_0, Y_0, X, Y$, representing that in historical version $T$, Xu provides a line passing through $(X_0, Y_0)$ with direction $(X, Y)$. Cong needs to answer how many line segments it intersects.

If the letter is 'Z', it represents an insertion operation. It is followed by four integers $T, i, X, Y$, representing that Xu inserts a point with coordinates $(X, Y)$ after $P_i$ based on historical version $T$. Specifically, if $i = 0$, it means the point is inserted before $P_1$.

Output

For each query operation, output a single integer on a new line representing the correct answer Cong should provide.

Examples

Input 1

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

Output 1

1
0
1

Note 1

For the third query, the line completely covers the line segment, which Xu considers an intersection.

Input 2

2 3 0
0 0
2 2
Z 0 2 0 2
H 0 0 1 1 1
H 1 0 1 1 1

Output 2

0
2

Input 3

See shallot/shallot.in and shallot/shallot.ans in the contestant directory.

Constraints

It is guaranteed that for every query operation, $T$ is less than or equal to the number of current operations, and all input data are integers.

There are 4 types of special data, which are mutually exclusive: 1. For 15% of the data, $1 \le N, M \le 1000$; 2. For 15% of the data, for the $i$-th operation, $T = i - 1$; 3. For 15% of the data, $C = 0$ and there are no modification operations; 4. For 15% of the data, for insertion operations, $Y = 0$ (the encrypted data refers to the decrypted $Y$), meaning the given line is parallel to the $x$-axis.

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

For 100% of the data, $1 \le N, M \le 10^5$, all coordinates are in the range $[-10^8, 10^8]$, the sum of all query answers in each test case does not exceed $10^6$, and the number of insertion operations does not exceed $5 \times 10^4$. Note that these line segments may intersect each other.