Hay $N$ cabras dispersas en una amplia llanura, pastando tranquilamente. No hay dos en la misma posición. Son perezosas: no se desplazan y solo giran a veces sobre sí mismas. En realidad, todas son robots que no pueden caminar, sino únicamente girar en su sitio. Sus narices son luces LED que pueden encenderse a distancia, y sus ojos son cámaras de alto rendimiento cuyas imágenes pueden verse remotamente en tiempo real y guardarse. Una cabra ve su propia nariz. Sus ojos también permiten ver a través de otras cabras, por lo que puede saber cuántas hay aunque se superpongan en la imagen. Su campo de visión horizontal es de $180^\circ$, incluyendo sus límites.

Según las posiciones, algunas cabras pueden ver las $N$ cabras a la vez y otras no pueden hacerlo en ninguna dirección. Por ejemplo, con las seis cabras numeradas de $0$ a $5$ de la figura, la cabra $5$ ve las seis simultáneamente, pero la $2$ no puede hacerlo por mucho que cambie la dirección de su mirada.

Para un experimento especial, se eligen dos cabras distintas que puedan ver, cada una, las $N$ cabras a la vez, y una cabra cualquiera de las restantes. Se encienden las narices de las tres elegidas para identificar su posición desde cualquier lugar. Se observan las imágenes de sus ojos y se guarda, para cada cabra elegida, una escena en la que las tres cabras iluminadas aparezcan en el mismo encuadre. Se examinan las tres escenas una por una. En cada una se marcan especialmente las tres cabras iluminadas y todas las cabras situadas entre las otras dos cabras iluminadas, incluidos los límites. El objetivo es contar cuántas de las $N$ cabras reciben una marca en las tres escenas.

Por ejemplo, si las tres elegidas entre las seis se representan con puntos rojos, las figuras siguientes muestran las cabras marcadas desde el punto de vista de cada cabra elegida. (Las figuras no son las escenas guardadas.) En este caso, $4$ cabras reciben las tres marcas.

Debes implementar las siguientes dos funciones para el experimento.

• void init( int x[], int y[] ): Se llama primero y exactamente una vez. Los arreglos (vectores) x e y tienen tamaño $N$. Los argumentos x[0..N-1] e y[0..N-1] dan las coordenadas $x$ e $y$ de las cabras. La cabra $i$ ($0\le i\le N-1$) está en (x[i], y[i]).
• int count( int a, int b, int c ): Usando las coordenadas (x[a], y[a]), (x[b], y[b]) y (x[c], y[c]) de las tres cabras dadas, calcula y devuelve el número de cabras marcadas las tres veces.

Detalles de implementación

Debes enviar un único archivo llamado goat.cpp que implemente las siguientes funciones.

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

Las funciones deben comportarse como se ha descrito. Puedes definir otras funciones para uso interno. El código enviado no debe realizar entrada/salida ni acceder a otros archivos.

Evaluador de ejemplo

El evaluador proporcionado lee la entrada con el siguiente formato.

• Primera línea: $N\ Q$, donde $N$ es el número de cabras y $Q$ el número de consultas.
• Cada una de las siguientes $N$ líneas: $x\ y$, las coordenadas $x$ e $y$ de una cabra.
• Cada una de las siguientes $Q$ líneas: $a\ b\ c$ ($a,b,c$), los índices de las tres cabras, con $0\le a,b,c\le N-1$.

Para cada consulta, el evaluador imprime en una línea independiente el número de cabras que cumplen la condición.

Restricciones

• $3\le N\le 3000$
• $1\le Q\le 5\times10^6$
• Las coordenadas $x$ e $y$ de todas las cabras están entre $0$ y $10^9$, inclusive.

Subtareas

1 (5 puntos)

• $N\le 500$, $Q\le 10^5$
• No hay tres puntos colineales.

2 (17 puntos)

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

3 (10 puntos)

• $N\le 500$
• No hay tres puntos colineales.

4 (8 puntos)

• $N\le 500$

5 (29 puntos)

• No hay tres puntos colineales.

6 (31 puntos)

• Sin restricciones adicionales.

Ejemplos

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

Salida 1

4
4
3

A continuación se muestran, en orden, las llamadas a funciones y sus resultados para el ejemplo 1.