#include <bits/stdc++.h> // https://oj.uz/problem/view/COCI20_satellti using namespace std; using ll = long long; #define fi first #define se second const int MX = 2001; ll hhash[MX][MX], pref[MX][MX]; char image[MX][MX]; ll poww[MX * MX / 2]; const ll MOD = (1LL << 61) - 1; const ll B = 9973; int N, M; int main() { cin.tie(NULL) -> sync_with_stdio(false); cin >> N >> M; poww[0] = 1; for (int i = 1; i < MX * MX / 2; ++i) poww[i] = (__int128)poww[i - 1] * B % MOD; for (int i = 1; i <= N; ++i) { string s; cin >> s; for (int j = 1; j <= M; ++j) image[i][j] = image[i + N][j] = image[i][j + M] = image[i + N][j + M] = s[j - 1]; } for (int i = 1; i <= 2 * N; ++i) for (int j = 1; j <= 2 * M; ++j) hhash[i][j] = ((__int128)hhash[i][j - 1] * B + image[i][j]) % MOD; for (int j = 1; j <= M; ++j) for (int i = 1; i <= 2 * N; ++i) { ll row = (hhash[i][j + M - 1] - (__int128)hhash[i][j - 1] * poww[M] % MOD + MOD) % MOD; pref[i][j] = ((__int128)pref[i - 1][j] * poww[M] + row) % MOD; } int ans = 1; auto cord = [&](int i) { return make_pair((i - 1) / M + 1, (i - 1) % M + 1); }; auto get_hash = [&](int i, int len) { auto [r, c] = cord(i); int fullrows = (len - 1) / M; int collen = len - fullrows * M; // pref[r + fullrows - 1][c] - (__int128)pref[r - 1][c] * poww[M * fullrows] ll blockhash = fullrows ? (ll)(pref[r + fullrows - 1][c] - (__int128)pref[r - 1][c] * poww[M * fullrows] % MOD + MOD) % MOD : 0LL; ll rowhash = (hhash[r + fullrows][c + collen - 1] - (__int128)hhash[r + fullrows][c - 1] * poww[collen] % MOD + MOD) % MOD; return (ll)(((__int128)blockhash * poww[collen] + rowhash) % MOD); }; auto get_image = [&](int i, int len) { auto [r, c] = cord(i); auto [dr, dc] = cord(len); r = r + dr - 1; c = c + dc - 1; return image[r][c]; }; for (int i = 1; i <= N * M; ++i) { int lo = 1, hi = N * M; while (lo < hi) { int m = (lo + hi) / 2; if (get_hash(i, m) == get_hash(ans, m)) // identical lo = m + 1; else hi = m; } if (get_image(i, lo) == '*' && get_image(ans, lo) == '.') ans = i; } for (int r = (ans - 1) / M + 1; r < (ans - 1) / M + 1 + N; ++r) { for (int c = (ans - 1) % M + 1; c < (ans - 1) % M + 1 + M; ++c) cout << image[r][c]; cout << '\n'; } return 0; } /*****************************= -+**********************************= :-*****************************************+: ..:*************+=+*******************************=. ..-==*****************+=-+*****************************+. ..-=***********************+--+****************************= :+**************#*#**********+--+***************************- .=--=. .+*********************#*********+--****************************++++----: -+***********************##*********--+********************************+--=. =****=**********************#*********+-=***************************#*****+--= .=****+***********************************-=*********************#*****##*****=-=. :=*****=************************************=-*****************#******#####*****=-=. .=**+***=**************************#**********==***********##*******#**######*****+-=. +***=***+***************************#**********-+*****####********#*****#####******+-=: =+**=****+****************#**********************-*####*********##***#*#######*******+-=. .=*#*=****=****************#***********#**********++#*********###****#*#*######********+-=. =**#++****=***#******#******#***********#**********=*******####****##**#########********=-= .=*##=****#=***#*******#*****#*#*********#*#********+****#####****###**#*######%#*********-== -*###=**###+*#*#######*##*######*######**##########*#*####*....-#########%##%##%##########=-*. =*###+######+############################################=..+=-+.########%##%##%##########*-+* +###*+######**#################%##########%###########%#*..=-+===-######%###+##%###########-+#. .+###**#######+###%############%#%#########%###########%#...=*:.=:.#####%#%%#+##%###########=+#+ .-+#%#**#######%=###%#############%%######%#%%##########*...+===+...####%%%%% *%%############=+## .=*#%#*+#######%%+##%%###########%#%%%######%%#%########=...====+..####%%%%%: *%%############=*## .+*#*##+###%###%%%%##%%##########*##%%%####%%%#%#######%*=-..====:####%%%%%= #%%############=###- .+*#=#-=#####%#%%%####%%%########+*###%%%##%%%#%#######%*==:==+-.*##%%%%%%+ #%%###########*=###+ :=##=#-+####%%#%%%#**##%%%#######+++#*+%*%%%%%#%%########=.-=....##%%%%%%*....%%%#####%#####+=####- .#*.#--*#####%#%%#****##%%#####+-===#+=**+%%%#%%########=......+%%%%%%%+ %%######%#####=*####. #* *+.*####%%%%%#++++- :*%%###+.....--..*==#%%%########==-:::=%%%%%%%- %%######%#####=#####. -# .%.=####%%%%%#++=*......:##*.......-..-==%%%#####%##=#%%%%%%%%%%# #%######%####*=###%# *. +-.####%%%%%%===.=....-:.*#...........-=%%%#######*==*@%%%%%%%* #%######%####+*###%# *.:###%%%%%%-.....=......*:...........-%%%######%+*==*#%%%%%# +%######%####=####%#. =.=###%%%%%:.............:............#*%%####*#*=====%@%%% :%#####%%####+######: .=%##%%%%%*.............:............#*%%####+#+======%#%* .:-=%%%%%%%%###+#####+#- .%%##%%%-*-..............::::.......#+%%####+#=====-...#: :*%%%%%%%%%%%%%%%%###*#####=#= .####%%%:.:-.......--...............#=#%###+*#====-...:*%%%%%%%%%%%%%%%%%%%%%%########:#+ *-#%#%%- -..........:----........:*=#%##%=*+=====#%%%%%%%%%%%%%%%%%%%%%%%%%%########:#* =*.%%%%= .:........:::..........=.=####+=#=*%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%###.*# #..%%%#. -....................-:+###%*%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*# +- :%%%#+ =..................===%##%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#:. .#. =%% .*= -.............:+#%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%+. .* *%- .-........:*%%%%%%%#%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%#. .=. ## ..-:..:#%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@%%%: ..=*- .*@@@@@%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%-. #@%%%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%*:. *@%%%%%%%%%%%%%%%%%%%%%@@@%@@@@%%%%%@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%=: :@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%#: .%@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%: .-%@%%%%%%%@@%%%%%%%%%%%%%%@@@@@@@@@@@%%%%%%%%%%%%@@@@@%%%%%%%%%%%%%%%%%%%%%%%%%%%%@- ..#%@%%%%%@%%%%%%%%%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%%%%%: .%@%%%%@%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%:: .:@@%@%%%%%%%%%%%%@@@@@@@@%%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@@@%%%%%%%%%%%%%%%%%%-:: .*@%%%%%%%%%%%%%@@@@@@@@@%%%%%%%%%@%%%%%%%%%%%%%%%%%%%%%%@%%@@%%%%%%%%%%%%%%%%@=: -@%@@@@@@@@@@@@@@@@@@%@%%%%%%@@%@@%%%%@@@%%%%%%%%%%%%%%%%%%%%@@@%@@@@@@@@@@@@@+: %@@@@@@@@@@@@@@@@@@@@%%%%%%@@@@@%%%%%@@@@%%%%%%%%%%%%%%%%%%%%%@@@@@@@@@@@@@@@+- *@@@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%%@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@@@@#- :%@@@@@@@@@@@@@@@@%%%%%%%%@@@@%%%%@@@@@@@@%%%%%%%%%%%%%%%%%@%%%%@@@@@@@@@@@@*%- :#@@@@@@@@@@@@@%%%%%%%%%@@@@%%%%%@@@@@@@@@%%%%%%%%%%%%%%%%%@%%%@@@@@@@@@@@+-%* :-@@@@@@@@@%%%%%%%%%%%@@@@@%%%%@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@@@#--*% :=@@@@@@%%%%%%%%%%%@%@@@@%%%@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@%%%@@@@@@@%%---%+ -:-@@@@%%%%%%%%@%%%@@%@@@%%%@@@@@@@@@@@@@%%%%%%%%%%%%%%%%%@@@%%@@@@@%%%%=--*% -=@@@%%%%%%%%%@@%%@@%@@@@%%@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%%@@%%%%%%+--=%+ -=@@%%%%%%%%%%@@%%@@%%@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@%%@##%%%%%#---*%- -+@%%%%%%%%%%%@@@%@@%%@@@@@%@@@@@@@@@@@@@@@@@%%%%%%%%%%%%%%%%@@@@%@##%%%%%%====%*/