#include <bits/stdc++.h> #define int long long #define vec vector #pragma GCC optimize("O2") #define endl " \n" #define all(x) x.begin(),x.end() using namespace std; int32_t main() { ios::sync_with_stdio(false); cin.tie(nullptr); cout.precision(0); cout<<fixed; int n,m; cin>>n>>m; vec<string> x(n); for (int i = 0; i < n; i++) { cin>>x[i]; } queue<pair<int,int>> q; vec<vec<int>> p(n,vec<int>(m)); vec<vec<bool>> vis(n,vec<bool>(m,0)); p[0][0]=0; set<pair<char,pair<int,int>>> qq; qq.insert({x[0][0],{0,0}}); int r=1; while(!qq.empty()){ //cout<<"round:"<<r++<<endl[1]; int last=qq.begin()->first; while((!qq.empty())&&qq.begin()->first==last) { q.emplace(qq.begin()->second.first,qq.begin()->second.second); //cout<<qq.begin()->second.first<<" "<<qq.begin()->second.second<<endl[1]; qq.erase(qq.begin()); } while((!qq.empty())) { qq.erase(qq.begin()); } while(!q.empty()) { auto [xx,yy]=q.front(); vis[yy][xx]=1; if((yy-1>=0&&vis[yy-1][xx])&&(xx-1>=0&&vis[yy][xx-1])) p[yy][xx]=-1;else if((yy-1>=0&&vis[yy-1][xx])) p[yy][xx]=1;else if((xx-1>=0&&vis[yy][xx-1])) p[yy][xx]=-1; q.pop(); if(xx+1<m&&yy+1<n) { if(x[yy][xx+1]==x[yy+1][xx]) { qq.insert({x[yy][xx+1],{xx+1,yy}}); qq.insert({x[yy+1][xx],{xx,yy+1}}); } if(x[yy][xx+1]>x[yy+1][xx]) { qq.insert({x[yy+1][xx],{xx,yy+1}}); } if(x[yy][xx+1]<x[yy+1][xx]) { qq.insert({x[yy][xx+1],{xx+1,yy}}); } }else { if(xx+1<m) { qq.insert({x[yy][xx+1],{xx+1,yy}}); } if(yy+1<n) { qq.insert({x[yy+1][xx],{xx,yy+1}}); } } } } string res; int xx=m-1,yy=n-1; while(p[yy][xx]) { res.push_back(x[yy][xx]); if(p[yy][xx]<0) xx--; else yy--; } res.push_back(x[yy][xx]); reverse(all(res)); cout<<res<<endl[1]; return 0; }