قرر 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