小葱同小绪係一對好朋友。自從小葱喺11連抽入面抽到1UR2SR之後，小绪就覺得小葱嘅人品特別好，於是出咗一道題嚟測試佢嘅人品。
小绪首先喺平面上畫咗 $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$ 次操作後得到嘅歷史版本。
插入新點嘅操作改為喺某個歷史版本 $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$ 一定小於或者等於當前操作嘅數量，所有輸入資料都係整數。
有以下4類特殊資料，佢哋兩兩冇交集：
- 對於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$。注意，呢啲線段有可能互相相交。