On sait peu que les vaches adorent les casse-têtes ! Pour l'anniversaire de Bessie, Farmer John lui offre un casse-tête mécanique intéressant. Il comprend trois objets solides, chacun formé de carrés unités $1\times1$ collés. Chaque forme est « connexe » : de n'importe quel carré, on peut atteindre tout autre en avançant au nord, au sud, à l'est ou à l'ouest à travers les carrés de l'objet.

Un objet se déplace par glissements répétés d'une unité vers le nord, le sud, l'est ou l'ouest. Le but est de les séparer : leurs rectangles englobants doivent être deux à deux disjoints. Étant donné les formes et positions, aidez Bessie à décider s'ils peuvent être séparés. Une configuration inséparable est dite verrouillée.

[Remarque : les programmes ne faisant que deviner aléatoirement la sortie peuvent être disqualifiés avec zéro point.]

Entrée

• Ligne 1 : trois entiers séparés par des espaces, $N1$, $N2$, $N3$, nombres de carrés unités des objets 1, 2, 3 respectivement.
• Lignes $2\ldots1+N1$ : chaque ligne donne les coordonnées $(x,y)$ du coin sud-ouest d'un carré de l'objet 1. Toutes les coordonnées sont dans $0\ldots9$.
• Lignes $2+N1\ldots1+N1+N2$ : chaque ligne donne les coordonnées $(x,y)$ du coin sud-ouest d'un carré de l'objet 2. Toutes les coordonnées sont dans $0\ldots9$.
• Lignes $2+N1+N2\ldots1+N1+N2+N3$ : chaque ligne donne les coordonnées $(x,y)$ du coin sud-ouest d'un carré de l'objet 3. Toutes les coordonnées sont dans $0\ldots9$.

Sortie

• Ligne 1 : affichez 1 si les objets peuvent être séparés, ou 0 s'ils sont verrouillés.

Exemples

Entrée 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

Sortie 1

1

Remarque

L'objet 1 contient 12 carrés, l'objet 2 en contient 3 et l'objet 3 en contient 5. Les formes sont celles de la figure ci-dessus.

Auteur du problème : Brian Dean, 2012