Há $N$ cabras espalhadas por uma ampla planície, pastando tranquilamente. Nenhuma dupla ocupa a mesma posição. Elas são preguiçosas: não se deslocam, apenas giram no próprio lugar às vezes. Na verdade, todas são robôs que não podem andar e só conseguem girar paradas. Seus narizes são luzes LED que podem ser acesas remotamente, e seus olhos são câmeras de alto desempenho cujas imagens podem ser vistas remotamente em tempo real e salvas. Uma cabra consegue ver seu próprio nariz. Os olhos também enxergam através das outras cabras, permitindo contar quantas há mesmo quando se sobrepõem na imagem. O campo de visão horizontal é de $180^\circ$, incluindo a fronteira desse campo.

Dependendo das posições, algumas cabras conseguem ver todas as $N$ cabras de uma vez, enquanto outras não conseguem em nenhuma direção. Por exemplo, nas seis cabras numeradas de $0$ a $5$ da figura, a cabra $5$ vê todas as seis ao mesmo tempo, mas a cabra $2$ não consegue, qualquer que seja a direção em que olhe.

Para um experimento especial, escolhem-se duas cabras distintas que possam, cada uma, ver todas as $N$ cabras de uma vez, e uma cabra arbitrária dentre as restantes. Acendem-se os narizes das três escolhidas para identificar suas posições de qualquer lugar. Observam-se as imagens dos olhos dessas cabras e salva-se, para cada uma, uma cena em que as três cabras iluminadas apareçam no mesmo quadro. Examinam-se as três cenas uma por uma. Em cada cena, marcam-se especialmente as três cabras iluminadas e todas as cabras entre as outras duas cabras iluminadas, incluindo as fronteiras. O objetivo é contar quantas das $N$ cabras são marcadas nas três cenas.

Por exemplo, se as três escolhidas dentre as seis forem indicadas por pontos vermelhos, as figuras abaixo mostram as cabras marcadas do ponto de vista de cada cabra escolhida. (As figuras não são as próprias cenas salvas.) Nesse caso, $4$ cabras são marcadas todas as três vezes.

Você deve implementar as duas funções a seguir para o experimento.

• void init( int x[], int y[] ): É chamada primeiro e exatamente uma vez. Os arrays (vetores) x e y têm tamanho $N$. Os argumentos x[0..N-1] e y[0..N-1] fornecem as coordenadas $x$ e $y$ das cabras. A cabra $i$ ($0\le i\le N-1$) está em (x[i], y[i]).
• int count( int a, int b, int c ): Usando as coordenadas (x[a], y[a]), (x[b], y[b]) e (x[c], y[c]) das três cabras dadas, calcula e retorna o número de cabras marcadas todas as três vezes.

Detalhes de implementação

Você deve enviar um único arquivo chamado goat.cpp que implemente as seguintes funções.

void init( int x[], int y[] );
int count( int a, int b, int c );

Essas funções devem funcionar conforme descrito. Você pode definir outras funções para uso interno. O código enviado não deve realizar entrada/saída nem acessar outros arquivos.

Avaliador de exemplo

O avaliador fornecido lê a entrada no seguinte formato.

• Primeira linha: $N\ Q$, onde $N$ é o número de cabras e $Q$ o número de consultas.
• Cada uma das próximas $N$ linhas: $x\ y$, as coordenadas $x$ e $y$ de uma cabra.
• Cada uma das próximas $Q$ linhas: $a\ b\ c$ ($a,b,c$), os índices das três cabras, com $0\le a,b,c\le N-1$.

Para cada consulta, o avaliador imprime em uma linha separada o número de cabras que satisfazem a condição.

Restrições

• $3\le N\le 3000$
• $1\le Q\le 5\times10^6$
• As coordenadas $x$ e $y$ de todas as cabras estão entre $0$ e $10^9$, inclusive.

Subtarefas

1 (5 pontos)

• $N\le 500$, $Q\le 10^5$
• Não há três pontos colineares.

2 (17 pontos)

• $N\le 500$, $Q\le 10^5$

3 (10 pontos)

• $N\le 500$
• Não há três pontos colineares.

4 (8 pontos)

• $N\le 500$

5 (29 pontos)

• Não há três pontos colineares.

6 (31 pontos)

• Sem restrições adicionais.

Exemplos

Entrada 1

6 3
0 0
1 1
2 2
4 3
0 2
2 0
0 5 2
1 3 4
4 1 5

Saída 1

4
4
3

Abaixo estão, em ordem, as chamadas de funções e seus resultados para o exemplo 1.