小葱 und 小绪 sind gute Freunde. Seit 小葱 bei einem elffachen Ziehen 1UR2SR erhalten hat, hält 小绪 ihn für besonders vom Glück begünstigt. Deshalb stellt 小绪 ihm eine Aufgabe, um sein Glück zu testen.

Zunächst zeichnet 小绪 $N$ Punkte $P_1,P_2,\ldots,P_N$ in die Ebene. Er verbindet diese $N$ Punkte der Reihe nach, also $(P_1,P_2),(P_2,P_3),\ldots,(P_{N-1},P_N)$, und erhält $N-1$ Strecken.

Danach zeichnet 小绪 jedes Mal eine Gerade in die Ebene und fragt 小葱, wie viele Strecken diese Gerade schneidet. Insbesondere zählt eine Berührung an einem Endpunkt als Schnitt, und auch wenn die Gerade die gesamte Strecke enthält, zählt dies als Schnitt.

Eine solche Frage kann 小葱 natürlich nicht aufhalten: Dank seines Glücks braucht er nur seiner Intuition zu folgen, um die richtige Antwort zu geben.

小绪 möchte herausfinden, wie groß das Glück von 小葱 wirklich ist, und erhöht deshalb die Schwierigkeit:

Zusätzlich zu den Anfragen fügt 小绪 gelegentlich einen neuen Punkt $P$ zwischen $P_i$ und $P_{i+1}$ ein und nummeriert dann alle Punkte in ihrer Reihenfolge neu. Die Indizes der Punkte nach $P_i$ werden also jeweils erhöht, und $P$ wird zum neuen Punkt $P_{i+1}$. Insbesondere kann $P$ auch vor dem ersten oder nach dem letzten Punkt eingefügt werden.

小葱 kann dank seines außerordentlichen Glücks weiterhin mühelos antworten. Deshalb erhöht 小绪 die Schwierigkeit noch weiter:

Nach jeder Einfügung oder Anfrage hält 小绪 alle Strecken des entstandenen Zustands fest und nennt dies eine historische Version. Die historische Version $T$ ist die nach der $T$-ten Operation entstandene Version.

Die Einfügeoperation wird so geändert, dass auf Grundlage einer historischen Version $T$ ein Punkt $P$ eingefügt und eine neue historische Version erzeugt wird. Nach einer Anfrage ist die neue historische Version gleich der abgefragten historischen Version $T$.

Bei einer Anfrage gibt 小绪 nun für eine historische Version $T$ eine Gerade vor und fragt, wie viele Strecken diese Gerade schneidet.

Obwohl 小葱 großes Glück hat, weiß er bei einer solchen Aufgabe nicht mehr weiter. Er wendet sich an dich, der du an der CTSC teilnimmst, und bittet dich, ihm bei der Lösung zu helfen.

Eingabe

Die erste Zeile enthält die Ganzzahlen $N,M,C$: die anfängliche Anzahl der Punkte, die Gesamtzahl der Operationen und die Angabe, ob die Daten verschlüsselt sind. Falls $C=1$, sind die Daten verschlüsselt: $X_0,Y_0,X,Y$ jeder Anfrage sowie $X,Y$ jeder Einfügung sind verschlüsselte Werte. Du musst sie mit $last\_ans$ bitweise XOR-verknüpfen, um die richtigen Werte zu erhalten. Dabei ist $last\_ans$ die Antwort auf die letzte Anfrage; anfangs gilt $last\_ans=0$.

Die nächsten $N$ Zeilen enthalten jeweils zwei Ganzzahlen. In der $i$-ten Zeile sind dies die horizontale und die vertikale Koordinate von $P_i$.

Die nächsten $M$ Zeilen beschreiben die $M$ Operationen von 小绪. Der Zustand nach der Operation in der $i$-ten Zeile (ab $1$ gezählt) ist die historische Version $i$.

Jede Operation beginnt mit einem Buchstaben, der ihren Typ angibt.

Ist dieser Buchstabe H, handelt es sich um eine Anfrage. Es folgen fünf Ganzzahlen $T,X_0,Y_0,X,Y$. Für die historische Version $T$ gibt 小绪 eine Gerade durch $(X_0,Y_0)$ mit Richtung $(X,Y)$ vor. 小葱 soll angeben, wie viele Strecken sie schneidet.

Ist dieser Buchstabe Z, handelt es sich um eine Einfügung. Es folgen vier Zahlen $T,i,X,Y$. 小绪 fügt auf Grundlage der historischen Version $T$ hinter $P_i$ einen Punkt mit den Koordinaten $(X,Y)$ ein. Insbesondere bedeutet $i=0$, dass der Punkt vor $P_1$ eingefügt wird.

Ausgabe

Gib für jede Anfrage eine Zeile mit einer Ganzzahl aus: der richtigen Antwort, die 小葱 geben sollte.

Beispiele

Eingabe 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

Ausgabe 1

1
0
1

Hinweis

Bei der dritten Anfrage enthält die Gerade die gesamte Strecke. 小绪 betrachtet auch dies als Schnitt.

Eingabe 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

Ausgabe 2

0
2

Ein- und Ausgabe 3

Siehe shallot/shallot.in und shallot/shallot.ans im Teilnehmerverzeichnis.

Beschränkungen

Es ist garantiert, dass $T$ bei jeder Anfrage höchstens die aktuelle Anzahl der Operationen ist. Alle Eingabedaten sind ganzzahlig.

Es gibt die folgenden vier Arten spezieller Daten, die paarweise disjunkt sind:

1. Für 15 % der Daten gilt $1\le N,M\le1000$;
2. Für 15 % der Daten gilt bei der $i$-ten Operation $T=i-1$;
3. Für 15 % der Daten gilt $C=0$, und es gibt keine Änderungsoperationen;
4. Für 15 % der Daten gilt bei Einfügeoperationen $Y=0$ (bei verschlüsselten Daten ist das entschlüsselte $Y$ gemeint), das heißt, die vorgegebenen Geraden sind parallel zur $x$-Achse.

Für die obigen Daten gilt außerdem $1\le N,M\le5\times10^4$.

Für 100 % der Daten gilt $1\le N,M\le10^5$. Alle Koordinaten liegen in $[-10^8,10^8]$. Die Summe der Antworten auf alle Anfragen eines Datensatzes ist höchstens $10^6$, und es gibt höchstens $5\times10^4$ Einfügeoperationen. Beachte, dass sich die Strecken gegenseitig schneiden können.