/*
g++ -std=gnu++20 cf2028.cpp -o cf2028 && ./cf2028 < input.txt > output.txt
*/
#include <vector>
#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <map>
#include <algorithm>
#include <deque>
#include <stack>
#include <set>
#include <math.h>
#include <queue>
#include <cmath>
#include <numeric>
#include <complex>
#include <chrono>
#include <random>
#include <assert.h>
#include <iomanip>
// #include <bits/stdc++.h>
using namespace std;
namespace macros {
bool printDebug = 0;
template<typename T>
void print(T arg) {
if (!printDebug) return;
cout << arg;
}
template<typename T, typename... Args>
void print(T first, Args... args) {
if (!printDebug) return;
cout << first << " ";
print(args...);
}
// # define M_PI 3.14159265358979323846
#define optimiza_io \
cin.tie(0); \
ios_base::sync_with_stdio(0);
#define ll long long
#define ld double
#define pb push_back
#define eb emplace_back
#define pi pair<ll, ll>
#define f first
#define s second
#define rep(i, a, b) for (ll i = (a); i < (b); i++)
#define repi(i, a, b) for (ll i = (a); i >= (b); i--)
#define trav(a, x) for (auto &(a) : (x))
#define endl "\n"
#define vi vector<ll>
#define vvi vector<vi>
#define vpi vector<pi>
#define vs vector<string>
#define sz(a) ((ll)(a).size())
#define ldd(a) ((ld)(a))
#define mp(a, b) make_pair((a), (b))
#define minn(a, b) (a) = min ((a), (b))
#define maxx(a, b) (a) = max ((a), (b))
#define all(x) (x).begin(), (x).end()
#define popcount(x) (ll)__builtin_popcount((x))
const ld EPS = 1e-7;
typedef long long C;
typedef complex<C> P;
#define X real()
#define Y imag()
template<typename T>
void printVec(vector<T> arr) {
trav(u, arr) {
print(u, " ");
}
print(endl);
}
// check if 2 ld are equal
bool equal_ld(ld a, ld b) {
return abs(a-b) < EPS;
}
// for xor hashing
ll rng(const ll most = INT64_MAX) {
static mt19937 gen(chrono::steady_clock::now().time_since_epoch().count());
return uniform_int_distribution<ll>(0, most)(gen);
}
void modulate(ll &x, const ll &mod) {
x %= mod;
x += mod;
x %= mod;
}
}
const ll INF = 1e6;
// const ll mod = 1e9+7;
const ll mod = 998244353;
const ll maxn = 3e5+10;
using namespace macros;
// solve
struct HashedString {
// change M and B if you want
static const long long M = 1e9 + 9;
static long long B;
// pow[i] contains B^i % M
static vector<long long> pow;
// p_hash[i] is the hash of the first i characters of the given string
vector<long long> p_hash;
// can be vi too
HashedString(const string &s) : p_hash(s.size() + 1) {
while (pow.size() <= s.size()) { pow.push_back((pow.back() * B) % M); }
p_hash[0] = 0;
for (int i = 0; i < s.size(); i++) {
p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
}
}
HashedString(const vi &s) : p_hash(s.size() + 1) {
while (pow.size() <= s.size()) { pow.push_back((pow.back() * B) % M); }
p_hash[0] = 0;
for (int i = 0; i < s.size(); i++) {
p_hash[i + 1] = ((p_hash[i] * B) % M + s[i]) % M;
}
}
// r inclusive
long long get_hash(int start, int end) {
long long raw_val = (p_hash[end + 1] - (p_hash[start] * pow[end - start + 1]));
return (raw_val % M + M) % M;
}
};
long long HashedString::B = rng(HashedString::M - 1);
vector<long long> HashedString::pow = {1};
void solve() {
ll n, m;
cin >> n >> m;
vs mat(n);
trav(u, mat) {
cin >> u;
u += u;
}
rep(i, 0, n) {
mat.pb(mat[i]);
}
vector<HashedString> ha, haCols;
vvi cols(m, vi(2*n)); // transposed
for (auto u : mat) {
ha.emplace_back(u);
}
// start j
rep(j, 0, m) {
rep(i, 0, 2*n) {
cols[j][i] = ha[i].get_hash(j, j+m-1);
}
}
rep(j, 0, m) {
haCols.emplace_back(cols[j]);
}
pi ans = mp(0,0);
auto getHashCols = [&] (pi &dir, ll mid) {
return haCols[dir.s].get_hash(dir.f , dir.f + mid);
};
auto getHash = [&] (pi &dir, ll difRow, ll mid) {
return ha[dir.f + difRow].get_hash(dir.s , dir.s + mid);
};
auto check = [&] (pi curr) {
// BS over colums, find first diff
ll l = 0, r = n-1, mid;
ll difRow = n;
while (l <= r) {
mid = (r-l) / 2 + l;
print("l = ", l, " ");
print("r = ", r, " ");
print("mid = ", mid, " ", endl);
if (getHashCols(ans, mid) == getHashCols(curr, mid)) {
l = mid+1;
print(" - equal", endl);
} else {
minn(difRow, mid);
print(" - dif, interesting", endl);
r = mid-1;
}
}
print("got", difRow, endl);
if (difRow == n) return false;
print(endl, "---", endl);
l = 0, r = m-1;
ll difCol = m;
while (l <= r) {
mid = (r-l) / 2 + l;
print("l = ", l, " ");
print("r = ", r, " ");
print("mid = ", mid, " ", endl);
if (getHash(ans, difRow, mid) == getHash(curr, difRow, mid)) {
l = mid+1;
print(" - equal", endl);
} else {
minn(difCol, mid);
print(" - dif, interesting", endl);
r = mid-1;
}
}
if (difCol == m) return false;
bool result = (
mat[curr.f + difRow][curr.s + difCol]
<
mat[ans.f + difRow][ans.s + difCol]
);
print("result = ", result, endl);
return result;
};
rep(i, 0, n) {
rep(j, 0, m) {
if (i == j && i == 0) continue; // first assumed to be smaller
print(i, j, ": ", endl);
if (check(mp(i, j))) {
ans = mp(i, j);
}
print(endl," ..-.-.-.- ", endl, endl);
}
}
rep(i, 0, n) {
rep(j, 0, m) {
cout << mat[i + ans.f][j + ans.s];
}
cout << endl;
}
}
//
/*
NEW ME:
- Read test cases and experiment with them, use your page 2!!!
- Ask questions. What to do to achieve this? What's different from usual slower X strat?
- And ofc, observations
- Long, Unnecesary coding is not needed!
ALWAYS REMEMBER:
- Focus on the target at hand! ---- Making observations? Making formula for X? Write your target down!
- Simplify before coding
- Check all test cases!
- Divide problema dificil en problemas pequeños. POR PARTES!
- OBSERVATIONS: Recuerda el significado de su nombre
- EDGE CASES: Yes
- Calm down
- Sometimes try formulazo. Intenta representar el valor de manera matemática at some point.
- Luego intenta derivar formula o simplificarla, ya de ahí tal vez ya queda el problema
- Formulazo o upper limits!
- for debugging, read code first before just printing everything haha
- Even if you find a solution, is the process you made necessary? Is there a way to simplify the process or omit some steps?
- If greedy, really check if you cannot phantom a possible edge case where it is out of your control
- Write down the formulas better to facilitate coding
- primero itera los bits en bitmasking!
- Si quiero hacer greedy, piensa en "cuando es que me conviene hacer x?"
OTHER
- its doable
- link your ideas, dont forget them
- remember key aspects, think of even more, optimal
*/
signed main() {
optimiza_io
bool file = 0;
if (file) {
freopen("lightsout.in", "r", stdin);
freopen("lightsout.out", "w", stdout);
}
bool multipleTestCases = 0;
printDebug = 0;
int t = 1;
if (multipleTestCases) {
cin >> t;
}
rep(i, 0, t) {
print("\n---------------------\n");
solve();
}
}
