Wenig bekannt ist, dass Kühe Rätsel lieben! Zum Geburtstag schenkt Farmer John Bessie ein interessantes mechanisches Rätsel. Es besteht aus drei festen Objekten aus zusammengeklebten Einheitsquadraten $1\times1$. Jede Form ist „zusammenhängend“: Von jedem Quadrat erreicht man jedes andere über Objektquadrate mit Schritten nach Norden, Süden, Osten oder Westen.

Ein Objekt wird wiederholt um eine Einheit nach Norden, Süden, Osten oder Westen verschoben. Ziel ist, sie zu trennen, sodass ihre Begrenzungsrechtecke paarweise disjunkt sind. Hilf Bessie anhand der Formen und Positionen zu entscheiden, ob sie trennbar sind. Eine untrennbare Anordnung heißt gesperrt.

[Hinweis: Programme, die nur zufällige Ausgaben erraten, können disqualifiziert werden und null Punkte erhalten.]

Eingabe

• Zeile 1: drei durch Leerzeichen getrennte ganze Zahlen $N1$, $N2$, $N3$, die Zahlen der Einheitsquadrate in Objekt 1, 2, 3.
• Zeilen $2\ldots1+N1$: Jede Zeile beschreibt die Koordinate $(x,y)$ der südwestlichen Ecke eines Quadrats in Objekt 1. Alle Koordinaten liegen in $0\ldots9$.
• Zeilen $2+N1\ldots1+N1+N2$: Jede Zeile beschreibt die Koordinate $(x,y)$ der südwestlichen Ecke eines Quadrats in Objekt 2. Alle Koordinaten liegen in $0\ldots9$.
• Zeilen $2+N1+N2\ldots1+N1+N2+N3$: Jede Zeile beschreibt die Koordinate $(x,y)$ der südwestlichen Ecke eines Quadrats in Objekt 3. Alle Koordinaten liegen in $0\ldots9$.

Ausgabe

• Zeile 1: Gib 1 aus, wenn sie trennbar sind, andernfalls 0, wenn sie gesperrt sind.

Beispiele

Eingabe 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

Ausgabe 1

1

Hinweis

Objekt 1 hat 12 Quadrate, Objekt 2 hat 3 und Objekt 3 hat 5. Die Formen sind in der Abbildung oben gezeigt.

Aufgabenautor: Brian Dean, 2012