本题解中方格图采用 \(0\)-索引。
注意到大写英文字母共 \(26\) 个，可以状压为一个 int 存储。
首先考虑解决 \(q=1\) 的问题。
设 \(fv_{i,j}\) 表示以 \((i,j)\) 为右下角的同色楼梯的最大高度，\(fs_{i,j}\) 表示 \(fv_{i,j}\) 对应的楼梯包含的字母集合。
则边界情况为 \(fv_{i,0}=fv_{0,j}=1\)，\(fs_{i,0}=\{a_{i,0}\}\)，\(fs_{0,j}=\{a_{0,j}\}\)。
对于 \(i>0\) 且 \(j>0\)，考虑用以 \((i-1,j)\) 和 \((i,j-1)\) 为右下角的楼梯拼出以 \((i,j)\) 为右下角的楼梯，有两种情况：
- 若 \(\operatorname{card}(fs_{i-1,j}\cup fs_{i,j-1}\cup \{a_{i,j}\})\le 1\)，此时可以拼成一个大的同色楼梯，有 \(fv_{i,j}=\min\{fv_{i-1,j},fv_{i,j-1}\}+1\)，\(fs_{i,j}=fs_{i-1,j}\cup fs_{i,j-1}\cup \{a_{i,j}\}\)。
- 若 \(\operatorname{card}(fs_{i-1,j}\cup fs_{i,j-1}\cup \{a_{i,j}\}) > 1\)，此时无法拼成大的同色楼梯，有 \(fv_{i,j}=1\)，\(fs_{i,j}=\{a_{i,j}\}\)。
设 \(fc_z\) 表示高度为 \(i\) 的同色楼梯数量，则 \(fc_z=\sum\limits_{i}\sum\limits_{j}[fs_{i,j}\ge z]\)。
再考虑用类似方法求出 \(q=2\) 的答案。
双色楼梯数量不好求，考虑容斥。设 \(gv_{i,j}\) 表示以 \((i,j)\) 为右下角的至多双色楼梯数量，\(gs_{i,j}\) 表示 \(gv_{i,j}\) 对应的楼梯包含的字母集合。
边界情况依然为 \(gv_{i,0}=gv_{0,j}=1\)，\(gs_{i,0}=\{a_{i,0}\}\)，\(gs_{0,j}=\{a_{0,j}\}\)。
对于 \(i>0\) 且 \(j>0\)，首先有 \(gv_{i,j}=fv_{i,j}\)，\(gs_{i,j}=fs_{i,j}\)，再考虑多出的情况。
多出的情况无非是考虑以 \((i-1,j)\) 和 \((i,j-1)\) 为右下角的楼梯是同色的还是双色的，我们对于每种情况都进行更新：
- 若 \(\operatorname{card}(fs_{i-1,j}\cup fs_{i,j-1}\cup \{a_{i,j}\})\le 2\)，有 \(gv_{i,j}\gets\min\{fv_{i-1,j},fv_{i,j-1}\}+1\)，\(gs_{i,j}\gets fs_{i-1,j}\cup fs_{i,j-1}\cup \{a_{i,j}\}\)。
- 若 \(\operatorname{card}(gs_{i-1,j}\cup fs_{i,j-1}\cup \{a_{i,j}\})\le 2\)，有 \(gv_{i,j}\gets\min\{gv_{i-1,j},fv_{i,j-1}\}+1\)，\(gs_{i,j}\gets gs_{i-1,j}\cup fs_{i,j-1}\cup \{a_{i,j}\}\)。
- 若 \(\operatorname{card}(fs_{i-1,j}\cup gs_{i,j-1}\cup \{a_{i,j}\})\le 2\)，有 \(gv_{i,j}\gets\min\{fv_{i-1,j},gv_{i,j-1}\}+1\)，\(gs_{i,j}\gets fs_{i-1,j}\cup gs_{i,j-1}\cup \{a_{i,j}\}\)。
- 若 \(\operatorname{card}(gs_{i-1,j}\cup gs_{i,j-1}\cup \{a_{i,j}\})\le 2\)，有 \(gv_{i,j}\gets\min\{gv_{i-1,j},gv_{i,j-1}\}+1\)，\(gs_{i,j}\gets gs_{i-1,j}\cup gs_{i,j-1}\cup \{a_{i,j}\}\)。
其中 \(\gets\) 符号表示更新过程，也就是如果 \(\min\{\cdot,\cdot\}+1 > gv_{i,j}\)，就同时更新 \(gv_{i,j}\) 和 \(gs_{i,j}\)，否则两者都不更新。
设 \(gc_z\) 表示高度为 \(i\) 的至多双色楼梯数量，则 \(gc_z=\sum\limits_{i}\sum\limits_{j}[gs_{i,j}\ge z]\)。双色楼梯数量即为 \(gc_z-fc_z\)。
时间复杂度 \(O(nm)\)，代码中的 \(n,m\) 好像跟题面是反的。
// Problem: P15348 [TOIP 2025] 同色楼梯和双色楼梯
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P15348
// Memory Limit: 512 MB
// Time Limit: 400000 ms
//
// Powered by CP Editor (https://cpeditor.org)//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {uniform_int_distribution<int> dist(L, R);return dist(rnd);
}template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}template<int mod>
inline unsigned int down(unsigned int x) {return x >= mod ? x - mod : x;
}template<int mod>
struct Modint {unsigned int x;Modint() = default;Modint(unsigned int x) : x(x) {}friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}friend Modint operator/(Modint a, Modint b) {return a * ~b;}friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}friend Modint operator~(Modint a) {return a ^ (mod - 2);}friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}friend Modint& operator++(Modint& a) {return a += 1;}friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}friend Modint& operator--(Modint& a) {return a -= 1;}friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}friend bool operator==(Modint a, Modint b) {return a.x == b.x;}friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};const int N = 4e3 + 5;int n, m, c, fv[N][N], fs[N][N], gv[N][N], gs[N][N], fc[N], gc[N];
string s[N];int main() {ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);cin >> n >> m;rep(i, 0, n - 1) cin >> s[i];rep(i, 0, n - 1) {rep(j, 0, m - 1) {int u = 1 << (s[i][j] - 'A');if(i == 0 || j == 0) {fv[i][j] = 1;fs[i][j] = u;gv[i][j] = 1;gs[i][j] = u;}else {if(__builtin_popcount(fs[i - 1][j] | fs[i][j - 1] | u) <= 1) {fv[i][j] = min(fv[i - 1][j], fv[i][j - 1]) + 1;fs[i][j] = u;gv[i][j] = min(fv[i - 1][j], fv[i][j - 1]) + 1;gs[i][j] = u;}else {fv[i][j] = 1;fs[i][j] = u;gv[i][j] = 1;gs[i][j] = u;}if(__builtin_popcount(fs[i - 1][j] | fs[i][j - 1] | u) <= 2) {if(min(fv[i - 1][j], fv[i][j - 1]) + 1 > gv[i][j]) {gv[i][j] = min(fv[i - 1][j], fv[i][j - 1]) + 1;gs[i][j] = fs[i - 1][j] | fs[i][j - 1] | u;}}if(__builtin_popcount(gs[i - 1][j] | fs[i][j - 1] | u) <= 2) {if(min(gv[i - 1][j], fv[i][j - 1]) + 1 > gv[i][j]) {gv[i][j] = min(gv[i - 1][j], fv[i][j - 1]) + 1;gs[i][j] = gs[i - 1][j] | fs[i][j - 1] | u;}}if(__builtin_popcount(fs[i - 1][j] | gs[i][j - 1] | u) <= 2) {if(min(fv[i - 1][j], gv[i][j - 1]) + 1 > gv[i][j]) {gv[i][j] = min(fv[i - 1][j], gv[i][j - 1]) + 1;gs[i][j] = fs[i - 1][j] | gs[i][j - 1] | u;}}if(__builtin_popcount(gs[i - 1][j] | gs[i][j - 1] | u) <= 2) {if(min(gv[i - 1][j], gv[i][j - 1]) + 1 > gv[i][j]) {gv[i][j] = min(gv[i - 1][j], gv[i][j - 1]) + 1;gs[i][j] = gs[i - 1][j] | gs[i][j - 1] | u;}}}++fc[fv[i][j]];++gc[gv[i][j]];}}rep(i, 2, n) {rep(j, 1, i - 1) {fc[j] += fc[i];gc[j] += gc[i];}}cin >> c;if(c == 1) {int ans = 0;rep(i, 1, n) if(fc[i] > 0) ans = i;cout << ans << endl;rep(i, 1, ans) cout << fc[i] << " \n"[i == ans];}else {int ans = 0;rep(i, 1, n) if(gc[i] - fc[i] > 0) ans = i;cout << ans << endl;rep(i, 1, ans) cout << gc[i] - fc[i] << " \n"[i == ans];}return 0;
}