小葱 i 小绪 są dobrymi przyjaciółmi. Odkąd 小葱 w losowaniu jedenastu kart zdobył 1UR2SR, 小绪 uważa, że 小葱 ma wyjątkowe szczęście. Postanowił więc dać mu zadanie, aby to szczęście sprawdzić.

Najpierw 小绪 narysował na płaszczyźnie $N$ punktów: $P_1,P_2,\ldots,P_N$. Połączył je kolejno, tworząc odcinki $(P_1,P_2),(P_2,P_3),\ldots,(P_{N-1},P_N)$, czyli łącznie $N-1$ odcinków.

Następnie za każdym razem rysuje na płaszczyźnie prostą i pyta 小葱, ile odcinków ona przecina. W szczególności przecięcie w końcu odcinka również się liczy, podobnie jak sytuacja, w której cała długość odcinka leży na prostej.

Takie pytania oczywiście nie stanowią dla 小葱 problemu: dzięki swojemu szczęściu potrafi intuicyjnie podać poprawną odpowiedź.

小绪 chce sprawdzić, jak wielkie jest szczęście 小葱, więc utrudnia zadanie:

Oprócz zadawania pytań od czasu do czasu wstawia nowy punkt $P$ między $P_i$ a $P_{i+1}$, po czym ponownie numeruje wszystkie punkty w kolejności. Indeksy punktów za $P_i$ zwiększają się o jeden, a punkt $P$ staje się nowym $P_{i+1}$. W szczególności punkt $P$ można wstawić także przed pierwszym lub za ostatnim punktem.

小葱, obdarzony niezwykłym szczęściem, nadal odpowiada bez trudu, więc 小绪 jeszcze bardziej zwiększa poziom trudności:

Po każdym wstawieniu lub zapytaniu 小绪 zapisuje wszystkie odcinki po wykonaniu operacji, nazywając ten zapis wersją historyczną. Wersja historyczna $T$ oznacza wersję uzyskaną po $T$-tej operacji.

Teraz wstawienie nowego punktu polega na wstawieniu punktu $P$ do wybranej wersji historycznej $T$ i utworzeniu nowej wersji historycznej. Po zapytaniu nowa wersja historyczna jest taka sama jak wersja $T$, której dotyczyło zapytanie.

Zapytania 小绪 do 小葱 mają teraz postać: dla wersji historycznej $T$ podana jest prosta i należy określić, ile odcinków ta prosta przecina.

Choć 小葱 ma wielkie szczęście, wobec takiego zadania jest bezradny. Zwrócił się więc do ciebie, uczestnika CTSC, z prośbą o pomoc.

Wejście

Plik wejściowy to shallot.in.

Pierwszy wiersz zawiera dwie liczby całkowite $N,M,C$, oznaczające początkową liczbę punktów, łączną liczbę operacji oraz to, czy dane są zaszyfrowane. Jeśli $C=1$, dane są zaszyfrowane: wartości $X_0,Y_0,X,Y$ w każdym zapytaniu oraz $X,Y$ w każdym wstawieniu należy poddać operacji XOR z $\mathit{last\_ans}$, aby otrzymać właściwe dane. $\mathit{last\_ans}$ jest odpowiedzią na poprzednie zapytanie, a początkowo $\mathit{last\_ans}=0$.

Następne $N$ wierszy zawiera po dwie liczby całkowite. W wierszu $i$ podane są współrzędne pozioma i pionowa punktu $P_i$.

Kolejne $M$ wierszy opisuje $M$ operacji 小绪. Wynik wykonania operacji z wiersza $i$ (numeracja od $1$) jest wersją historyczną $i$.

Opis każdej operacji zaczyna się od litery określającej jej rodzaj.

Litera H oznacza zapytanie. Dalej podanych jest pięć liczb całkowitych $T,X_0,Y_0,X,Y$. Dla wersji historycznej $T$ 小绪 podaje prostą przechodzącą przez $(X_0,Y_0)$ o kierunku $(X,Y)$, a 小葱 ma odpowiedzieć, ile odcinków ta prosta przecina.

Litera Z oznacza wstawienie. Dalej podane są cztery liczby $T,i,X,Y$. Na podstawie wersji historycznej $T$ 小绪 wstawia za punktem $P_i$ nowy punkt o współrzędnych $(X,Y)$. W szczególności, jeśli $i=0$, punkt zostaje wstawiony przed $P_1$.

Wyjście

Dla każdego zapytania wypisz do pliku shallot.out jeden wiersz zawierający jedną liczbę całkowitą: poprawną odpowiedź, której powinien udzielić 小葱.

Przykład

Wejście 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

Wyjście 1

1
0
1

Uwagi

W trzecim zapytaniu cały odcinek leży na prostej. 小绪 uznaje to również za przecięcie.

Wejście 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

Wyjście 2

0
2

Wejście i wyjście 3

Zobacz pliki shallot/shallot.in i shallot/shallot.ans w katalogu zawodnika.

Ograniczenia

Gwarantuje się, że w każdym zapytaniu $T$ nie przekracza liczby dotychczasowych operacji. Wszystkie dane wejściowe są liczbami całkowitymi.

Występują cztery rozłączne rodzaje danych specjalnych:

1. Dla $15\%$ danych gwarantuje się $1\le N,M\le1000$.
2. Dla $15\%$ danych gwarantuje się, że dla $i$-tej operacji $T=i-1$.
3. Dla $15\%$ danych gwarantuje się $C=0$ i brak operacji modyfikacji.
4. Dla $15\%$ danych w operacjach wstawienia gwarantuje się $Y=0$ (dla danych zaszyfrowanych chodzi o $Y$ po odszyfrowaniu), czyli podane proste są równoległe do osi $x$.

Dla powyższych danych gwarantuje się również $1\le N,M\le5\times10^4$.

Dla $100\%$ danych gwarantuje się $1\le N,M\le10^5$, wszystkie współrzędne należą do przedziału $[-10^8,10^8]$, suma odpowiedzi na wszystkie zapytania w jednym zestawie danych nie przekracza $10^6$, a liczba operacji wstawienia nie przekracza $5\times10^4$. Uwaga: odcinki mogą się wzajemnie przecinać.