Trong giờ Ngữ văn Croatia, Jakov đọc một bài thơ gồm \(n\) dòng và \(n/4\) khổ. Bốn dòng liên tiếp tạo thành một khổ; mỗi dòng có đúng \(m\) từ.

Hai dòng vần khi \(k\) chữ cái cuối của từ cuối cùng của chúng trùng nhau. Nếu một từ cuối có ít hơn \(k\) chữ cái thì hai dòng không vần. Một khổ có thể có các sơ đồ vần sau:

• AABB: dòng 1 vần dòng 2, dòng 3 vần dòng 4;
• ABAB: dòng 1 vần dòng 3, dòng 2 vần dòng 4;
• ABBA: dòng 1 vần dòng 4, dòng 2 vần dòng 3.

Hãy đếm số khổ có từng sơ đồ vần. Một khổ có thể thỏa nhiều sơ đồ vần.

Dữ liệu vào

Dòng đầu chứa \(n,m,k\) (\(1\le n\le500\), \(n\) chia hết cho \(4\), \(1\le m,k\le20\)). \(n\) dòng tiếp theo, mỗi dòng gồm \(m\) từ; mỗi từ có không quá \(20\) chữ cái thường tiếng Anh.

Dữ liệu ra

In ba số: số khổ có vần AABB, ABAB, ABBA, theo thứ tự đó.

Ràng buộc

Các giới hạn chính thức của dữ liệu được nêu đầy đủ trong phần Dữ liệu vào.

Phân nhóm

1. \(15\) điểm: \(n=4\).
2. \(15\) điểm: mọi từ chỉ có một ký tự.
3. \(20\) điểm: không có ràng buộc thêm.

Ví dụ

8 2 3
aa bb
cc bb
dd ee
ff ee
auu aaaaaahh
auu wer
asdf power
lol kldahh

0 0 1

8 2 2
ja programiram
mjesec listopad
ponekad chillam
voda vodopad
banana jabuka
fiziku znam
teska odluka
njam njam

0 2 0

4 4 2
pas konj zec macka
trokut teziste poluravnina tocka
nogomet tenis ragbi odbojka
sir mlijeko kulen sunka

1 1 1

Nguồn

COCI 2025/2026 - Vòng 1, bài Rima.

Đề bài, dữ liệu kiểm thử và lời giải tham khảo được lấy từ nguồn chính thức của Croatian Open Competition in Informatics.