小葱 y 小绪 son buenos amigos. Desde que 小葱 consiguió 1UR2SR en una tirada de 11 cartas, 小绪 piensa que tiene muchísima suerte. Por ello, le plantea un problema para poner a prueba su suerte.

Primero, 小绪 dibuja $N$ puntos en el plano, llamados $P_1,P_2,\ldots,P_N$. Los conecta en orden, es decir, conecta $(P_1,P_2),(P_2,P_3),\ldots,(P_{N-1},P_N)$, obteniendo $N-1$ segmentos.

Después, cada vez dibuja una recta en el plano y pregunta a 小葱 cuántos segmentos corta esa recta. En particular, una intersección en un extremo del segmento cuenta como intersección, y también cuenta el caso en que la recta contiene por completo el segmento.

Naturalmente, este problema no supone ninguna dificultad para 小葱: gracias a su suerte, puede dar la respuesta correcta simplemente siguiendo su intuición.

小绪 quiere averiguar hasta qué punto llega la suerte de 小葱, así que aumenta la dificultad:

Además de hacer consultas, de vez en cuando inserta un nuevo punto $P$ entre $P_i$ y $P_{i+1}$ y vuelve a numerar todos los puntos en orden. Es decir, los índices de los puntos posteriores a $P_i$ aumentan en uno, y $P$ se convierte en el nuevo punto $P_{i+1}$. En particular, también se puede insertar $P$ antes del primer punto o después del último.

小葱, que tiene una suerte extraordinaria, sigue respondiendo con facilidad, por lo que 小绪 vuelve a aumentar la dificultad:

Después de cada inserción o consulta, 小绪 guarda todos los segmentos resultantes como una versión histórica. La versión histórica $T$ es la obtenida después de la operación número $T$.

La operación de insertar un punto cambia: ahora se parte de alguna versión histórica $T$, se inserta un punto $P$ y se obtiene una nueva versión histórica. Tras una consulta, la nueva versión histórica es la versión histórica $T$ consultada.

Las consultas de 小绪 pasan a consistir en dar una recta y una versión histórica $T$, y preguntar cuántos segmentos de esa versión corta la recta.

Aunque 小葱 tiene mucha suerte, ya no sabe cómo enfrentarse a este problema. Por eso acude a ti, que has venido a participar en CTSC, y te pide ayuda para resolverlo.

Entrada

El archivo de entrada es shallot.in.

La primera línea contiene los enteros $N,M,C$, que indican el número inicial de puntos, el número total de operaciones y si los datos están cifrados. Si $C=1$, los datos están cifrados: $X_0,Y_0,X,Y$ en cada consulta y $X,Y$ en cada inserción están cifrados. Debes aplicarles XOR con $\mathit{last\_ans}$ para obtener los datos correctos, donde $\mathit{last\_ans}$ es la respuesta a la consulta anterior y, al principio, $\mathit{last\_ans}=0$.

Las siguientes $N$ líneas contienen dos enteros cada una. Los dos números de la línea $i$ son las coordenadas horizontal y vertical de $P_i$.

Las siguientes $M$ líneas describen las $M$ operaciones de 小绪. El resultado después de la operación de la línea $i$, numerada a partir de $1$, es la versión histórica $i$.

Cada operación comienza con una letra que indica su tipo.

Si la letra es «H», se trata de una consulta. Le siguen cinco enteros $T,X_0,Y_0,X,Y$: en la versión histórica $T$, 小绪 da una recta que pasa por $(X_0,Y_0)$ y tiene dirección $(X,Y)$. 小葱 debe responder cuántos segmentos corta.

Si la letra es «Z», se trata de una inserción. Le siguen cuatro números $T,i,X,Y$: partiendo de la versión histórica $T$, 小绪 inserta un punto de coordenadas $(X,Y)$ después de $P_i$. En particular, si $i=0$, el punto se inserta antes de $P_1$.

Salida

En el archivo shallot.out, para cada consulta, escribe una línea con un entero: la respuesta correcta que debe dar 小葱.

Ejemplos

Entrada 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

Salida 1

1
0
1

Nota

En la tercera consulta, la recta contiene por completo el segmento. 小绪 considera que este caso también cuenta como intersección.

Entrada 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

Salida 2

0
2

Ejemplo 3

Consulta shallot/shallot.in y shallot/shallot.ans en el directorio de los participantes.

Restricciones

Se garantiza que el valor $T$ de cada consulta no supera el número actual de operaciones. Todos los datos de entrada son enteros.

Hay los siguientes cuatro grupos de datos especiales, disjuntos dos a dos:

1. Para el $15\%$ de los datos, se garantiza $1\le N,M\le1000$.
2. Para el $15\%$ de los datos, se garantiza que en la operación $i$ se cumple $T=i-1$.
3. Para el $15\%$ de los datos, se garantiza $C=0$ y no hay operaciones de modificación.
4. Para el $15\%$ de los datos, en las inserciones se garantiza $Y=0$; en datos cifrados se trata del valor de $Y$ después de descifrarlo. Es decir, las rectas dadas son paralelas al eje $x$.

En los datos anteriores también se garantiza $1\le N,M\le5\times10^4$.

Para el $100\%$ de los datos, se garantiza $1\le N,M\le10^5$, todas las coordenadas están en $[-10^8,10^8]$, la suma de las respuestas de todas las consultas de cada conjunto de datos no supera $10^6$ y el número de inserciones no supera $5\times10^4$. Ten en cuenta que los segmentos pueden cortarse entre sí.