#include <bits/stdc++.h>
using namespace std;
struct cww {
  cww() {
    if (1) {
      ios::sync_with_stdio(false);
      cin.tie(0);
    }
  }
} star;
template <typename T>
inline bool chmin(T &l, T r) {
  bool a = l > r;
  if (a) l = r;
  return a;
}
template <typename T>
inline bool chmax(T &l, T r) {
  bool a = l < r;
  if (a) l = r;
  return a;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &it : v) is >> it;
  return is;
}
class range {
 private:
  struct I {
    int x;
    int operator*() { return x; }
    bool operator!=(I &lhs) { return x < lhs.x; }
    void operator++() { ++x; }
  };
  I i, n;

 public:
  range(int n) : i({0}), n({n}) {}
  range(int i, int n) : i({i}), n({n}) {}
  I &begin() { return i; }
  I &end() { return n; }
};
namespace latte {
void create_begin_bucket(vector<int> &v, vector<int> &bucket) {
  fill(bucket.begin(), bucket.end(), 0);
  for (int i = 0; i < (int)v.size(); i++) bucket[v[i]]++;
  int sum = 0;
  for (int i = 0; i < (int)bucket.size(); i++) {
    bucket[i] += sum;
    swap(sum, bucket[i]);
  }
}
void create_end_bucket(vector<int> &v, vector<int> &bucket) {
  fill(bucket.begin(), bucket.end(), 0);
  for (int i = 0; i < (int)v.size(); i++) bucket[v[i]]++;
  for (int i = 1; i < (int)bucket.size(); i++) bucket[i] += bucket[i - 1];
}
void induced_sort(vector<int> &v, vector<int> &sa, int mv, vector<int> &bucket,
                  vector<int> &is_l) {
  create_begin_bucket(v, bucket);
  for (int i = 0; i < (int)v.size(); i++)
    if (sa[i] > 0 && is_l[sa[i] - 1]) sa[bucket[v[sa[i] - 1]]++] = sa[i] - 1;
}
void invert_induced_sort(vector<int> &v, vector<int> &sa, int mv,
                         vector<int> &bucket, vector<int> &is_l) {
  create_end_bucket(v, bucket);
  for (int i = v.size() - 1; i >= 0; i--)
    if (sa[i] > 0 && !is_l[sa[i] - 1]) sa[--bucket[v[sa[i] - 1]]] = sa[i] - 1;
}
vector<int> sa_is(vector<int> v, int mv) {
  if (v.size() == 1) return vector<int>(1, 0);
  vector<int> is_l(v.size());
  vector<int> bucket(mv + 1);
  vector<int> sa(v.size(), -1);
  auto is_lms = [&](int x) -> bool { return x > 0 && is_l[x - 1] && !is_l[x]; };
  is_l[v.size() - 1] = 0;
  for (int i = v.size() - 2; i >= 0; i--)
    is_l[i] = v[i] > v[i + 1] || (v[i] == v[i + 1] && is_l[i + 1]);
  create_end_bucket(v, bucket);
  for (int i = 0; i < (int)v.size(); i++)
    if (is_lms(i)) sa[--bucket[v[i]]] = i;
  induced_sort(v, sa, mv, bucket, is_l);
  invert_induced_sort(v, sa, mv, bucket, is_l);
  int cur = 0;
  vector<int> order(v.size());
  for (int i = 0; i < (int)v.size(); i++)
    if (is_lms(i)) order[i] = cur++;
  vector<int> next_v(cur);
  cur = -1;
  int prev = -1;
  for (int i = 0; i < (int)v.size(); i++) {
    if (!is_lms(sa[i])) continue;
    bool diff = false;
    for (int d = 0; d < v.size(); d++) {
      if (prev == -1 || v[sa[i] + d] != v[prev + d] ||
          is_l[sa[i] + d] != is_l[prev + d]) {
        diff = true;
        break;
      } else if (d > 0 && is_lms(sa[i] + d))
        break;
    }
    if (diff) {
      cur++;
      prev = sa[i];
    }
    next_v[order[sa[i]]] = cur;
  }
  vector<int> re_order(next_v.size());
  for (int i = 0; i < (int)v.size(); i++)
    if (is_lms(i)) re_order[order[i]] = i;
  vector<int> next_sa = sa_is(next_v, cur);
  create_end_bucket(v, bucket);
  for (int i = 0; i < sa.size(); i++) sa[i] = -1;
  for (int i = next_sa.size() - 1; i >= 0; i--)
    sa[--bucket[v[re_order[next_sa[i]]]]] = re_order[next_sa[i]];
  induced_sort(v, sa, mv, bucket, is_l);
  invert_induced_sort(v, sa, mv, bucket, is_l);
  return sa;
}
vector<int> sa_is(string &s) {
  vector<int> v(s.size() + 1);
  for (int i = 0; i < (int)s.size(); i++) v[i] = s[i];
  return sa_is(v, *max_element(v.begin(), v.end()));
}
}  // namespace latte
namespace SA {
int n, k;
int R[1123456];
int T[1123456];
bool compare_sa(int i, int j) {
  if (R[i] != R[j])
    return R[i] < R[j];
  else {
    int ri = i + k <= n ? R[i + k] : -1;
    int rj = j + k <= n ? R[j + k] : -1;
    return ri < rj;
  }
}
vector<int> construct_sa(string &S) { return latte::sa_is(S); }
vector<int> construct_lcp(string &S, vector<int> &sa) {
  n = S.size();
  for (int i = 0; i <= n; i++) R[sa[i]] = i;
  int h = 0;
  vector<int> lcp(n + 1, 0);
  for (int i = 0; i < n; i++) {
    int j = sa[R[i] - 1];
    if (h > 0) h--;
    for (; j + h < n && i + h < n; h++) {
      if (S[j + h] != S[i + h]) break;
    }
    lcp[R[i] - 1] = h;
  }
  return lcp;
}
}  // namespace SA
using namespace std;
constexpr int INF = 1e7;
template <typename SEG>
using SetInitialLeaf = function<void(SEG &, int)>;
template <typename SEG>
using SetInitialSegment = function<void(SEG &, const int, const int)>;
template <typename RET, typename SEG>
using GetSingleSegment = function<RET(SEG &, const int, const int)>;
template <typename RET>
using GetMergedSegment = function<RET(RET, RET)>;
template <typename SEG, typename Q>
using UpdateSingleSegment = function<void(SEG &, Q)>;
template <typename SEG>
using LazyUpdate = function<void(SEG &, SEG &, SEG &)>;
struct node {
  int ret;
};
int a[1123456];
SetInitialLeaf<node> set_leaf = [](node &v, const int id) { v.ret = a[id]; };
SetInitialSegment<node> set_segment = [](node &v, const int l, const int r) {};
GetSingleSegment<int, node> segment_min = [](node &v, const int l,
                                             const int r) { return v.ret; };
GetMergedSegment<int> merge_segment = [](int l, int r) {
  return l < r ? l : r;
};
UpdateSingleSegment<node, int> force_update = [](node &v, int l) { v.ret = l; };
UpdateSingleSegment<node, int> weak_update = [](node &v, int l) {
  if (v.ret > l) v.ret = l;
};
template <typename T>
struct BufferManager {
  T *mem;
  int ptr;
  BufferManager(T *mem) {
    ptr = 0;
    this->mem = mem;
  }
  T *get(int m) {
    ptr += m;
    return mem + ptr - m;
  }
  void reset() { ptr = 0; }
};
namespace NodeBuffer {
constexpr int BufferSize = 4123456;
using NodeType = node;
NodeType mem[BufferSize];
BufferManager<NodeType> buffer(mem);
}  // namespace NodeBuffer
template <typename Node, typename RET>
struct SegmentTree {
  int size;
  Node *seg;
  GetSingleSegment<RET, Node> get_single_segment;
  GetMergedSegment<RET> get_merged_segment;
  LazyUpdate<Node> lazy_update;
  void init(int l, int r, SetInitialSegment<Node> &init_segment,
            SetInitialLeaf<Node> &init_leaf, int k = 0) {
    auto &v = seg[k];
    init_segment(v, l, r);
    if (r - l == 1) {
      init_leaf(v, l);
    } else if (r - l > 1) {
      int m = (l + r) / 2;
      init(l, m, init_segment, init_leaf, k * 2 + 1);
      init(m, r, init_segment, init_leaf, k * 2 + 2);
      v.ret = get_merged_segment(get_single_segment(seg[k * 2 + 1], l, m),
                                 get_single_segment(seg[k * 2 + 2], m, r));
    }
  }
  SegmentTree(
      int n, GetSingleSegment<RET, Node> gss, GetMergedSegment<RET> gms,
      SetInitialSegment<Node> sis, SetInitialLeaf<Node> sil,
      LazyUpdate<Node> lu = [](Node &v, Node &l, Node &r) {},
      BufferManager<Node> &buf = NodeBuffer::buffer)
      : get_single_segment(gss), get_merged_segment(gms), lazy_update(lu) {
    size = 1;
    while (size < n) size *= 2;
    seg = buf.get(size * 2 + 10);
    init(0, size, sis, sil);
  }
  RET get(int a, int b, int k, int l, int r) {
    if (a <= l && r <= b) return get_single_segment(seg[k], l, r);
    int m = (l + r) / 2;
    bool ll = !(m <= a || b <= l);
    bool rr = !(r <= a || b <= m);
    RET ret;
    if (ll && rr)
      ret = get_merged_segment(get(a, b, k * 2 + 1, l, m),
                               get(a, b, k * 2 + 2, m, r));
    else if (ll)
      ret = get(a, b, k * 2 + 1, l, m);
    else
      ret = get(a, b, k * 2 + 2, m, r);
    return ret;
  }
  RET get(int a, int b) { return get(a, b, 0, 0, size); }
  template <typename Q>
  void update(int a, int b, int k, int l, int r,
              UpdateSingleSegment<Node, Q> &update_segment, Q value) {
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      update_segment(seg[k], value);
    } else {
      if (r - l > 1) lazy_update(seg[k], seg[2 * k + 1], seg[2 * k + 2]);
      int m = (l + r) / 2;
      update(a, b, k * 2 + 1, l, m, update_segment, value);
      update(a, b, k * 2 + 2, m, r, update_segment, value);
      seg[k].ret = get_merged_segment(get_single_segment(seg[k * 2 + 1], l, m),
                                      get_single_segment(seg[k * 2 + 2], m, r));
    }
  }
  template <typename Q>
  void update_segment(int a, int b,
                      UpdateSingleSegment<Node, Q> &update_segment, Q value) {
    update(a, b, 0, 0, size, update_segment, value);
  }
  template <typename Q>
  void update_element(int a, UpdateSingleSegment<Node, Q> &update_segment,
                      Q value) {
    update(a, a + 1, 0, 0, size, update_segment, value);
  }
};
int id[1123456];
int main() {
  int n;
  string s;
  cin >> n >> s;
  int loop = (n + 1) / 2;
  string t(loop, ' ');
  t.back() = '\n';
  auto sa = SA::construct_sa(s);
  auto lcp = SA::construct_lcp(s, sa);
  for (int i : range(lcp.size())) a[i] = lcp[i];
  for (int i : range(sa.size())) {
    id[sa[i]] = i;
  }
  SegmentTree<node, int> rmq(lcp.size(), segment_min, merge_segment,
                             set_segment, set_leaf);
  auto check = [&](int l, int r, int len) {
    l = id[l];
    r = id[r];
    if (l > r) swap(l, r);
    return rmq.get(l, r) >= len;
  };
  vector<int> ret(loop, -1);
  for (int i : range(n / 2)) {
    int j = n - 1 - i;
    if (s[i] != s[j]) continue;
    int lb = 0;
    int ub = i + 1;
    while (ub - lb > 1) {
      const int mid = (lb + ub) / 2;
      (check(i - mid, j - mid, mid * 2 + 1) ? lb : ub) = mid;
    }
    chmax(ret[i - lb], lb * 2 + 1);
  }
  for (int i : range(1, loop)) chmax(ret[i], ret[i - 1] - 2);
  for (int i : range(loop)) cout << ret[i] << t[i];
  return 0;
}

### Prompt

Your task is to create a Cpp solution to the following problem:

You are given a string s consisting of n lowercase Latin letters.

Let's denote k-substring of s as a string subsk = sksk + 1..sn + 1 - k. Obviously, subs1 = s, and there are exactly <image> such substrings.

Let's call some string t an odd proper suprefix of a string T iff the following conditions are met:

  * |T| > |t|; 
  * |t| is an odd number; 
  * t is simultaneously a prefix and a suffix of T.



For evey k-substring (<image>) of s you have to calculate the maximum length of its odd proper suprefix.

Input

The first line contains one integer n (2 ≤ n ≤ 106) — the length s.

The second line contains the string s consisting of n lowercase Latin letters.

Output

Print <image> integers. i-th of them should be equal to maximum length of an odd proper suprefix of i-substring of s (or  - 1, if there is no such string that is an odd proper suprefix of i-substring).

Examples

Input

15
bcabcabcabcabca


Output

9 7 5 3 1 -1 -1 -1


Input

24
abaaabaaaabaaabaaaabaaab


Output

15 13 11 9 7 5 3 1 1 -1 -1 1


Input

19
cabcabbcabcabbcabca


Output

5 3 1 -1 -1 1 1 -1 -1 -1

Note

The answer for first sample test is folowing: 

  * 1-substring: bcabcabcabcabca
  * 2-substring: cabcabcabcabc
  * 3-substring: abcabcabcab
  * 4-substring: bcabcabca
  * 5-substring: cabcabc
  * 6-substring: abcab 
  * 7-substring: bca 
  * 8-substring: c 

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct cww {
  cww() {
    if (1) {
      ios::sync_with_stdio(false);
      cin.tie(0);
    }
  }
} star;
template <typename T>
inline bool chmin(T &l, T r) {
  bool a = l > r;
  if (a) l = r;
  return a;
}
template <typename T>
inline bool chmax(T &l, T r) {
  bool a = l < r;
  if (a) l = r;
  return a;
}
template <typename T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto &it : v) is >> it;
  return is;
}
class range {
 private:
  struct I {
    int x;
    int operator*() { return x; }
    bool operator!=(I &lhs) { return x < lhs.x; }
    void operator++() { ++x; }
  };
  I i, n;

 public:
  range(int n) : i({0}), n({n}) {}
  range(int i, int n) : i({i}), n({n}) {}
  I &begin() { return i; }
  I &end() { return n; }
};
namespace latte {
void create_begin_bucket(vector<int> &v, vector<int> &bucket) {
  fill(bucket.begin(), bucket.end(), 0);
  for (int i = 0; i < (int)v.size(); i++) bucket[v[i]]++;
  int sum = 0;
  for (int i = 0; i < (int)bucket.size(); i++) {
    bucket[i] += sum;
    swap(sum, bucket[i]);
  }
}
void create_end_bucket(vector<int> &v, vector<int> &bucket) {
  fill(bucket.begin(), bucket.end(), 0);
  for (int i = 0; i < (int)v.size(); i++) bucket[v[i]]++;
  for (int i = 1; i < (int)bucket.size(); i++) bucket[i] += bucket[i - 1];
}
void induced_sort(vector<int> &v, vector<int> &sa, int mv, vector<int> &bucket,
                  vector<int> &is_l) {
  create_begin_bucket(v, bucket);
  for (int i = 0; i < (int)v.size(); i++)
    if (sa[i] > 0 && is_l[sa[i] - 1]) sa[bucket[v[sa[i] - 1]]++] = sa[i] - 1;
}
void invert_induced_sort(vector<int> &v, vector<int> &sa, int mv,
                         vector<int> &bucket, vector<int> &is_l) {
  create_end_bucket(v, bucket);
  for (int i = v.size() - 1; i >= 0; i--)
    if (sa[i] > 0 && !is_l[sa[i] - 1]) sa[--bucket[v[sa[i] - 1]]] = sa[i] - 1;
}
vector<int> sa_is(vector<int> v, int mv) {
  if (v.size() == 1) return vector<int>(1, 0);
  vector<int> is_l(v.size());
  vector<int> bucket(mv + 1);
  vector<int> sa(v.size(), -1);
  auto is_lms = [&](int x) -> bool { return x > 0 && is_l[x - 1] && !is_l[x]; };
  is_l[v.size() - 1] = 0;
  for (int i = v.size() - 2; i >= 0; i--)
    is_l[i] = v[i] > v[i + 1] || (v[i] == v[i + 1] && is_l[i + 1]);
  create_end_bucket(v, bucket);
  for (int i = 0; i < (int)v.size(); i++)
    if (is_lms(i)) sa[--bucket[v[i]]] = i;
  induced_sort(v, sa, mv, bucket, is_l);
  invert_induced_sort(v, sa, mv, bucket, is_l);
  int cur = 0;
  vector<int> order(v.size());
  for (int i = 0; i < (int)v.size(); i++)
    if (is_lms(i)) order[i] = cur++;
  vector<int> next_v(cur);
  cur = -1;
  int prev = -1;
  for (int i = 0; i < (int)v.size(); i++) {
    if (!is_lms(sa[i])) continue;
    bool diff = false;
    for (int d = 0; d < v.size(); d++) {
      if (prev == -1 || v[sa[i] + d] != v[prev + d] ||
          is_l[sa[i] + d] != is_l[prev + d]) {
        diff = true;
        break;
      } else if (d > 0 && is_lms(sa[i] + d))
        break;
    }
    if (diff) {
      cur++;
      prev = sa[i];
    }
    next_v[order[sa[i]]] = cur;
  }
  vector<int> re_order(next_v.size());
  for (int i = 0; i < (int)v.size(); i++)
    if (is_lms(i)) re_order[order[i]] = i;
  vector<int> next_sa = sa_is(next_v, cur);
  create_end_bucket(v, bucket);
  for (int i = 0; i < sa.size(); i++) sa[i] = -1;
  for (int i = next_sa.size() - 1; i >= 0; i--)
    sa[--bucket[v[re_order[next_sa[i]]]]] = re_order[next_sa[i]];
  induced_sort(v, sa, mv, bucket, is_l);
  invert_induced_sort(v, sa, mv, bucket, is_l);
  return sa;
}
vector<int> sa_is(string &s) {
  vector<int> v(s.size() + 1);
  for (int i = 0; i < (int)s.size(); i++) v[i] = s[i];
  return sa_is(v, *max_element(v.begin(), v.end()));
}
}  // namespace latte
namespace SA {
int n, k;
int R[1123456];
int T[1123456];
bool compare_sa(int i, int j) {
  if (R[i] != R[j])
    return R[i] < R[j];
  else {
    int ri = i + k <= n ? R[i + k] : -1;
    int rj = j + k <= n ? R[j + k] : -1;
    return ri < rj;
  }
}
vector<int> construct_sa(string &S) { return latte::sa_is(S); }
vector<int> construct_lcp(string &S, vector<int> &sa) {
  n = S.size();
  for (int i = 0; i <= n; i++) R[sa[i]] = i;
  int h = 0;
  vector<int> lcp(n + 1, 0);
  for (int i = 0; i < n; i++) {
    int j = sa[R[i] - 1];
    if (h > 0) h--;
    for (; j + h < n && i + h < n; h++) {
      if (S[j + h] != S[i + h]) break;
    }
    lcp[R[i] - 1] = h;
  }
  return lcp;
}
}  // namespace SA
using namespace std;
constexpr int INF = 1e7;
template <typename SEG>
using SetInitialLeaf = function<void(SEG &, int)>;
template <typename SEG>
using SetInitialSegment = function<void(SEG &, const int, const int)>;
template <typename RET, typename SEG>
using GetSingleSegment = function<RET(SEG &, const int, const int)>;
template <typename RET>
using GetMergedSegment = function<RET(RET, RET)>;
template <typename SEG, typename Q>
using UpdateSingleSegment = function<void(SEG &, Q)>;
template <typename SEG>
using LazyUpdate = function<void(SEG &, SEG &, SEG &)>;
struct node {
  int ret;
};
int a[1123456];
SetInitialLeaf<node> set_leaf = [](node &v, const int id) { v.ret = a[id]; };
SetInitialSegment<node> set_segment = [](node &v, const int l, const int r) {};
GetSingleSegment<int, node> segment_min = [](node &v, const int l,
                                             const int r) { return v.ret; };
GetMergedSegment<int> merge_segment = [](int l, int r) {
  return l < r ? l : r;
};
UpdateSingleSegment<node, int> force_update = [](node &v, int l) { v.ret = l; };
UpdateSingleSegment<node, int> weak_update = [](node &v, int l) {
  if (v.ret > l) v.ret = l;
};
template <typename T>
struct BufferManager {
  T *mem;
  int ptr;
  BufferManager(T *mem) {
    ptr = 0;
    this->mem = mem;
  }
  T *get(int m) {
    ptr += m;
    return mem + ptr - m;
  }
  void reset() { ptr = 0; }
};
namespace NodeBuffer {
constexpr int BufferSize = 4123456;
using NodeType = node;
NodeType mem[BufferSize];
BufferManager<NodeType> buffer(mem);
}  // namespace NodeBuffer
template <typename Node, typename RET>
struct SegmentTree {
  int size;
  Node *seg;
  GetSingleSegment<RET, Node> get_single_segment;
  GetMergedSegment<RET> get_merged_segment;
  LazyUpdate<Node> lazy_update;
  void init(int l, int r, SetInitialSegment<Node> &init_segment,
            SetInitialLeaf<Node> &init_leaf, int k = 0) {
    auto &v = seg[k];
    init_segment(v, l, r);
    if (r - l == 1) {
      init_leaf(v, l);
    } else if (r - l > 1) {
      int m = (l + r) / 2;
      init(l, m, init_segment, init_leaf, k * 2 + 1);
      init(m, r, init_segment, init_leaf, k * 2 + 2);
      v.ret = get_merged_segment(get_single_segment(seg[k * 2 + 1], l, m),
                                 get_single_segment(seg[k * 2 + 2], m, r));
    }
  }
  SegmentTree(
      int n, GetSingleSegment<RET, Node> gss, GetMergedSegment<RET> gms,
      SetInitialSegment<Node> sis, SetInitialLeaf<Node> sil,
      LazyUpdate<Node> lu = [](Node &v, Node &l, Node &r) {},
      BufferManager<Node> &buf = NodeBuffer::buffer)
      : get_single_segment(gss), get_merged_segment(gms), lazy_update(lu) {
    size = 1;
    while (size < n) size *= 2;
    seg = buf.get(size * 2 + 10);
    init(0, size, sis, sil);
  }
  RET get(int a, int b, int k, int l, int r) {
    if (a <= l && r <= b) return get_single_segment(seg[k], l, r);
    int m = (l + r) / 2;
    bool ll = !(m <= a || b <= l);
    bool rr = !(r <= a || b <= m);
    RET ret;
    if (ll && rr)
      ret = get_merged_segment(get(a, b, k * 2 + 1, l, m),
                               get(a, b, k * 2 + 2, m, r));
    else if (ll)
      ret = get(a, b, k * 2 + 1, l, m);
    else
      ret = get(a, b, k * 2 + 2, m, r);
    return ret;
  }
  RET get(int a, int b) { return get(a, b, 0, 0, size); }
  template <typename Q>
  void update(int a, int b, int k, int l, int r,
              UpdateSingleSegment<Node, Q> &update_segment, Q value) {
    if (r <= a || b <= l) return;
    if (a <= l && r <= b) {
      update_segment(seg[k], value);
    } else {
      if (r - l > 1) lazy_update(seg[k], seg[2 * k + 1], seg[2 * k + 2]);
      int m = (l + r) / 2;
      update(a, b, k * 2 + 1, l, m, update_segment, value);
      update(a, b, k * 2 + 2, m, r, update_segment, value);
      seg[k].ret = get_merged_segment(get_single_segment(seg[k * 2 + 1], l, m),
                                      get_single_segment(seg[k * 2 + 2], m, r));
    }
  }
  template <typename Q>
  void update_segment(int a, int b,
                      UpdateSingleSegment<Node, Q> &update_segment, Q value) {
    update(a, b, 0, 0, size, update_segment, value);
  }
  template <typename Q>
  void update_element(int a, UpdateSingleSegment<Node, Q> &update_segment,
                      Q value) {
    update(a, a + 1, 0, 0, size, update_segment, value);
  }
};
int id[1123456];
int main() {
  int n;
  string s;
  cin >> n >> s;
  int loop = (n + 1) / 2;
  string t(loop, ' ');
  t.back() = '\n';
  auto sa = SA::construct_sa(s);
  auto lcp = SA::construct_lcp(s, sa);
  for (int i : range(lcp.size())) a[i] = lcp[i];
  for (int i : range(sa.size())) {
    id[sa[i]] = i;
  }
  SegmentTree<node, int> rmq(lcp.size(), segment_min, merge_segment,
                             set_segment, set_leaf);
  auto check = [&](int l, int r, int len) {
    l = id[l];
    r = id[r];
    if (l > r) swap(l, r);
    return rmq.get(l, r) >= len;
  };
  vector<int> ret(loop, -1);
  for (int i : range(n / 2)) {
    int j = n - 1 - i;
    if (s[i] != s[j]) continue;
    int lb = 0;
    int ub = i + 1;
    while (ub - lb > 1) {
      const int mid = (lb + ub) / 2;
      (check(i - mid, j - mid, mid * 2 + 1) ? lb : ub) = mid;
    }
    chmax(ret[i - lb], lb * 2 + 1);
  }
  for (int i : range(1, loop)) chmax(ret[i], ret[i - 1] - 2);
  for (int i : range(loop)) cout << ret[i] << t[i];
  return 0;
}

```