#include <iostream> #include <vector> #include <algorithm> using namespace std; const int N = 35; #define int long long int dp[N][N], Dp[N][N], n, m, k; char a[N][N]; void get(vector<pair<char, pair<int, int>>> v){ // cout<<"here again!!!!!!!!!!!!!!!!!!"<<endl; cout<<v.back().first; if (v[0].second == make_pair(n, m)) return; vector<pair<char, pair<int, int>>> v2; for (auto [c, pr] : v){ auto [i, j] = pr; if (i + 1 <= n) v2.push_back({a[i+1][j], {i+1, j}}), Dp[i+1][j] += Dp[i][j]; if (j + 1 <= m) v2.push_back({a[i][j+1], {i, j+1}}), Dp[i][j+1] += Dp[i][j]; } sort(begin(v2), end(v2)); v2.resize(unique(begin(v2), end(v2)) - begin(v2)); int k2 = 0; char prv = '0'; for (auto [c, pr] : v2){ auto [i, j] = pr; if (c != prv and k2 < k){ k -= k2, k2 = 0; prv = c; } k2 += dp[i][j] * Dp[i][j];; // cout<<i<<" "<<j<<" "<<k2<<" "<<k<<endl; if (k2 >= k){ // cout<<"done"<<endl; while (v2.size() > 0 and v2.back().first != c) v2.pop_back(); while (v2.size() > 0 and v2.front().first != c) v2.erase(begin(v2)); break; } } get(v2); } signed main(){ cin>>n>>m; for (int i=1;i<=n;i++){ for (int j=1;j<=m;j++) cin>>a[i][j]; } dp[n][m] = 1; for (int i=n;i>=1;i--){ for (int j=m;j>=1;j--) dp[i][j] += dp[i+1][j] + dp[i][j+1]; } // for (int i=1;i<=n;i++){ // for (int j=1;j<=m;j++){ // if (dp[i][j] < 10) // cout<<' '; // cout<<dp[i][j]<<' '; // } // cout<<'\n'; // } cin>>k; Dp[1][1] = 1; get({{a[1][1], {1, 1}}}); }