Бик у порцеляновій крамниці (Платина)#10578
Фермер Джон вирішив, що його будинку бракує прикрас. Відвідуючи місцевий магазин порцеляни, він знайшов вишукану скляну фігурку корови і вирішив купити її, знаючи, що вона ідеально підійде для камінної полиці над його каміном.
Форма фігурки корови описується за допомогою сітки символів розміром n \times m~(3 \le n, m \le 500), подібної до показаної нижче. Малі літери позначають клітинки, які є частиною фігурки, причому різні літери відповідають різним кольорам, а символи '' позначають порожні клітинки.
...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa...
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............На жаль, якраз перед тим, як FJ встиг здійснити покупку, бик пробіг через магазин і розбив не тільки фігурку FJ, а й багато інших скляних предметів з полиць! Фігурка FJ розбилася на частини, які невдовзі перемішалися з різними частинами, що лежали на підлозі. Кожна з частин описується сіткою символів, подібною до вихідної фігурки.
Допоможіть FJ визначити, скільки наборів із частин, обраних серед частин на підлозі, можна склеїти назад, щоб відновити його розбиту фігурку.
Частини на підлозі могли бути перевернуті горизонтально або вертикально, а також повернуті на будь-який кут, кратний градусам. Маючи вихідну сітку та сіток, що описують частини, необхідно знайти всі набори з частин, які можна з'єднати так, щоб отримати вихідне зображення. Частини можна переміщувати, перевертати горизонтально або вертикально та повертати на будь-який кут, кратний градусам.
Після накладання трьох частин вони повинні в точності утворювати вихідне зображення: кожна кольорова клітинка вихідного зображення повинна бути представлена рівно в одній із трьох частин, без пропущених або перекритих клітинок.
У першому рядку міститься одне ціле число k~(4 \le k \le 100). Далі йдуть k + 1 описів частин. Перший опис відповідає вихідній скляній фігурці корови, а наступні описів відповідають розбитим частинам.
Кожен опис починається з рядка, що містить два цілих числа і c~(1 \le r, c \le 100). Наступні рядків містять по малих літер англійського алфавіту, що описують колір кожної клітинки. Кожна частина є зв'язною по горизонталі та вертикалі і містить хоча б одну непорожню клітинку.
Виведіть кількість трійок i, j, k~(i \lt j \lt k), таких що частини і можна розташувати так, щоб вони утворили вихідну скляну фігурку корови.
Існують три розв'язки, що використовують такі набори частин: (0, 1, 2), (0, 2, 4) та (1, 3, 4).
Приклад 1