Farmer John muốn trang trí nhà thêm. Tại cửa hàng đồ sứ, ông thấy tượng bò bằng kính tinh xảo và quyết định mua vì nó vừa vặn trên kệ phía trên lò sưởi.
Hình tượng là lưới $N \times M$ ký tự ($3 \leq N, M \leq 500$), như dưới. Chữ thường là phần của tượng với màu khác nhau, còn . không thuộc tượng.
............... ............... x..x........... xxxx........... xxxxaaaaaaa... .xx.aaaaaaaaa.. ....aaaaaaa.aa. ....ll...ll.... ....vv...vv.... ...............
Ngay trước khi mua, một con bò đực chạy qua cửa hàng, làm vỡ tượng và nhiều đồ kính khác trên kệ! Tượng vỡ thành 3 mảnh, lẫn trong tổng $K$ mảnh trên sàn ($4 \leq K \leq 100$). Mỗi mảnh trong $K$ mảnh được mô tả bằng lưới như tượng gốc.
Đếm số bộ 3 mảnh trong $K$ mảnh có thể dán lại thành tượng gốc.
Mảnh có thể bị lật dọc hoặc ngang, hoặc xoay bội số của 90 độ. Cho lưới gốc và $K$ lưới mảnh, tìm các bộ 3 tạo được hình gốc, cho phép tịnh tiến, lật hoặc xoay bội số 90 độ. Khi chồng lại, 3 mảnh phải tạo đúng hình gốc, mỗi ô có màu của gốc thuộc đúng một mảnh.
Dữ liệu vào
Dòng đầu chứa $K$. Tiếp theo có $K + 1$ mô tả: đầu là tượng gốc, $K$ mô tả sau là các mảnh.
Mỗi mô tả bắt đầu bằng $R$ và $C$ ($1 \le R, C \le 100$). $R$ dòng tiếp theo chứa $C$ chữ thường mô tả màu. Mỗi mảnh liên thông theo kề ngang hoặc dọc và có ít nhất một ô không rỗng.
Dữ liệu ra
In số bộ ba $i, j, k$ ($i < j < k$) mà các mảnh $i$, $j$, $k$ có thể ghép thành bò gốc.
Ví dụ
Dữ liệu vào 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..
Dữ liệu ra 1
3
Ghi chú
Ba lời giải dùng $(0, 1, 2)$, $(0, 2, 4)$, $(1, 3, 4)$.
Giới hạn thời gian là 6 giây mỗi trường hợp kiểm tra, gấp đôi cho bài nộp Java và Python.
Tác giả: Brian Dean