小葱 и 小绪 — хорошие друзья. После того как 小葱 за один набор из 11 вытягиваний получил 1UR2SR, 小绪 решил, что ему невероятно везёт, и придумал задачу, чтобы проверить его удачу.
Сначала 小绪 нарисовал на плоскости $N$ точек $P_1,P_2,\ldots,P_N$. Затем он последовательно соединил их, то есть провёл отрезки $(P_1,P_2),(P_2,P_3),\ldots,(P_{N-1},P_N)$, получив $N-1$ отрезков.
После этого 小绪 каждый раз рисовал на плоскости прямую и спрашивал 小葱, сколько отрезков она пересекает. В частности, пересечение в конце отрезка также считается пересечением, как и случай, когда прямая целиком содержит отрезок. Такая задача, конечно, не затрудняла 小葱: благодаря своей удаче он мог интуитивно дать правильный ответ.
小绪 захотел выяснить, насколько велика удача 小葱, и усложнил задачу.
Помимо запросов, время от времени 小绪 вставляет новую точку $P$ между $P_i$ и $P_{i+1}$, после чего заново нумерует все точки по порядку. Индексы точек, следующих за $P_i$, увеличиваются, а точка $P$ становится новой точкой $P_{i+1}$. В частности, точку $P$ можно вставить перед первой точкой или после последней.
Необычайно удачливый 小葱 по-прежнему легко давал ответы, поэтому 小绪 ещё больше усложнил задачу.
После каждой вставки или запроса 小绪 записывает все отрезки в получившемся состоянии, называя его исторической версией. Историческая версия $T$ — это версия, полученная после $T$-й операции.
Теперь вставка новой точки выполняется на основе некоторой исторической версии $T$: в неё вставляется точка $P$, и получается новая историческая версия. После запроса новая историческая версия совпадает с версией $T$, о которой был задан запрос.
Теперь запрос 小绪 к 小葱 устроен так: для исторической версии $T$ задаётся прямая, и требуется узнать, сколько отрезков она пересекает.
Хотя 小葱 очень удачлив, перед такой задачей он оказался бессилен. Ему осталось лишь обратиться к вам, участнику CTSC, и попросить помочь решить эту задачу.
Входные данные
Входной файл — shallot.in.
В первой строке даны два целых числа $N,M,C$, обозначающие начальное число точек, общее число операций и наличие шифрования данных. Если $C=1$, данные зашифрованы: значения $X_0,Y_0,X,Y$ в запросах и $X,Y$ в операциях вставки зашифрованы. Чтобы получить правильные значения, нужно применить к ним побитовое исключающее ИЛИ с $last\_ans$, где $last\_ans$ — ответ на предыдущий запрос. Изначально $last\_ans=0$.
В следующих $N$ строках дано по два целых числа: числа в $i$-й строке задают абсциссу и ординату точки $P_i$.
Следующие $M$ строк описывают $M$ операций 小绪. Результат операции в $i$-й строке, считая с $1$, является исторической версией $i$.
В начале каждой операции стоит буква, обозначающая её тип.
Если это H, операция является запросом. Далее следуют пять целых чисел $T,X_0,Y_0,X,Y$. Для исторической версии $T$ 小绪 задаёт прямую, проходящую через $(X_0,Y_0)$ с направлением $(X,Y)$, а 小葱 должен ответить, сколько отрезков она пересекает.
Если это Z, операция является вставкой. Далее следуют четыре числа $T,i,X,Y$: на основе исторической версии $T$ 小绪 вставляет после $P_i$ точку с координатами $(X,Y)$. В частности, если $i=0$, точка вставляется перед $P_1$.
Выходные данные
В файл shallot.out для каждого запроса выведите отдельной строкой одно целое число — правильный ответ, который должен дать 小葱.
Примеры
Входные данные 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
Выходные данные 1
1 0 1
Примечание
В третьем запросе прямая целиком содержит отрезок, и 小绪 также считает это пересечением.
Входные данные 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
Выходные данные 2
0 2
Пример 3
См. файлы shallot/shallot.in и shallot/shallot.ans в каталоге участника.
Ограничения
Гарантируется, что значение $T$ в каждом запросе не превосходит текущего числа операций. Все входные данные — целые числа.
Есть следующие четыре типа специальных данных, попарно не пересекающиеся:
- Для $15\%$ данных гарантируется $1\le N,M\le1000$.
- Для $15\%$ данных гарантируется, что в $i$-й операции $T=i-1$.
- Для $15\%$ данных гарантируется $C=0$ и отсутствие операций изменения.
- Для $15\%$ данных в операциях вставки гарантируется $Y=0$; для зашифрованных данных имеется в виду значение $Y$ после расшифровки. То есть заданная прямая параллельна оси $x$.
Для перечисленных выше данных также гарантируется $1\le N,M\le5\times10^4$.
Для $100\%$ данных гарантируется $1\le N,M\le10^5$. Все координаты лежат в диапазоне $[-10^8,10^8]$, сумма ответов на все запросы в каждом наборе данных не превосходит $10^6$, а число операций вставки не превосходит $5\times10^4$. Обратите внимание, что отрезки могут пересекаться друг с другом.