小葱と小绪は仲のよい友達です。小葱が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$ 本の線分を作りました。

その後、小绪は毎回平面上に直線を1本描き、その直線が何本の線分と交わるかを小葱に尋ねます。特に、線分の端点で交わる場合も、直線が線分全体を覆う場合も、交差として数えます。

この程度の問題では小葱は困りません。自分の運のよさを頼りに、直感だけで正解できます。

小绪は小葱がどれほど強運なのかを試すため、問題を難しくしました。

質問に加えて、ときどき新しい点 $P$ を $P_i$ と $P_{i+1}$ の間に挿入し、その後すべての点の添字を順番に付け直します。つまり、$P_i$ より後ろの点の添字がそれぞれ増え、点 $P$ が新しい $P_{i+1}$ になります。特に、最初の点の前や最後の点の後ろに挿入することもできます。

非常に強運な小葱は依然として簡単に答えられたため、小绪はさらに難しくしました。

挿入または質問のたびに、小绪は操作後のすべての線分を記録し、それを履歴バージョンと呼びます。履歴バージョン $T$ は、$T$ 回目の操作の後に得られたバージョンを表します。

新しい点を挿入する操作では、ある履歴バージョン $T$ をもとに点 $P$ を挿入し、新しい履歴バージョンを得ることにしました。質問操作の後の新しい履歴バージョンは、質問の対象とした履歴バージョン $T$ と同じです。

質問も変更し、ある履歴バージョン $T$ に対して直線を1本与え、その直線が何本の線分と交わるかを尋ねることにしました。

小葱は強運ですが、この問題にはお手上げです。そこで CTSC に参加しているあなたに、この問題を解いてほしいと頼みました。

入力

入力ファイルは shallot.in です。

最初の行には整数 $N,M,C$ が与えられ、初期の点の数、操作の総数、データが暗号化されているかを表します。$C=1$ の場合、各質問操作の $X_0,Y_0,X,Y$ と各挿入操作の $X,Y$ は暗号化されています。これらと $last\_ans$ の排他的論理和を取り、正しいデータを得てください。$last\_ans$ は直前の質問の答えで、初期値は $last\_ans=0$ です。

続く $N$ 行にはそれぞれ整数が2個あり、$i$ 行目の2個の数は点 $P_i$ の横座標と縦座標を表します。

続く $M$ 行は小绪の $M$ 回の操作を表します。$i$ 行目（1から数える）の操作後の結果が履歴バージョン $i$ です。

各操作の最初には、その操作の種類を表す英字が1文字あります。

H の場合は質問操作です。続く5個の整数 $T,X_0,Y_0,X,Y$ は、履歴バージョン $T$ において、点 $(X_0,Y_0)$ を通り方向ベクトルが $(X,Y)$ である直線を小绪が与えることを表します。小葱は、この直線が何本の線分と交わるかを答えます。

Z の場合は挿入操作です。続く4個の数 $T,i,X,Y$ は、履歴バージョン $T$ をもとに、$P_i$ の後ろへ座標 $(X,Y)$ の点を挿入することを表します。特に $i=0$ の場合、点は $P_1$ の前に挿入されます。

出力

出力ファイル shallot.out には、質問操作ごとに小葱が答えるべき正しい答えを、1行に整数1個ずつ出力してください。

入出力例

入力 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

注記

3回目の質問では、直線が線分全体を覆っています。小绪はこれも交差とみなします。

入力 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$ は、その時点の操作数以下であることが保証されます。入力データはすべて整数です。

次の4種類の特別なデータがあり、互いに重なりません。

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$ が保証されます。

すべてのデータで、$1\le N,M\le10^5$、すべての座標は $[-10^8,10^8]$ の範囲内です。また、各データにおけるすべての質問の答えの合計は $10^6$ 以下で、挿入操作は $5\times10^4$ 回以下です。線分どうしが交差する場合があることに注意してください。