Бик у посудній лавці (Платина)
Фермер Джон вирішив, що його дім потребує більшого оздоблення. Відвідавши місцеву крамницю посуду, він знаходить тонку скляну статуетку корови, яку вирішує купити, знаючи, що вона ідеально поміститься на полиці над його каміном.
Форма фігурки корови описується сіткою розміром 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).