Poucos sabem que as vacas adoram quebra-cabeças! No aniversário de Bessie, Farmer John lhe dá um interessante quebra-cabeça mecânico. São três objetos sólidos de quadrados unitários $1\times1$ colados. Cada forma é «conexa»: de qualquer quadrado chega-se a qualquer outro, andando ao norte, sul, leste ou oeste por quadrados do objeto.

Um objeto se move por deslizamentos repetidos de uma unidade ao norte, sul, leste ou oeste. O objetivo é separá-los, com suas caixas delimitadoras disjuntas entre si. Dados os formatos e posições, ajude Bessie a decidir se podem ser separados. Uma configuração inseparável é bloqueada.

[Nota: programas que apenas adivinhem aleatoriamente a saída podem ser desqualificados, recebendo zero pontos.]

Entrada

• Linha 1: três inteiros separados por espaços, $N1$, $N2$, $N3$, números de quadrados unitários dos objetos 1, 2, 3 respectivamente.
• Linhas $2\ldots1+N1$: cada linha descreve a coordenada $(x,y)$ do canto sudoeste de um quadrado do objeto 1. Todas as coordenadas estão em $0\ldots9$.
• Linhas $2+N1\ldots1+N1+N2$: cada linha descreve a coordenada $(x,y)$ do canto sudoeste de um quadrado do objeto 2. Todas as coordenadas estão em $0\ldots9$.
• Linhas $2+N1+N2\ldots1+N1+N2+N3$: cada linha descreve a coordenada $(x,y)$ do canto sudoeste de um quadrado do objeto 3. Todas as coordenadas estão em $0\ldots9$.

Saída

• Linha 1: imprima 1 se podem ser separados, ou 0 se estão bloqueados.

Exemplos

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

Saída 1

1

Nota

O objeto 1 tem 12 quadrados, o 2 tem 3 e o 3 tem 5. As formas são as da figura acima.

Autor do problema: Brian Dean, 2012