小葱 і 小绪 — добрі друзі. Відтоді як 小葱 отримав 1UR2SR під час серії з 11 витягувань, 小绪 вважає, що йому надзвичайно щастить. Тому 小绪 запропонував 小葱 задачу, щоб перевірити його везіння.

Спочатку 小绪 намалював на площині $N$ точок $P_1,P_2,\ldots,P_N$. Він послідовно сполучив ці $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$-ї операції.

Тепер вставлення нової точки означає вставлення точки $P$ на основі певної історичної версії $T$ з отриманням нової історичної версії. Після запиту новою історичною версією стає історична версія $T$, до якої стосувався запит.

Тепер у запиті 小绪 задає історичну версію $T$ і пряму та запитує 小葱, скільки відрізків вона перетинає.

Хоча 小葱 дуже щасливий, із такою задачею він уже нічого не може вдіяти. Йому довелося звернутися до тебе, учасника CTSC, з проханням допомогти розв'язати цю задачу.

Вхідні дані

Вхідний файл — shallot.in.

Перший рядок містить два цілі числа $N,M,C$, що задають початкову кількість точок, загальну кількість операцій і те, чи зашифровані дані. Якщо $C=1$, дані зашифровані: значення $X_0,Y_0,X,Y$ у кожному запиті та $X,Y$ в операції вставлення є зашифрованими. Щоб отримати правильні дані, потрібно застосувати до них побітове виключне АБО з $\mathit{last\_ans}$, де $\mathit{last\_ans}$ — відповідь на попередній запит. Спочатку $\mathit{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$ не перевищує поточної кількості операцій. Усі вхідні дані — цілі числа.

Є чотири наведені нижче спеціальні категорії даних, які попарно не перетинаються:

1. Для $15\%$ даних гарантується $1\le N,M\le1000$;
2. Для $15\%$ даних гарантується, що для $i$-ї операції $T=i-1$;
3. Для $15\%$ даних гарантується $C=0$, і операцій зміни немає;
4. Для $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$. Зауважте, що ці відрізки можуть перетинатися між собою.