题目描述

小葱和小绪是一对好朋友，自从小葱 11 连出了 1UR2SR 之后，小绪就觉得小葱的人品特别好，于是小绪给小葱出了一道题来测试小葱的人品。

小绪首先在平面上画了 \(N\) 个点，分别是 \(P_1,P_2,\cdots,P_N\)。

小绪把这 \(N\) 个点顺次相连，即连接 \((P_1,P_2)\)，\((P_2,P_3)\),…,\((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\) ，那么代表数据被加密过，每次询问操作中的 \(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\) 之前。

输出

要求对于每一次询问操作，输出一行一个整数代表小葱应该回答的正确答案。

样例 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

解释

对于第三次询问，直线完全覆盖了线段，小绪会认为这也算相交。

数据范围限制

保证每次询问操作的 \(T\) 一定小于等于当前操作的数量，所有输入数据均为整数。

有以下 \(4\) 类特殊数据，它们两两没有交集：

1.对于 \(10\%\) 的数据，保证 \(1 \leq N,M \leq 1000\)；

2.对于 \(15\%\) 的数据，保证对于第 \(i\) 次操作，\(T=i-1\)；
3.对于 \(15\%\) 的数据，保证 \(C=0\) 且不存在修改操作；

4.对于 \(15\%\) 的数据，对于插入操作，保证 \(Y=0\)（加密过的数据指解密后的Y），即给出的直线平行于 \(x\) 轴。

以上数据还保证 \(1 \leq N\),\(M \leq 5 \times 10^4\)。

对于 \(100\%\) 的数据，保证 \(1 \leq N,M \leq 10^5\),所有的坐标范围在 \([-10^8,10^8]\) 内，且每组数据中所有询问的答案总和不超过 \(10^6\)，插入操作的次数不会超过 \(5 \times 10^4\)。注意这些线段可能会互相相交。

限制

每个测试点时限：5s
内存限制：2GB

来源

CTSC2015