题目描述

小葱和小绪是一对好朋友，自从小葱 $11$ 连出了 1UR2SR 之后，小绪就觉得小葱的人品特别好。

于是小绪给小葱出了一道题来测试小葱的人品。 小绪首先在平面上画了 $N$ 个点，分别是 $P_1,P_2,\dots,P_N$。

小绪把这 $N$ 个点顺次相连，即连接 $(P_1,P_2),(P_2,P_3),\dots,(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，给出一条直线，询问这条直线会与多少条线段相交。

小葱虽然人品很好，但面对这样的问题却也束手无策了，他只好找到来参加 CTSC 的你，请你来帮他解决这个问题。

输入格式

第一行三个整数 $N,M,C$，表示一开始的点数和总共的操作数，以及数据是否加密。

如果 $C=1$，那么代表数据被加密过，每次询问操作中的 $X0,Y0,X,Y$ 以及插入操作中的 $X,Y$ 都是被加密过的数据，你需要将它们异或 $lastans$ 从而得到正确的数据，其中 $lastans$ 是上一次询问的答案，刚开始 $lastans=0$。

接下来 $N$ 行每行两个整数，其中第 $i$ 行的两个整数表示 $P_i$ 的横坐标和纵坐标。

接下来 $M$ 行，表示小绪的 $M$ 次操作，其中第 $i$ 行（从 $1$ 开始标号）操作后得到的结果为历史版本 $i$。

对于每次操作，首先会有一个字母代表小绪的这次操作的操作类型。

如果这个字母是 H，代表本次操作为一次询问操作。

接下来会有五个整数 $T,X0,Y0,X,Y$，代表在历史版本 $T$ 的情况下，小绪给出一条经过 $(X0,Y0)$，方向为 $(X,Y)$ 的直线，小葱要回答出它会和多少条直线相交。

如果这个字母是 Z，代表本次操作为一次插入操作。

接下来会有四个数 $T,i,X,Y$，代表小绪在历史版本T的基础上，在 $P_i$ 后面插入了一个坐标为 $(X,Y)$ 的点。特别地，如果 $i=0$，表示该点在 $P_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
0
1

数据规模与约定

下面四类特殊数据，它们两两没有交集：

对于 $10\%$ 的数据，$1 \le n,m \le 1000$。

对于 $15\%$ 的数据，对于第 $i$ 次操作，$T=i-1$。

对于 $15\%$ 的数据，保证 $C=0$ 且不存在修改操作。

对于 $15\%$ 的数据，对于询问操作保证 $Y=0$ （加密过的数据指解密后的 $Y$），即给出直线平行于 $x$ 轴。

最后对于 $100\%$ 的数据，$1 \le n, m, \le 10^5$，所有坐标范围在 $[-10^8,10^8]$，且每组数据中所有询问的答案的总和不超过 $10^6$，插入操作的次数不会超过 $5 \times 10^4$。

注意这些线段可能会互相相交。