#include <bits/stdc++.h> using namespace std; #define int long long #define pb push_back #define emb emplace_back #define fr first #define sc second #define all(x) x.begin(),x.end() #define sp << " " << #define N 1000 #define inf 1e9 typedef pair<int,int> ii; typedef tuple<int,int,int> iii; vector<int> sufarr(int n,int m,vector<int> v,bool Case){ vector<int> p,c,pn,cn; p.assign(n*m,0); c.assign(n*m,0); pn.assign(n*m,0); cn.assign(n*m,0); vector<int> cnt; cnt.assign(n*m,0); for(int i=0;i<n*m;i++) cnt[v[i]]++; for(int i=1;i<n*m;i++) cnt[i]+=cnt[i-1]; for(int i=n*m-1;i>=0;i--) p[--cnt[v[i]]]=i; c[p[0]]=0; int difn=1; for(int i=1;i<n*m;i++){ if(v[p[i-1]]!=v[p[i]]) difn++; c[p[i]]=difn-1; } auto ff=[&m](int x,int k){ if(m-x%m>k) return x+k; else return x+k-m; }; for(int k=1;k<m;k<<=1){ for(int i=0;i<n*m;i++){ pn[i]=p[i]-k; if(p[i]%m<k) pn[i]+=m; } cnt.assign(difn,0); for(int i=0;i<n*m;i++) cnt[c[i]]++; for(int i=1;i<difn;i++) cnt[i]+=cnt[i-1]; for(int i=n*m-1;i>=0;i--) p[--cnt[c[pn[i]]]]=pn[i]; cn[p[0]]=0; difn=1; for(int i=1;i<n*m;i++){ ii cur={c[p[i]],c[ff(p[i],k)]}; ii pre={c[p[i-1]],c[ff(p[i-1],k)]}; if(cur!=pre) difn++; cn[p[i]]=difn-1; } swap(c,cn); } if(Case) return p; else return c; } void solve(){ int n,m; cin >> n >> m; char stl[n][m]; vector<int> a; a.assign(n*m,0); for(int i=0;i<n;i++){ for(int j=0;j<m;j++){ cin >> stl[i][j]; a[i*m+j]=(stl[i][j]=='.'?1:0); } } vector<int> p=sufarr(n,m,a,0); for(int i=0;i<m;i++) for(int j=0;j<n;j++) a[i*n+j]=p[j*m+i]; int start=sufarr(m,n,a,1)[0]; int x=start%n,y=start/n; for(int i=0;i<n;i++){ for(int j=0;j<m;j++) cout << stl[(i+x)%n][(j+y)%m]; cout << "\n"; } } int32_t main(){ cout << fixed << setprecision(0); ios_base::sync_with_stdio(false); cin.tie(NULL);cout.tie(NULL); int test=1; //~ cin >> test; while(test--){ solve(); } }