說明

在一個 $m\times n$ 的方格圖中，每一格都有恰一種顏色，我們用大寫英文字母代表每種顏色。

所謂的「樓梯」是指：連續的某些直行的區段，這些區段的底部位置（下方所在的列）必須是一樣的，而高度則是自左而右逐步加一。注意，一個樓梯圖形的高度與寬度必然是相等的。

所謂的「同色樓梯」是指：一個樓梯其中所涵蓋方格的顏色皆相同。

所謂的「雙色樓梯」是指：一個樓梯其中所涵蓋方格的顏色有恰兩種。

按照以下的範例圖形中，藍色、黃色與綠色分別是寬度（高度）為 $2$、$3$ 與 $4$ 的「同色樓梯」。請注意，樓梯與樓梯可能重疊，例如藍色 C 樓梯旁還有一個C樓梯。此外，大樓梯中必然有小樓梯，例如下圖中寬度 $3$ 的 B 樓梯中有 $3$ 個寬度 $2$ 的樓梯。寬度 $4$ 的 A 樓梯中則含有 $3$ 個寬度 $3$ 的樓梯以及 $6$ 個寬度 $2$ 的樓梯。

:::align{center} :::

以下的範例圖形中，有標註出所有「雙色樓梯」。

:::align{center} :::

你的任務是算出所有寬度（高度）的同色樓梯或雙色樓梯分別有幾個。

输入格式

$$\begin{aligned} &m \; n \\ &a_{1,1} a_{1,2} a_{1,3} \cdots a_{1,n} \\ &a_{2,1} a_{2,2} a_{2,3} \cdots a_{2,n} \\ &a_{3,1} a_{3,2} a_{3,3} \cdots a_{3,n} \\ &\vdots \\ &a_{m,1} a_{m,2} a_{m,3} \cdots a_{m,n} \\ &q \end{aligned}$$

• $m$、$n$ 分別代表區域高度、區域寬度。
• $a_{i,j}$ 代表該區域的顏色。
• 若 $q=1$ 代表詢問同色樓梯數量。若 $q=2$ 代表詢問雙色樓梯數量。

输出格式

$$\begin{aligned} &k \\ &s_1 \; s_2 \; s_3 \; \cdots \; s_k \end{aligned}$$

• $k$ 為一非負整數，代表寬度（高度）最大的同色樓梯（雙色樓梯）的寬度（高度）。
• $s_i$ 皆為非負整數，代表寬度（高度）為 $i$ 的同色樓梯（雙色樓梯）數量。
• 若 $k = 0$，第二行輸出一空行。

6 8
BCCDDAAA
CCCBBBAB
DDDAAAAB
EBBEAAAA
EBBAAAAA
BBBBABCD
1

4
48 12 4 1

3 3
BCC
CCC
DDD
1

2
9 2

3 3
BCC
CCC
DDD
2

3
0 2 1

提示

測資限制

• $1 \le m \le 4000$。
• $1 \le n \le 4000$。
• $a_{i,j}$ 為大寫英文字母。
• $m$ 和 $n$ 皆為整數。
• $q \in \{1,2\}$。

評分說明

本題共有五組子任務，條件限制如下所示。每一組可有一或多筆測試資料，該組所有測試資料皆需答對才會獲得該組分數。

子任務	分數	額外輸入限制
1	5	$q=1$，所有 $a_{i,j}$ 相同。
2	9	$q=1$，$m \le 200$, $n \le 200$。
3	22	$q=1$，$m \le 200$。
4	33	$q=1$。
5	31	$q=2$。