题目描述

Jakov 写了一首诗，由 $n$ 句 $n/4$ 段组成。第 $1\sim 4$ 句为第一段，$5\sim 8$ 句为第二段，以此类推。诗的每句由 $m$ 个单词组成。

我们称两个句子是押韵的，当且仅当这两句话的最后一个单词的最后 $k$ 个字母相同。特别地，若某句中最后一个单词不足 $k$ 个字母，认为这两句不押韵。

已知每段有三种押韵的模式：

• $\text{AABB}$：一二句押韵，三四句押韵；
• $\text{ABAB}$：一三句押韵，二四句押韵；
• $\text{ABBA}$：一四句押韵，二三句押韵。

请统计出这三种押韵模式在诗中出现的次数。

输入格式

第一行，三个正整数 $n,m,k$（$1\le n\le 500$ 且 $n$ 是 $4$ 的倍数，$1\le m,k\le 20$）。

接下来 $n$ 行，第 $i$ 行表示第 $i$ 句。每句中 $m$ 个单词，每个单词由至多 $20$ 个小写英文字母组成。

输出格式

输出一行三个整数：$\text{AABB},\text{ABAB},\text{ABBA}$ 押韵模式的出现次数。

输入输出样例 #1

输入 #1

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

输出 #1

0 0 1

输入输出样例 #2

输入 #2

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

输出 #2

0 2 0

输入输出样例 #3

输入 #3

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

输出 #3

1 1 1

说明/提示

样例解释

样例一解释：第一段不押韵，因为 $k=3$，但是最后一个单词只有 $2$ 个字母。第二段押 $\text{ABBA}$ 韵（一四句：$\texttt{aaaaa\underline{ahh}},\texttt{kld\underline{ahh}}$；二三句：$\texttt{\underline{wer}},\texttt{po\underline{wer}}$）。综上，输出 $\texttt{0 0 1}$。

样例三解释：在唯一的一段中，每句的最后一个单词的最后 $2$ 个字母都是 $\texttt{ka}$。根据定义，符合全部的三种押韵模式。

子任务

• $\text{Subtask 1 (15 pts)}$：$n=4$。
• $\text{Subtask 2 (15 pts)}$：每个单词仅由一个字母组成。
• $\text{Subtask 3 (20 pts)}$：无额外限制。