Фермер Джон решил украсить свой дом. Посетив китайский магазинчик, он нашёл стеклянную фигурку коровы и решил её купить.
Форма коровы описывается решёткой из \(N \times M\) (\(3 \leq N, M \leq 500\)) символов (на рисунке ниже приведён пример). Различные символы (маленькие латинские) обозначают различные цвета, а символ '.' - отсутствие фигуры.
...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa....
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............
К несчастью до покупки в магазинчик ворвался бык, всё разгромил и сломал фигурку ФД на три части, которые затерялись на полу среди \(K\) (\(4 \leq K \leq 100\)) других кусков на полу. Каждый из \(K\) кусков на полу описывается аналогично тому как это сделано выше.
Помогите ФД определить сколько наборов из 3 кусков (из \(K\) валяющихся на полу) могут составить сломанную фигуру.
Куски на полу могут перемещаться горизонтально и вертикально, переворачиваться горизонтально и вертикально, а также поворачиваться на количество градусов, кратное 90. Они должны составить точно исходную фигурку — каждая позиция должна быть представлена ровно одним куском.
ФОРМАТ ВВОДА:
Первая строка содержит одно целое число \(K\). Далее идут \(K + 1\) описаний. Первое описывает оригинальную фигурку, остальные \(K\) - описание кусков на полу.
Каждое описание начинается со строки, содержащей два целых числа \(R\) и \(C\) (\(1 \le R, C \le 100\)). Последующие \(R\) строк содержат по \(C\) маленьких латинских символов, описывающих цвет каждой ячейки. Каждый кусок соединяется горизонтально или вертикально и имеет хотя бы одну не-пустую ячейку.
ФОРМАТ ВЫВОДА:
Выведите количество триплетов \(i, j, k\) (\(i < j < k\)) таких, что куски \(i\), \(j\), и \(k\) могут составить исходную фигурку коровы.
ПРИМЕР ВВОДА:
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..
ПРИМЕР ВЫВОДА:
3
Эти три решения используют куски \((0, 1, 2)\), \((0, 2, 4)\), \((1, 3, 4)\). Заметим, что эта задача имеет 6 секунд на тест (а для Питона и Java - 12)
| № | Входные данные | Выходные данные |
|
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..
|
3
|