F. Fibonacci Grid

#include <bits/stdc++.h>
using namespace std;

#define ALL(x) begin(x), end(x)
#define SZ(x) ((int)(x).size())

const int INF = INT_MAX >> 2;

int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);

    int N, M; cin >> N >> M;

    vector<string> grid(N);
    for (string &str : grid) cin >> str;

    {
        int n_0 = 0;
        for (string &str : grid) n_0 += count(ALL(str), '0');
        if (n_0 == 0 or n_0 == N*M) {
            for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) cout << -1 << " \n"[j == M-1];
            return 0;
        }
    }

    vector<int> fib{1, 1}, fib_inv(3*M);
    while (fib.back() < 3*M) fib.emplace_back(end(fib)[-1] + end(fib)[-2]);
    for (int i = 0, tok = 1; i < 3*M; ++i) {
        while (fib[tok] <= i) ++tok;
        fib_inv[i] = tok - 1;
    }

    vector ans(N, vector<int>(M, -1));
    vector val(N, vector<int>(M));

    for (char c0 : {'0', '1'}) for (char c1 : {'0', '1'}) {

        string s0(1, c0), s1(1, c1);
        while (SZ(s1) < 3*M) tie(s0, s1) = tuple{s1, s1+s0};

        string S = s1 + "#";
        for (int i = 0; i < N; ++i) S += grid[i] + grid[i] + grid[i] + grid[i] + "$";

        vector<int> Z(SZ(S), 0);
        for (int i = 1, r = 0, p = 0; i < SZ(S); ++i) {
            if (i < r) Z[i] = min(r-i, Z[i-p]);
            while (i + Z[i] < SZ(S) and S[Z[i]] == S[i + Z[i]]) ++Z[i], ++r, p = i;
            if (i + Z[i] > r) r = i + Z[i], p = i;
        }

        for (int i = 0, offset = SZ(s1)+1; i < N; ++i, offset += 4*M+1) {
            if (Z[offset] >= 3*M) {
                for (int j = 0; j < M; ++j) val[i][j] = INF;
            }
            else {
                for (int j = 0; j < M; ++j) val[i][j] = fib_inv[Z[offset+j]];
            }
        }

        for (int j = 0; j < M; ++j) {
            deque<int> deq_id, deq_val;
            int sz = 0;
            for (int i = 2*N+SZ(fib); i >= 0; --i) {
                int tmp_val = val[i%N][j] - i;
                while (SZ(deq_val) and tmp_val < deq_val[sz-1]) deq_id.pop_back(), deq_val.pop_back(), --sz;
                deq_id.emplace_back(i), deq_val.emplace_back(tmp_val), ++sz;

                if (i < N and grid[i][j] == c0 and grid[(i+1)%N][j] == c1) {
                    int pos = prev(lower_bound(ALL(deq_val), -i)) - begin(deq_val);
                    ans[i][j] = deq_id[pos] - i - 2;
                }
            }
        }

    }

    for (int i = 0; i < N; ++i) for (int j = 0; j < M; ++j) cout << ans[i][j] << " \n"[j == M-1];

    return 0;
}