¡Poco se sabe que a las vacas les encantan los rompecabezas! Para el cumpleaños de Bessie, Farmer John le regala un interesante rompecabezas mecánico. Son tres objetos sólidos de cuadrados unidad $1\times1$ pegados. Cada forma es «conexa»: de cualquier cuadrado se llega a cualquier otro avanzando al norte, sur, este u oeste por cuadrados del objeto.

Se mueve un objeto deslizándolo repetidamente una unidad al norte, sur, este u oeste. El objetivo es separarlos, con sus cajas delimitadoras disjuntas entre sí. Dadas las formas y posiciones, ayuda a Bessie a decidir si pueden separarse. Una configuración inseparable está bloqueada.

[Nota: los programas que solo adivinen aleatoriamente la salida pueden ser descalificados, obteniendo cero puntos.]

Entrada

• Línea 1: tres enteros separados por espacios, $N1$, $N2$, $N3$, números de cuadrados unidad de los objetos 1, 2, 3 respectivamente.
• Líneas $2\ldots1+N1$: cada línea describe la coordenada $(x,y)$ de la esquina suroeste de un cuadrado del objeto 1. Todas las coordenadas están en $0\ldots9$.
• Líneas $2+N1\ldots1+N1+N2$: cada línea describe la coordenada $(x,y)$ de la esquina suroeste de un cuadrado del objeto 2. Todas las coordenadas están en $0\ldots9$.
• Líneas $2+N1+N2\ldots1+N1+N2+N3$: cada línea describe la coordenada $(x,y)$ de la esquina suroeste de un cuadrado del objeto 3. Todas las coordenadas están en $0\ldots9$.

Salida

• Línea 1: imprime 1 si pueden separarse, o 0 si están bloqueados.

Ejemplos

Entrada 1

12 3 5
0 0
1 0
2 0
3 0
3 1
0 1
0 2
0 3
0 4
1 4
2 4
3 4
2 1
2 2
1 2
2 3
3 3
4 3
4 4
4 2

Salida 1

1

Nota

El objeto 1 tiene 12 cuadrados, el 2 tiene 3 y el 3 tiene 5. Las formas son las de la figura anterior.

Autor del problema: Brian Dean, 2012