Farmer John quyết định rằng ngôi nhà của ông cần được trang trí thêm. Khi ghé thăm cửa hàng đồ sứ địa phương, ông tìm thấy một bức tượng bò bằng thủy tinh tinh xảo và quyết định mua nó vì biết rằng nó sẽ vừa khít trên bệ phía trên lò sưởi.

Hình dạng của bức tượng bò được mô tả bằng một lưới ký tự kích thước \(N \times M\) như dưới đây (\(3 \leq N, M \leq 500\)), trong đó mỗi ký tự là chữ cái thường thuộc về bức tượng (các chữ cái khác nhau biểu thị các màu khác nhau), còn ký tự . thì không.

...............
...............
x..x...........
xxxx...........
xxxxaaaaaaa...
.xx.aaaaaaaaa..
....aaaaaaa.aa.
....ll...ll....
....vv...vv....
...............

Không may, ngay trước khi FJ kịp mua, một con bò đực chạy xuyên qua cửa hàng và làm vỡ không chỉ bức tượng của FJ mà còn nhiều đồ vật bằng thủy tinh khác trên các kệ! Bức tượng của FJ vỡ thành \(3\) mảnh, rồi nhanh chóng bị lẫn vào tổng cộng \(K\) mảnh nằm trên sàn (\(4 \leq K \leq 100\)). Mỗi mảnh trong số \(K\) mảnh được mô tả bằng một lưới ký tự, giống như bức tượng ban đầu.

Hãy giúp FJ xác định có bao nhiêu bộ gồm \(3\) mảnh (trong số \(K\) mảnh trên sàn) có thể được dán lại với nhau để phục hồi bức tượng bị vỡ.

Các mảnh trên sàn có thể đã bị lật theo chiều dọc hoặc chiều ngang, hoặc xoay một bội số nào đó của \(90\) độ. Do đó, với lưới ban đầu cùng \(K\) lưới mô tả các mảnh, cần tìm các bộ gồm \(3\) mảnh có thể ghép lại để tạo thành hình ban đầu; được phép tịnh tiến, lật hoặc xoay các mảnh theo các bội số của \(90\) độ. Khi chồng lên nhau, \(3\) mảnh phải tạo thành chính xác hình ban đầu, và mỗi ô có màu trong hình ban đầu phải được biểu diễn trong đúng một mảnh.

Dữ liệu vào

Dòng đầu tiên chứa một số nguyên \(K\). Tiếp theo là \(K + 1\) phần mô tả mảnh. Phần mô tả đầu tiên là bức tượng bò bằng thủy tinh ban đầu, còn \(K\) phần mô tả sau là các mảnh vỡ.

Mỗi phần mô tả bắt đầu bằng một dòng chứa hai số nguyên \(R\) và \(C\) (\(1 \leq R, C \leq 100\)). \(R\) dòng tiếp theo chứa \(C\) ký tự chữ cái thường mô tả màu của mỗi ô. Mỗi mảnh liên thông theo chiều ngang/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\)) sao cho các mảnh \(i\), \(j\) và \(k\) có thể được sắp xếp để tạo thành bức tượng bò bằng thủy tinh ban đầu.

Ví dụ

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..

3

Lưu ý rằng bài này có giới hạn thời gian là \(6\) giây cho mỗi test (và gấp đôi thời gian đó đối với bài nộp bằng Java và Python).

Nguồn

USACO 2016 US Open Contest, Platinum - Bull in a China Shop: https://usaco.org/index.php?page=viewproblem2&cpid=649

Tác giả: Brian Dean.