小葱 et 小绪 sont de bons amis. Depuis que 小葱 a obtenu 1UR2SR lors de onze tirages consécutifs, 小绪 trouve que 小葱 a une chance exceptionnelle. Il lui propose donc un problème pour la mettre à l’épreuve.

小绪 dessine d’abord $N$ points du plan, $P_1,P_2,\ldots,P_N$. Il les relie dans cet ordre, en traçant $(P_1,P_2),(P_2,P_3),\ldots,(P_{N-1},P_N)$, pour obtenir $N-1$ segments.

Ensuite, à chaque fois, 小绪 trace une droite du plan et demande à 小葱 combien de segments elle intersecte. En particulier, une intersection à une extrémité compte comme une intersection, tout comme le cas où la droite contient entièrement le segment.

Un tel problème ne pose naturellement aucune difficulté à 小葱 : sa chance lui permet de donner intuitivement la bonne réponse.

Pour déterminer à quel point 小葱 est chanceux, 小绪 augmente la difficulté :

En plus des requêtes, 小绪 insère de temps en temps un nouveau point $P$ entre $P_i$ et $P_{i+1}$, puis réattribue les indices à tous les points dans leur ordre. Les indices des points après $P_i$ augmentent ainsi d’une unité, et $P$ devient le nouveau point $P_{i+1}$. En particulier, $P$ peut aussi être inséré avant le premier point ou après le dernier.

小葱, toujours aussi chanceux, répond encore facilement. 小绪 augmente donc davantage la difficulté :

Après chaque insertion ou requête, 小绪 enregistre tous les segments obtenus, ce qui constitue une version historique. La version historique $T$ est celle obtenue après la $T$-ième opération.

Une insertion consiste désormais à insérer un point $P$ dans une version historique $T$ pour obtenir une nouvelle version historique. Après une requête, la nouvelle version historique est la version $T$ sur laquelle porte la requête.

Pour chaque requête, 小绪 donne maintenant une droite et une version historique $T$, et demande combien de segments de cette version la droite intersecte.

Malgré sa chance, 小葱 est démuni face à ce problème. Il vient donc vous trouver, vous qui participez au CTSC, pour vous demander de l’aider à le résoudre.

Entrée

Le fichier d’entrée est shallot.in.

La première ligne contient deux entiers $N,M,C$, indiquant le nombre initial de points, le nombre total d’opérations et si les données sont chiffrées. Si $C=1$, les données sont chiffrées : les valeurs $X_0,Y_0,X,Y$ des requêtes et $X,Y$ des insertions sont chiffrées. Vous devez leur appliquer un XOR avec $last\_ans$ pour obtenir les valeurs correctes, où $last\_ans$ est la réponse à la dernière requête ; initialement, $last\_ans=0$.

Les $N$ lignes suivantes contiennent chacune deux entiers. Ceux de la $i$-ième ligne sont l’abscisse et l’ordonnée de $P_i$.

Les $M$ lignes suivantes décrivent les $M$ opérations de 小绪. Le résultat après l’opération de la $i$-ième ligne, numérotée à partir de $1$, est la version historique $i$.

Chaque opération commence par une lettre indiquant son type.

Si cette lettre est H, il s’agit d’une requête. Elle est suivie de cinq entiers $T,X_0,Y_0,X,Y$ : dans la version historique $T$, 小绪 donne la droite passant par $(X_0,Y_0)$ et de vecteur directeur $(X,Y)$. 小葱 doit indiquer combien de segments elle intersecte.

Si cette lettre est Z, il s’agit d’une insertion. Elle est suivie de quatre nombres $T,i,X,Y$ : dans la version historique $T$, 小绪 insère après $P_i$ un point de coordonnées $(X,Y)$. En particulier, si $i=0$, le point est inséré avant $P_1$.

Sortie

Dans le fichier de sortie shallot.out, pour chaque requête, affichez sur une ligne un entier représentant la réponse correcte que 小葱 doit donner.

Exemples

Entrée 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

Sortie 1

1
0
1

Remarque

Pour la troisième requête, la droite contient entièrement le segment ; 小绪 considère que cela compte aussi comme une intersection.

Entrée 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

Sortie 2

0
2

Entrée et sortie 3

Consultez shallot/shallot.in et shallot/shallot.ans dans le répertoire des candidats.

Contraintes

Pour chaque requête, $T$ est garanti inférieur ou égal au nombre actuel d’opérations. Toutes les données d’entrée sont des entiers.

Il existe les quatre catégories particulières suivantes, deux à deux disjointes :

1. Pour $15\%$ des données, $1\le N,M\le1000$.
2. Pour $15\%$ des données, à la $i$-ième opération, $T=i-1$.
3. Pour $15\%$ des données, $C=0$ et il n’y a aucune opération de modification.
4. Pour $15\%$ des données, pour les opérations d’insertion, $Y=0$ (pour les données chiffrées, il s’agit de $Y$ après déchiffrement), c’est-à-dire que les droites données sont parallèles à l’axe des $x$.

Pour toutes ces données, $1\le N,M\le5\times10^4$ est également garanti.

Pour $100\%$ des données, $1\le N,M\le10^5$, toutes les coordonnées appartiennent à $[-10^8,10^8]$, la somme des réponses à toutes les requêtes d’un jeu de données ne dépasse pas $10^6$, et le nombre d’insertions ne dépasse pas $5\times10^4$. Notez que les segments peuvent se croiser.