Farmer John은 집을 더 꾸미기로 했습니다. 도자기 가게에서 섬세한 유리 소 조각상을 발견하고 벽난로 위 선반에 딱 맞아 사기로 합니다.
모양은 다음과 같은 $N \times M$ 문자 격자입니다($3 \leq N, M \leq 500$). 소문자는 다른 색의 조각상 부분이며 .는 조각상에 포함되지 않습니다.
............... ............... x..x........... xxxx........... xxxxaaaaaaa... .xx.aaaaaaaaa.. ....aaaaaaa.aa. ....ll...ll.... ....vv...vv.... ...............
구매 직전 황소가 가게를 지나가 조각상과 선반의 다른 유리 제품도 많이 깨뜨렸습니다! 조각상은 3조각으로 깨져 바닥의 총 $K$조각에 섞였습니다($4 \leq K \leq 100$). $K$개의 각 조각도 원래 조각상처럼 문자 격자로 표현됩니다.
바닥의 $K$조각 중 3조각을 골라 붙여 원래 조각상을 복구할 수 있는 집합 수를 구하세요.
조각은 상하나 좌우로 뒤집히거나 90도의 배수만큼 회전되었을 수 있습니다. 원래 격자와 $K$개의 조각 격자로부터 평행 이동, 뒤집기, 90도 배수 회전을 허용하여 원래 그림을 만드는 3조각 집합을 찾으세요. 겹쳐 놓은 3조각은 원래 그림을 정확히 만들고, 원래의 각 색칠된 칸은 정확히 한 조각에 있어야 합니다.
입력
첫 줄에는 $K$가 주어집니다. 다음에 $K + 1$개의 설명이 있으며 첫째는 원래 조각상, 다음 $K$개는 깨진 조각입니다.
각 설명은 정수 $R$과 $C$로 시작합니다($1 \le R, C \le 100$). 다음 $R$개 줄에는 색을 나타내는 소문자 $C$개가 있습니다. 각 조각은 상하좌우 인접으로 연결되며 비어 있지 않은 칸이 적어도 하나 있습니다.
출력
조각 $i$, $j$, $k$로 원래 소를 만들 수 있는 삼중쌍 $i, j, k$($i < j < k$)의 개수를 출력하세요.
예제
입력 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..
출력 1
3
참고
세 해는 $(0, 1, 2)$, $(0, 2, 4)$, $(1, 3, 4)$를 사용합니다.
각 테스트 케이스 시간 제한은 6초이며 Java와 Python 제출은 그 두 배입니다.
문제 작성: Brian Dean