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$ осколков описан сеткой, как исходная фигурка.
Найдите число наборов из 3 осколков среди $K$, которые можно склеить в исходную фигурку.
Осколки могли быть перевёрнуты по вертикали или горизонтали и повёрнуты на угол, кратный 90 градусам. По исходной сетке и $K$ сеткам найдите наборы из 3 частей, восстанавливающие рисунок с помощью переносов, отражений и поворотов на кратные 90 градусам углы. После наложения части должны точно образовать исходную картинку, причём каждая цветная клетка должна принадлежать ровно одной части.
Входные данные
Первая строка содержит целое число $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