Farmer John möchte sein Haus dekorieren. Im Porzellanladen findet er eine zarte gläserne Kuhfigur und will sie kaufen, da sie perfekt auf den Kaminsims passt.
Ihre Form ist ein $N \times M$-Zeichengitter ($3 \leq N, M \leq 500$), wie unten. Kleinbuchstaben bilden die Figur mit verschiedenen Farben; . gehört nicht dazu.
............... ............... x..x........... xxxx........... xxxxaaaaaaa... .xx.aaaaaaaaa.. ....aaaaaaa.aa. ....ll...ll.... ....vv...vv.... ...............
Vor dem Kauf läuft ein Bulle durch den Laden und zerbricht die Figur sowie viele andere Glasgegenstände in den Regalen! Die Figur zerbricht in 3 Teile, die unter $K$ Teilen am Boden verschwinden ($4 \leq K \leq 100$). Jedes der $K$ Teile ist wie das Original durch ein Zeichengitter beschrieben.
Bestimme die Anzahl Mengen von 3 Teilen aus den $K$, die sich zur ursprünglichen Figur zusammenkleben lassen.
Die Teile können vertikal oder horizontal gespiegelt oder um Vielfache von 90 Grad gedreht sein. Suche anhand des Originals und der $K$ Gitter Mengen von 3 Teilen, die mit Verschiebungen, Spiegelungen und Drehungen um Vielfache von 90 Grad das Original bilden. Übereinandergelegt müssen die 3 Teile exakt das Original bilden, wobei jedes farbige Quadrat in genau einem Teil vorkommt.
Eingabe
Die erste Zeile enthält $K$. Danach folgen $K + 1$ Beschreibungen: zuerst das Original, dann die $K$ Bruchstücke.
Jede Beschreibung beginnt mit $R$ und $C$ ($1 \le R, C \le 100$). Die folgenden $R$ Zeilen enthalten jeweils $C$ Kleinbuchstaben für die Farben. Jedes Teil ist über horizontale oder vertikale Nachbarschaft zusammenhängend und hat mindestens eine nichtleere Zelle.
Ausgabe
Gib die Anzahl Tripel $i, j, k$ ($i < j < k$) aus, deren Teile $i$, $j$ und $k$ das Original bilden können.
Beispiele
Eingabe 1
5 5 5 aaaaa ..a.. bbabb ..a.. aaaaa 3 5 ..abb ..a.. aaaaa 5 2 a. a. aa a. a. 1 2 bb 1 5 bbabb 2 5 aaaaa ..a..
Ausgabe 1
3
Hinweis
Die drei Lösungen verwenden $(0, 1, 2)$, $(0, 2, 4)$ und $(1, 3, 4)$.
Das Zeitlimit beträgt 6 Sekunden pro Testfall, für Java und Python das Doppelte.
Aufgabenautor: Brian Dean