#include <bits/stdc++.h> // https://oj.uz/problem/view/COCI20_satellti using namespace std; using ll = long long; #define fi first #define se second struct StringHash { int N, M; const ll MOD = (1LL << 61) - 1; const ll B = 9973; vector<ll> pow, hash, pref; StringHash(string& s, int m) : N(s.size()), M(m), pow(s.size()), hash(s.size()), pref(s.size()) { pow[0] = 1; for (int i = 1; i < N; ++i) pow[i] = (__int128)pow[i - 1] * B % MOD; hash[0] = s[0]; for (int i = 1; i < N; ++i) hash[i] = ((__int128)hash[i - 1] * B + s[i]) % MOD; pref[0] = hash[0]; for (int i = 1; i < N; ++i) { int l = (i / M) * M; int r = l + M - 1; // row: // hash[r] - hash[i - 1] * pow[r - i + 1] + hash[i - 1] - (l - 1 < 0 ? 0 : hash[l - 1]) * pow[i - l + 1]; ll abovecurrow = (__int128)(l - 1 < 0 ? 0 : hash[l - 1]) * pow[i - l + 1] % MOD; ll row = ((hash[r] + (__int128)hash[i - 1] * (1 - pow[r - i + 1]) - abovecurrow) % MOD + MOD) % MOD; pref[i] = row + (i < M ? 0LL : pref[i - M]) * (__int128)pow[M] % MOD; } } ll hh(auto& v, int l, int r) { if (r < 0) return 0; if (l <= 0) return v[r]; return (v[r] - (__int128)v[l - 1] * pow[r - l + 1] % MOD + MOD) % MOD; } ll getHash(int i, int len) { int to = i + (len / M) * M; ll block; if (to - M < 0) block = 0; else if (i - M < 0) block = pref[to - M]; else block = (pref[to - M] - (__int128)pref[i - M] * pow[to - i] % MOD + MOD) % MOD; if (len % M == 0) return block; // cout << "B: " << block << endl; int l = (to / M) * M; int r = l + M - 1; ll row = hh(hash, to, min(to + len % M - 1, r)); if (r < to + len % M - 1) // goes over into next row { int toadd = len % M - (to - r + 1); if (toadd) row = ((__int128)row * pow[toadd] + hh(hash, l, l + toadd - 1)) % MOD; } return ((__int128)block * pow[len % M] + row) % MOD; } }; int main() { cin.tie(NULL) -> sync_with_stdio(false); int N, M; cin >> N >> M; string image; for (int i = 0; i < N; ++i) { string s; cin >> s; image.append(s); } image.append(image); StringHash h(image, M); // for (int i = 1; i <= N; ++i) // { // for (int j = 1; j <= M; ++j) // cout << (grid[i][j] == '*') << ' '; // cout << endl; // } int ans = 0; for (int i = 0; i < N * M; ++i) { int lo = 1, hi = N * M; while (lo < hi) { int mid = (lo + hi) / 2; if (h.getHash(i, mid) == h.getHash(ans, mid)) // identical lo = mid + 1; else hi = mid; } // cout << i << ' ' << lo << endl; // cout << image[i + lo - 1] << ' ' << image[ans + lo - 1] << endl; if (image[i + lo - 1] == '*' && image[ans + lo - 1] != '*') ans = i; } // cout << '*' * 9973 + '*' << endl; // cout << h.getHash(1, 2) << endl << h.getHash(6, 2) << endl; // cout << ans << endl; for (int i = ans / M; i < ans / M + N; ++i) { for (int j = ans % M; j != M; ++j) cout << image[i * M + j]; for (int j = 0; j != ans % M; ++j) cout << image[i * M + j]; cout << '\n'; } return 0; } /*****************************= -+**********************************= :-*****************************************+: ..:*************+=+*******************************=. ..-==*****************+=-+*****************************+. ..-=***********************+--+****************************= :+**************#*#**********+--+***************************- .=--=. .+*********************#*********+--****************************++++----: -+***********************##*********--+********************************+--=. =****=**********************#*********+-=***************************#*****+--= .=****+***********************************-=*********************#*****##*****=-=. :=*****=************************************=-*****************#******#####*****=-=. .=**+***=**************************#**********==***********##*******#**######*****+-=. +***=***+***************************#**********-+*****####********#*****#####******+-=: =+**=****+****************#**********************-*####*********##***#*#######*******+-=. .=*#*=****=****************#***********#**********++#*********###****#*#*######********+-=. =**#++****=***#******#******#***********#**********=*******####****##**#########********=-= .=*##=****#=***#*******#*****#*#*********#*#********+****#####****###**#*######%#*********-== -*###=**###+*#*#######*##*######*######**##########*#*####*....-#########%##%##%##########=-*. =*###+######+############################################=..+=-+.########%##%##%##########*-+* +###*+######**#################%##########%###########%#*..=-+===-######%###+##%###########-+#. .+###**#######+###%############%#%#########%###########%#...=*:.=:.#####%#%%#+##%###########=+#+ .-+#%#**#######%=###%#############%%######%#%%##########*...+===+...####%%%%% *%%############=+## .=*#%#*+#######%%+##%%###########%#%%%######%%#%########=...====+..####%%%%%: *%%############=*## .+*#*##+###%###%%%%##%%##########*##%%%####%%%#%#######%*=-..====:####%%%%%= #%%############=###- .+*#=#-=#####%#%%%####%%%########+*###%%%##%%%#%#######%*==:==+-.*##%%%%%%+ #%%###########*=###+ :=##=#-+####%%#%%%#**##%%%#######+++#*+%*%%%%%#%%########=.-=....##%%%%%%*....%%%#####%#####+=####- .#*.#--*#####%#%%#****##%%#####+-===#+=**+%%%#%%########=......+%%%%%%%+ %%######%#####=*####. #* *+.*####%%%%%#++++- :*%%###+.....--..*==#%%%########==-:::=%%%%%%%- %%######%#####=#####. -# .%.=####%%%%%#++=*......:##*.......-..-==%%%#####%##=#%%%%%%%%%%# #%######%####*=###%# *. +-.####%%%%%%===.=....-:.*#...........-=%%%#######*==*@%%%%%%%* #%######%####+*###%# *.:###%%%%%%-.....=......*:...........-%%%######%+*==*#%%%%%# +%######%####=####%#. =.=###%%%%%:.............:............#*%%####*#*=====%@%%% :%#####%%####+######: .=%##%%%%%*.............:............#*%%####+#+======%#%* .:-=%%%%%%%%###+#####+#- .%%##%%%-*-..............::::.......#+%%####+#=====-...#: :*%%%%%%%%%%%%%%%%###*#####=#= .####%%%:.:-.......--...............#=#%###+*#====-...:*%%%%%%%%%%%%%%%%%%%%%%########:#+ *-#%#%%- -..........:----........:*=#%##%=*+=====#%%%%%%%%%%%%%%%%%%%%%%%%%%########:#* =*.%%%%= .:........:::..........=.=####+=#=*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###.*# #..%%%#. -....................-:+###%*%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*# +- :%%%#+ =..................===%##%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:. .#. =%% .*= -.............:+#%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+. .* *%- .-........:*%%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%#. .=. ## ..-:..:#%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%: ..=*- .*@@@@@%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%-. #@%%%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*:. *@%%%%%%%%%%%%%%%%%%%%%@@@%@@@@%%%%%@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%=: :@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#: .%@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%: .-%@%%%%%%%@@%%%%%%%%%%%%%%@@@@@@@@@@@%%%%%%%%%%%%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%@- ..#%@%%%%%@%%%%%%%%%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%: .%@%%%%@%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%:: .:@@%@%%%%%%%%%%%%@@@@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@@@%%%%%%%%%%%%%%%%%%-:: .*@%%%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@%%@@%%%%%%%%%%%%%%%%@=: -@%@@@@@@@@@@@@@@@@@@%@%%%%%%@@%@@%%%%@@@%%%%%%%%%%%%%%%%%%%%@@@%@@@@@@@@@@@@@+: %@@@@@@@@@@@@@@@@@@@@%%%%%%@@@@@%%%%%@@@@%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@@@+- *@@@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%%@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@@@#- :%@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%@@@@@@@@%%%%%%%%%%%%%%%%%@%%%%@@@@@@@@@@@@*%- :#@@@@@@@@@@@@@%%%%%%%%%@@@@%%%%%@@@@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@+-%* :-@@@@@@@@@%%%%%%%%%%%@@@@@%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@@@#--*% :=@@@@@@%%%%%%%%%%%@%@@@@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@%%---%+ -:-@@@@%%%%%%%%@%%%@@%@@@%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@@%%@@@@@%%%%=--*% -=@@@%%%%%%%%%@@%%@@%@@@@%%@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%%@@%%%%%%+--=%+ -=@@%%%%%%%%%%@@%%@@%%@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%@##%%%%%#---*%- -+@%%%%%%%%%%%@@@%@@%%@@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@@%@##%%%%%%====%*/