#include <bits/stdc++.h> using namespace std; using ll = long long; const int N = 2000; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); const ll M = (1ll << 61) - 1, R = uniform_int_distribution<ll>(0, M - 1)(rng); array<ll, N> h[N], hhash[N], pows; ll sub(array<ll, N> &a, int l, int r) { return (ll)((a[r] - (__int128)pows[r - l + 1] * a[l - 1]) % M); } int bin_search(int l, int r, function<bool(int)> f) { while (l < r) { int m = (l + r + 1) / 2; if (f(m)) l = m; else r = m - 1; } return l; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, m; cin >> n >> m; vector<string> image(n); for (auto &s : image) cin >> s; pows[0] = 1; for (int i = 1; i < N; i++) pows[i] = (ll)((__int128)R * pows[i - 1] % M); for (int i = 1; i < 2 * n; i++) { for (int j = 1; j < 2 * m; j++) h[i][j] = (ll)(((__int128)R * h[i][j - 1] + image[(i - 1) % n][(j - 1) % m]) % M); for (int j = 1; j <= m; j++) hhash[j][i] = (ll)(((__int128)R * hhash[j][i - 1] + sub(h[i], j, j + m - 1)) % M); } int r = 0, c = 0; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { int rsame = bin_search(0, n, [&](int mid) { return sub(hhash[c + 1], r + 1, r + mid) == sub(hhash[j + 1], i + 1, i + mid); }); if (rsame == n) continue; int csame = bin_search(0, m, [&](int mid) { return sub(h[r + rsame + 1], c + 1, c + mid) == sub(h[i + rsame + 1], j + 1, j + mid); }); if (image[(r + rsame) % n][(c + csame) % m] > image[(i + rsame) % n][(j + csame) % m]) { r = i; c = j; } } } for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) cout << image[(r + i) % n][(c + j) % m]; cout << '\n'; } }