#include <bits/stdc++.h>
using namespace std;
#define int long long
#define _ << " , " <<
#define bug(x) cout << #x << " >>>>>>> " << x << endl;
#define Max(a, b) (a > b ? a : b)
#define Min(a, b) (a < b ? a : b)
#define ii pair<int, int>
#define fi first
#define se second
#define UNTIL(t) while (clock() < (t) * CLOCKS_PER_SEC)
#define SZ(a) (int)a.size()
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
const int MAX = 2000000; //2 * 10^5
const int MOD = 1000000007; //10^9 + 7
const int OO = 0x3f3f3f3f; // 0x3f3f3f3f;
const double EPS = 1e-9; //10^-9
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int normalize(int x)
{
x = x % MOD;
if(x < 0) x += MOD;
return x;
}
int add(int a, int b)
{
return normalize(normalize(a) + normalize(b));
}
int prod(int a, int b)
{
return normalize(normalize(a) * normalize(b));
}
int sub(int a, int b)
{
return normalize(normalize(a) - normalize(b));
}
int expMod(int x, int e)
{
int ans = 1;
while(e > 0)
{
if(e & 1LL) ans = prod(ans, x), e--;
else x = prod(x, x), e /= 2;
}
return normalize(ans);
}
int inv(int x)
{
return expMod(x, MOD - 2);
}
int n, m;
string image[2005];
int pf[2005][2005];
int P[2005];
int Q[2005];
int invpx[2005];
int invqx[2005];
int get(int i, int j) {
int x = image[i - 1][j - 1] == '.' ? 1 : 0;
return prod(x, prod(P[i], Q[j]));
}
void build() {
P[0] = Q[0] = 1;
for(int i = 1; i < 2005; i++) {
P[i] = prod(17, P[i - 1]);
Q[i] = prod(13, Q[i - 1]);
}
for(int i = 0; i < 2005; i++) {
invqx[i] = inv( Q[i] );
invpx[i] = inv( P[i] );
}
for(int i = 1; i <= 2 * n; i++)
for(int j = 1; j <= 2 * m; j++)
pf[i][j] = add(sub( add(pf[i - 1][j], pf[i][j - 1]), pf[i - 1][j - 1]), get(i, j));
}
int query(int i, int j) {
return pf[i][j];
}
int sub_matrix(int x1, int y1, int x2, int y2) {
int sum = 0;
sum = add(sum, query(max(x1, x2), max(y1, y2)));
sum = sub(sum, query(max(x1, x2), min(y1, y2) - 1));
sum = sub(sum, query(min(x1, x2) - 1, max(y1, y2)));
sum = add(sum, query(min(x1, x2) - 1, min(y1, y2) - 1));
sum = prod(sum, invpx[x1]);
sum = prod(sum, invqx[y1]);
return sum;
}
int get_raw(int a, int b, int A, int B) {
int l = 0, r = n - 1, ans = -1;
while(l <= r) {
int mid = (l + r) / 2;
int s1 = sub_matrix(a, b, a + mid, b + m - 1);
int s2 = sub_matrix(A, B, A + mid, B + m - 1);
if(s1 != s2) r = mid - 1, ans = mid;
else l = mid + 1;
}
return ans;
}
int get_col(int a, int b, int A, int B, int R) {
int l = 0, r = m - 1, ans = -1;
while(l <= r) {
int mid = (l + r) / 2;
int s1 = sub_matrix(a, b, a + R, b + mid);
int s2 = sub_matrix(A, B, A + R, B + mid);
if(s1 != s2) r = mid - 1, ans = mid;
else l = mid + 1;
}
return ans;
}
void print_matrix(int I, int J) {
I--; J--;
for(int i = I; i < I + n; i++) {
for(int j = J; j < J + m; j++)
cout << image[i][j];
cout << '\n';
}
}
void solve(){
cin >> n >> m;
for(int i = 0; i < n; i++) {
cin >> image[i];
image[i] += image[i];
image[i + n] = image[i];
}
build();
int I = 1, J = 1;
for(int i = 1; i <= n; i++)
for(int j = 1; j <= m; j++)
if(image[i - 1][j - 1] == '*')
I = i, J = j, i = n, j = m;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
int r = get_raw(i, j, I, J);
if(r == -1) continue;
int c = get_col(i, j, I, J, r);
if(c == -1) continue;
int pri = i + r - 1, prj = j + c - 1;
if(image[pri][prj] == '*') I = i, J = j;
}
}
print_matrix(I, J);
}
int32_t main() {
fastio;
int t = 1;
for(int caso = 1; caso <= t; ++caso) {
solve();
}
return 0;
}
/*
Before submit:
Check the corners cases
Check solution restrictions
For implementation solutions:
Check the flow of the variables
For intervals problems:
Think about two pointers
For complete search:
Think about cuts
If you get WA:
Reread your code looking for stupid typos
Try various manual testcases
Recheck the correctness of your algorithm
Reread the statement
Write a straightforward solution, create lots of testcases by yourself, and compare both solutions
Generate random test cases and perform a stress test, comparing your solution with the one that you are sure is correct
Change the coder (if you're with a team)
Give up. You may have other tasks to solve.
*/
