Бык в посудной лавке (Платина)
Фермер Джон решил, что его дом нуждается в большем украшении. Посетив местную посудную лавку, он находит тонкую стеклянную статуэтку коровы, которую решает купить, зная, что она идеально поместится на полке над его камином.
Форма фигурки коровы описывается сеткой n * m (3 ≤ n, m ≤ 500) таких символов, как тот, что ниже, где символы строчных букв являются частью фигурки (обозначающие разные цвета), а символы '.' - нет.
............... ............... x..x........... xxxx........... xxxxaaaaaaa... .xx.aaaaaaaaa.. ....aaaaaaa.aa. ....ll...ll.... ....vv...vv.... ...............
К сожалению, прямо перед тем, как ФД успевает сделать покупку, через магазин пробегает бык и разбивает не только статуэтку ФД, но и многие другие стеклянные предметы на полках! Фигурка ФД распадается на 3 части, которые быстро теряются среди k частей, лежащих на земле. Каждая из k частей описывается сеткой символов, как и оригинальная фигурка.
Пожалуйста, помогите ФД определить, сколько комплектов из 3 деталей (из k на полу) можно склеить вместе, чтобы починить его сломанную фигурку.
Кусочки на земле могли быть перевернуты вертикально или горизонтально, или повернуты кратно на 90 градусов. Следовательно, учитывая исходную сетку, а также k сеток, описывающих части, Вы хотите найти наборы из 3 частей, которые можно соединить вместе чтобы сформировать исходную картинку, при этом части разрешается перемещать, переворачивать и поворачивать на 90 градусов. При наложении друг на друга 3 части должны точно формировать исходную картинку, при этом каждый цветной квадрат в исходной картинке представлен ровно одной из частей.
Входные данные
Первая строка содержит одно целое число k (4 ≤ k ≤ 100). После этого идут k + 1 описаний кусков. Первое описание задает оригинальную стеклянную корову, следующие k описаний задают разбитые осколки.
Каждое описание начинается со строки, содержащей два целых числа r и c (1 ≤ r, c ≤ 100). Следующие r строк содержат c строчных букв алфавита, описывающие цвет каждой ячейки. Каждая часть будет соединена по горизонтали/вертикали и должна иметь хотя бы одну непустую ячейку.
Выходные данные
Выведите количество троек i, j, k (i < j < k) таких, что куски i, j и k можно расположить так, чтобы получилась оригинальная стеклянная корова.
Пример
Три решения используют детали (0, 1, 2), (0, 2, 4), (1, 3, 4).