Farmer John quiere decorar más su casa. En una tienda de porcelana encuentra una delicada figura de vaca de vidrio y decide comprarla para la repisa sobre la chimenea.
Su forma es una cuadrícula de $N \times M$ caracteres ($3 \leq N, M \leq 500$), como abajo. Las minúsculas son partes de distintos colores de la figura; los . no lo son.
............... ............... x..x........... xxxx........... xxxxaaaaaaa... .xx.aaaaaaaaa.. ....aaaaaaa.aa. ....ll...ll.... ....vv...vv.... ...............
Antes de comprarla, un toro atraviesa la tienda y rompe la figura y muchos objetos de vidrio de las estanterías. La figura queda en 3 piezas, perdidas entre $K$ piezas en el suelo ($4 \leq K \leq 100$). Cada una de las $K$ piezas se describe con una cuadrícula como la original.
Cuenta los conjuntos de 3 piezas de entre las $K$ que se pueden pegar para reconstruir la figura.
Las piezas pueden estar volteadas vertical u horizontalmente o rotadas un múltiplo de 90 grados. Con la original y las $K$ cuadrículas, busca conjuntos de 3 que formen la imagen permitiendo traslaciones, volteos y rotaciones múltiplos de 90 grados. Superpuestas, deben formar exactamente la original, y cada casilla coloreada debe estar representada en exactamente una pieza.
Entrada
La primera línea contiene $K$. Siguen $K + 1$ descripciones: la primera es la figura original y las siguientes $K$ las piezas.
Cada descripción empieza con $R$ y $C$ ($1 \le R, C \le 100$). Las siguientes $R$ líneas contienen $C$ minúsculas que describen los colores. Cada pieza es conexa por adyacencia horizontal o vertical y tiene al menos una casilla no vacía.
Salida
Imprime el número de ternas $i, j, k$ ($i < j < k$) para las que las piezas $i$, $j$ y $k$ forman la vaca original.
Ejemplos
Entrada 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..
Salida 1
3
Nota
Las tres soluciones usan $(0, 1, 2)$, $(0, 2, 4)$ y $(1, 3, 4)$.
El límite de tiempo es de 6 segundos por caso de prueba, y el doble para Java y Python.
Autor: Brian Dean