A Hashes

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define len(v) (int)v.size()
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define pii pair<int, int>
#define vi vector<int>
#define vii vector<vector<int>>
#define vpii vector<pair<int, int>>
#define ull unsigned long long
//#define int long long
//#define ll ull
const int N = 1e6 + 1;
const int maxn = 2e5 + 10;
const int C = 20;
const int logn = 20;
const int inf = 1e9;
const ll mod = 1e9 + 7;
const int M = 1e9;
const ull M2 = 998244353;
const ld eps = 1e-6;
using namespace std;

// random
std::mt19937_64 gen(std::chrono::steady_clock::now().time_since_epoch().count());

template<class T>
istream &operator>>(istream &in, vector<T> &a) {
    for (auto &i : a)
        in >> i;
    return in;
}

template<class T>
ostream &operator<<(ostream &out, vector<T> &a) {
    for (auto &i : a)
        out << i << ' ';
    return out;
}

ll binpow (ll a, ll n) {
    if (n == 0)
        return 1ll;
    if (n % 2 == 1)
        return ((binpow (a, n-1) * a) % mod);
    else {
        ll b = binpow (a, n/2);
        return ((b * b) % mod);
    }
}

ll inv(ll x) {
    return binpow(x, 1200720071 - 2);
}

int p = 59, m = 1e9 + 33;
ll ppow[maxn];
void clchash(string a, vector<ll>& h, vector<ll>& h2) {
    int n = len(a);
    h.resize(n + 1); h2.resize(n + 1);
    h[0] = 0;
    for (int i = 0; i < n; ++i) { // h[n]
        h[i + 1] = ((h[i] * p) % m + a[i] * 1ll) % m;
    }
    h2[n] = 0;
    for (int i = n - 1; i >= 0; --i) { // h[n]
        h2[i] = ((h2[i + 1] * p) % m + a[i] * 1ll) % m;
    }
}
ll geth(int l, int r, vector<ll>& h) { // [l, r] ; 0 <= l, r < n ;  p^{r - l} * p^l = p^r
    return ((h[r + 1] - (h[l] * ppow[r - l + 1]) % m) % m);
}
ll geth2(int l, int r, vector<ll>& h) {
    return (h[l] - (h[r + 1] * ppow[r - l + 1]) % m) % m;
}


vector<int> solve(int n, string s) {
    vector<ll> h, h2;
    clchash(s, h, h2);
    vector<int> a(n);
    a[0] = 1;
    for (int i = 1; i < n; ++i) {
        if (i == n - 1) {
            cout << "";
        }
        int l = -1;
        int r = i + 1;
        //cout << i << '\n';
        while (l + 1 < r) {
            int mid = (l + r) / 2;
            ll get1 = geth(0, mid, h);
            ll get2 = geth2(i - mid, i, h2);
            //cout << 0 << ' ' << m << "     " << i - m << ' ' << i << '\n';
            if (get1 == get2)
                l = mid;
            else
                r = mid;
        }
        a[i] = l + 1;
    }
    return a;
    /*string a;
    cin >> a;
    vector<ll> h, h2;
    clchash(a, h, h2);
    int k; cin >> k;
    while (k--) {
        int l1, r1, l2, r2; cin >> l1 >> r1 >> l2 >> r2;
        cout << geth(l1, r1, h) << ' ' << geth2(l2, r2, h2) << '\n';
    }
     */
}

vector<int> zfunc(string s) {
    int n = len(s);
    vector<int> z(n + 1);
    int l = 0, r = 0;
    for (int i = 1; i < n; ++i) {
        if (r >= i) z[i] = min(z[i - l], r - i + 1);
        while (z[i] + 1 < n && s[z[i]] == s[z[i] + i])
            ++z[i];
        if (i + z[i] - 1 > r) {
            l = i;
            r = i + z[i] - 1;
        }
    }
    return z;
}

vector<int> solve2(int n, string s) {
    string ss = s;
    reverse(all(s));
    ss += s;
    vi zt = zfunc(ss);
    vi res;
    for (int i = len(ss) - 1; i >= len(s); --i)
        res.push_back(zt[i]);
    return res;
}



signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    /*ppow[0] = 1ll;
    for (int i = 1; i < maxn; ++i) {
        ppow[i] = (ppow[i - 1] * p) % m;
    }

    int test = 1;
    while (true) {
        int n = gen() % 15;
        string s;
        for (int i = 0; i < n; ++i) {
            char cur = ((gen() % 250) + 250) % 250;
            while (!((cur <= 'z' && cur >= 'a') || (cur <= 'Z' && cur >= 'A')))
                cur = ((gen() % 250) + 250) % 250;
            s += cur;
        }
        cout << "TEST " << test << ": ";
        cout << s << '\n';
        vi ans1 = solve(n, s), ans2 = solve2(n, s);
        for (int i = 0; i < n; ++i) {
            if (ans1[i] != ans2[i]) {
                cout << "WA" << ' ' << test << '\n';
                cout << n << ' ' << s << '\n';
                exit(0);
            }
        }
        test++;
    }
    */
    int T = 1;
    //cin >> T;
    while (T--) {
        solve();
    }
}