#include #include // #include // #include using namespace std; using namespace atcoder; // using namespace __gnu_pbds; using ll=long long; #define int ll using ld = long double; #define _overload3(_1,_2,_3,name,...) name #define _rep(i,n) repi(i,0,n) #define repi(i,a,b) for(int i=int(a);i=int(0);--i) #define fore(i,a) for(auto &i:a) #define all(x) x.begin(),x.end() #define sz(x) ((int)(x).size()) #define bp(x) (__builtin_popcount((long long)(x))) #define pb push_back #define eb emplace_back #define mpa make_pair #define bit(n) (1LL<<(n)) template using V = vector; template using VV = V>; template using max_heap = priority_queue; template using min_heap = priority_queue, greater<>>; #define P pair #define TP tuple #define F first #define S second templatebool chmax(T &a, const T &b) { if (abool chmin(T &a, const T &b) { if (b>h>>w; V s(h); rep(i,h)cin>>s[i]; // if(h==1&&w==1){ // cout< ans; ans.emplace_back(0,0); deque

dq; int nowh=0,noww=0; const int d[]={0,1,0}; V> col(h,V(w)); while(!(nowh==h-1&&noww==w-1)){ deque dq; dq.emplace_back(nowh,noww,0); int p=0; set st; int nexth=-1,nextw=-1; while(sz(dq)){ auto [a,b,c]=dq.front(); dq.pop_front(); if(p!=c){ if(sz(st)!=1||(a==h-1&&b==w-1)){ ans.emplace_back(nexth,nextw); nowh=nexth; noww=nextw; break; } st.clear(); } p=c; rep(i,2){ int na=a+d[i]; int nb=b+d[i+1]; if(na>=h||nb>=w||col[na][nb])continue; dq.emplace_back(na,nb,c+1); st.insert(s[na][nb]); col[na][nb]=1; if(s[na][nb]<=*st.begin()){ nexth=na; nextw=nb; } } } } string x; rep(i,1,sz(ans)){ rep(j,ans[i-1].first,ans[i].first){ x+=s[j][ans[i-1].second]; } rep(j,ans[i-1].second,ans[i].second){ x+=s[ans[i].first][j]; } } x+=s[h-1][w-1]; cout<