小葱 e 小绪 são bons amigos. Desde que 小葱 conseguiu 1UR2SR numa sequência de 11 tentativas, 小绪 passou a achar que ele tinha muita sorte e lhe propôs um problema para testar essa sorte.

Primeiro, 小绪 desenhou $N$ pontos no plano, $P_1,P_2,\ldots,P_N$. Ligou-os sucessivamente, conectando $(P_1,P_2),(P_2,P_3),\ldots,(P_{N-1},P_N)$, e obteve $N-1$ segmentos de reta.

Depois, a cada vez, 小绪 desenhava uma reta no plano e perguntava a 小葱 quantos segmentos ela intersectava. Em particular, uma interseção num extremo de um segmento conta como interseção, e uma reta que contém completamente um segmento também conta como interseção.

Naturalmente, um problema assim não era difícil para 小葱: bastava confiar na sua sorte e intuição para dar a resposta correta.

小绪 queria descobrir até que ponto 小葱 tinha sorte, por isso aumentou a dificuldade:

Além das consultas, de vez em quando 小绪 insere um novo ponto $P$ entre $P_i$ e $P_{i+1}$ e renumera todos os pontos pela ordem. Isto é, os índices dos pontos depois de $P_i$ aumentam sucessivamente, e $P$ torna-se o novo ponto $P_{i+1}$. Em particular, $P$ também pode ser inserido antes do primeiro ponto ou depois do último.

小葱, que tem imensa sorte, continuava a responder facilmente, por isso 小绪 aumentou novamente a dificuldade:

Depois de cada inserção ou consulta, 小绪 regista todos os segmentos existentes após a operação, formando uma versão histórica. A versão histórica $T$ é a obtida depois da operação $T$.

A operação de inserção passa a inserir um ponto $P$ numa determinada versão histórica $T$, produzindo uma nova versão histórica. Depois de uma consulta, a nova versão histórica é a própria versão histórica $T$ consultada.

As consultas de 小绪 passam a indicar uma versão histórica $T$ e uma reta, perguntando quantos segmentos dessa versão a reta intersecta.

Apesar de ter muita sorte, 小葱 não sabe como resolver este problema. Por isso, procurou-te, que vieste participar no CTSC, para te pedir ajuda.

Entrada

O ficheiro de entrada é shallot.in.

A primeira linha contém dois inteiros $N,M,C$, indicando o número inicial de pontos, o número total de operações e se os dados estão cifrados. Se $C=1$, os dados estão cifrados: os valores $X_0,Y_0,X,Y$ de cada consulta e os valores $X,Y$ de cada inserção estão cifrados. Deves aplicar-lhes XOR com $\mathit{last\_ans}$ para obter os dados corretos, sendo $\mathit{last\_ans}$ a resposta à última consulta. Inicialmente, $\mathit{last\_ans}=0$.

As $N$ linhas seguintes contêm dois inteiros cada. Os dois valores da linha $i$ são, respetivamente, a abcissa e a ordenada de $P_i$.

As $M$ linhas seguintes descrevem as $M$ operações de 小绪. O resultado após a operação da linha $i$ (numerada a partir de $1$) é a versão histórica $i$.

Cada operação começa com uma letra que indica o seu tipo.

Se a letra for 'H', trata-se de uma consulta. Seguem-se cinco inteiros $T,X_0,Y_0,X,Y$, indicando que, na versão histórica $T$, 小绪 fornece uma reta que passa por $(X_0,Y_0)$ e tem direção $(X,Y)$. 小葱 deve responder quantos segmentos ela intersecta.

Se a letra for 'Z', trata-se de uma inserção. Seguem-se quatro números $T,i,X,Y$, indicando que 小绪 insere, na versão histórica $T$, um ponto de coordenadas $(X,Y)$ depois de $P_i$. Em particular, se $i=0$, o ponto é inserido antes de $P_1$.

Saída

No ficheiro de saída shallot.out, para cada consulta, escreve uma linha com um inteiro que represente a resposta correta que 小葱 deve dar.

Exemplos

Entrada 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

Saída 1

1
0
1

Explicação

Na terceira consulta, a reta contém completamente o segmento, o que 小绪 também considera uma interseção.

Entrada 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

Saída 2

0
2

Exemplo 3

Consulta os ficheiros shallot/shallot.in e shallot/shallot.ans no diretório do participante.

Restrições

É garantido que o valor $T$ de cada consulta não excede o número atual de operações. Todos os dados de entrada são inteiros.

Existem quatro categorias especiais de dados, duas a duas disjuntas:

1. Em $15\%$ dos dados, é garantido que $1\le N,M\le 1000$;
2. Em $15\%$ dos dados, é garantido que, na operação $i$, $T=i-1$;
3. Em $15\%$ dos dados, é garantido que $C=0$ e não existem operações de modificação;
4. Em $15\%$ dos dados, nas operações de inserção, é garantido que $Y=0$ (para dados cifrados, refere-se a $Y$ depois de decifrado), isto é, a reta fornecida é paralela ao eixo $x$.

Para os dados acima, também é garantido que $1\le N,M\le 5\times 10^4$.

Em $100\%$ dos dados, é garantido que $1\le N,M\le 10^5$, todas as coordenadas pertencem a $[-10^8,10^8]$, a soma das respostas a todas as consultas de cada conjunto de dados não excede $10^6$, e o número de inserções não excede $5\times 10^4$. Nota que estes segmentos podem intersectar-se uns aos outros.