Farmer John vuole decorare meglio la casa. In un negozio di porcellane trova una delicata statuetta di mucca in vetro e decide di comprarla per la mensola sopra il camino.
La forma è una griglia di $N \times M$ caratteri ($3 \leq N, M \leq 500$), come sotto. Le minuscole sono parti della statuetta di colori diversi; i . non ne fanno parte.
............... ............... x..x........... xxxx........... xxxxaaaaaaa... .xx.aaaaaaaaa.. ....aaaaaaa.aa. ....ll...ll.... ....vv...vv.... ...............
Prima dell’acquisto un toro attraversa il negozio, rompendo la statuetta e molti altri oggetti di vetro sugli scaffali! La statuetta si rompe in 3 pezzi, persi tra $K$ pezzi sul pavimento ($4 \leq K \leq 100$). Ciascuno dei $K$ pezzi è descritto da una griglia come l’originale.
Conta gli insiemi di 3 pezzi tra i $K$ che si possono incollare per ricostruire la statuetta.
I pezzi possono essere ribaltati verticalmente o orizzontalmente o ruotati di multipli di 90 gradi. Con l’originale e le $K$ griglie, cerca insiemi di 3 pezzi che formino l’immagine, consentendo traslazioni, ribaltamenti e rotazioni di multipli di 90 gradi. Sovrapposti, i 3 pezzi devono formare esattamente l’originale, con ogni casella colorata presente in esattamente un pezzo.
Input
La prima riga contiene $K$. Seguono $K + 1$ descrizioni: la prima è la statuetta originale e le successive $K$ sono i pezzi.
Ogni descrizione inizia con $R$ e $C$ ($1 \le R, C \le 100$). Le successive $R$ righe contengono $C$ minuscole che descrivono i colori. Ogni pezzo è connesso tramite adiacenze orizzontali o verticali e ha almeno una casella non vuota.
Output
Stampa il numero di triple $i, j, k$ ($i < j < k$) per cui i pezzi $i$, $j$ e $k$ formano la mucca originale.
Esempi
Input 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..
Output 1
3
Spiegazione
Le tre soluzioni usano $(0, 1, 2)$, $(0, 2, 4)$ e $(1, 3, 4)$.
Il limite di tempo è di 6 secondi per caso di test, e il doppio per Java e Python.
Autore: Brian Dean