#include <bits/stdc++.h>
using namespace std;
template <typename T>
istream& operator>>(istream& is, vector<T>& a) {
  for (T& ai : a) is >> ai;
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> const& a) {
  os << "[ ";
  for (const T& ai : a) os << ai << " ";
  return os << "]";
}
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& a) {
  return is >> a.first >> a.second;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2> const& a) {
  return os << "(" << a.first << ", " << a.second << ")";
}
class RMQ {
 public:
  RMQ(vector<int> const& a) : _a(a) {
    for (int t = 0, m = 2, n = a.size(); m <= n; ++t, m <<= 1) {
      _rmq.emplace_back(n - m + 1);
      for (int i = 0; i + m <= n; ++i) {
        int r0 = t ? _rmq[t - 1][i] : i;
        int r1 = t ? _rmq[t - 1][i + (1 << t)] : i + 1;
        _rmq[t][i] = _a[r0] < _a[r1] ? r0 : r1;
      }
    }
  }
  int query(int i, int j) const {
    if (j > _a.size()) j = _a.size();
    if (j <= i) return -1;
    int n = j - i;
    if (n == 1) return i;
    int t = 30 - __builtin_clz(n);
    int r0 = _rmq[t][i], r1 = _rmq[t][j - (1 << (1 + t))];
    return _a[r0] < _a[r1] ? r0 : r1;
  }

 private:
  vector<int> const& _a;
  vector<vector<int> > _rmq;
};
class SA {
 public:
  SA(const string& s) : _s(s) {
    compute_suf();
    compute_lcp();
  }
  ~SA() {
    if (_rmq) delete _rmq;
  }
  int lcp(int i, int j) const {
    if (i == j) return _s.size() - i;
    i = _sufinv[i];
    j = _sufinv[j];
    if (i > j) swap(i, j);
    if (i + 1 == j) return _lcp[i];
    return _lcp[_rmq->query(i, j)];
  }

 private:
  struct entry_t {
    int a, b, i;
    bool operator<(const entry_t& rhs) const {
      return (a < rhs.a) || (a == rhs.a && b < rhs.b);
    }
  };
  void compute_suf() {
    int n = _s.size();
    vector<entry_t> suf(n + 1);
    vector<int> idx(n + 1);
    for (int i = 0; i <= n; ++i) {
      suf[i].a = i < n ? _s[i] : -1;
      suf[i].b = i + 1 < n ? _s[i + 1] : -1;
      suf[i].i = i;
    }
    sort(suf.begin(), suf.end());
    int t = 2;
    while (t <= n) {
      for (int i = 0, r = 0, p = suf[0].a; i <= n; ++i) {
        idx[suf[i].i] = i;
        if (suf[i].a != p || suf[i].b != suf[i - 1].b) ++r;
        p = suf[i].a;
        suf[i].a = r;
      }
      int j = 0;
      for (int i = 0; i <= n; ++i) {
        if (suf[i].a != suf[j].a) {
          sort(suf.begin() + j, suf.begin() + i);
          j = i;
        }
        int k = suf[i].i + t;
        suf[i].b = k > n ? -1 : suf[idx[k]].a;
      }
      sort(suf.begin() + j, suf.end());
      t <<= 1;
    }
    _suf.resize(n + 1);
    for (int i = 0; i <= n; ++i) _suf[i] = suf[i].i;
  }
  void compute_lcp() {
    int n = _s.size();
    _sufinv.resize(n + 1);
    for (int i = 0; i <= n; ++i) _sufinv[_suf[i]] = i;
    _lcp.resize(n + 1);
    int k = 0;
    for (int i = 0, j; i <= n; ++i) {
      if (_sufinv[i] == n) {
        k = 0;
        continue;
      }
      j = _suf[_sufinv[i] + 1];
      while (i + k < n && j + k < n && _s[i + k] == _s[j + k]) ++k;
      _lcp[_sufinv[i]] = k;
      if (k) --k;
    }
    _rmq = new RMQ(_lcp);
  }

 private:
  const string& _s;
  vector<int> _suf, _sufinv, _lcp;
  RMQ* _rmq;
};
void f() {
  int n;
  string s;
  cin >> n >> s;
  SA sa(s);
  vector<int> r(n >> 1, -1);
  for (int i = 0, j = n - 1; i < j; ++i, --j) {
    if (s[i] != s[j]) continue;
    int a = 0, b = i + 1;
    while (a + 1 < b) {
      int c = (a + b) >> 1;
      if (sa.lcp(i - c, j - c) >= 2 * c + 1)
        a = c;
      else
        b = c;
    }
    r[i - a] = max(r[i - a], 2 * a + 1);
  }
  for (int i = 0; i < n >> 1; ++i) {
    if (i) r[i] = max(r[i], r[i - 1] - 2);
    cout << r[i] << " ";
  }
  if (n & 1) cout << "-1";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  f();
  return 0;
}

### Prompt

In cpp, your task is to solve 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;
template <typename T>
istream& operator>>(istream& is, vector<T>& a) {
  for (T& ai : a) is >> ai;
  return is;
}
template <typename T>
ostream& operator<<(ostream& os, vector<T> const& a) {
  os << "[ ";
  for (const T& ai : a) os << ai << " ";
  return os << "]";
}
template <typename T1, typename T2>
istream& operator>>(istream& is, pair<T1, T2>& a) {
  return is >> a.first >> a.second;
}
template <typename T1, typename T2>
ostream& operator<<(ostream& os, pair<T1, T2> const& a) {
  return os << "(" << a.first << ", " << a.second << ")";
}
class RMQ {
 public:
  RMQ(vector<int> const& a) : _a(a) {
    for (int t = 0, m = 2, n = a.size(); m <= n; ++t, m <<= 1) {
      _rmq.emplace_back(n - m + 1);
      for (int i = 0; i + m <= n; ++i) {
        int r0 = t ? _rmq[t - 1][i] : i;
        int r1 = t ? _rmq[t - 1][i + (1 << t)] : i + 1;
        _rmq[t][i] = _a[r0] < _a[r1] ? r0 : r1;
      }
    }
  }
  int query(int i, int j) const {
    if (j > _a.size()) j = _a.size();
    if (j <= i) return -1;
    int n = j - i;
    if (n == 1) return i;
    int t = 30 - __builtin_clz(n);
    int r0 = _rmq[t][i], r1 = _rmq[t][j - (1 << (1 + t))];
    return _a[r0] < _a[r1] ? r0 : r1;
  }

 private:
  vector<int> const& _a;
  vector<vector<int> > _rmq;
};
class SA {
 public:
  SA(const string& s) : _s(s) {
    compute_suf();
    compute_lcp();
  }
  ~SA() {
    if (_rmq) delete _rmq;
  }
  int lcp(int i, int j) const {
    if (i == j) return _s.size() - i;
    i = _sufinv[i];
    j = _sufinv[j];
    if (i > j) swap(i, j);
    if (i + 1 == j) return _lcp[i];
    return _lcp[_rmq->query(i, j)];
  }

 private:
  struct entry_t {
    int a, b, i;
    bool operator<(const entry_t& rhs) const {
      return (a < rhs.a) || (a == rhs.a && b < rhs.b);
    }
  };
  void compute_suf() {
    int n = _s.size();
    vector<entry_t> suf(n + 1);
    vector<int> idx(n + 1);
    for (int i = 0; i <= n; ++i) {
      suf[i].a = i < n ? _s[i] : -1;
      suf[i].b = i + 1 < n ? _s[i + 1] : -1;
      suf[i].i = i;
    }
    sort(suf.begin(), suf.end());
    int t = 2;
    while (t <= n) {
      for (int i = 0, r = 0, p = suf[0].a; i <= n; ++i) {
        idx[suf[i].i] = i;
        if (suf[i].a != p || suf[i].b != suf[i - 1].b) ++r;
        p = suf[i].a;
        suf[i].a = r;
      }
      int j = 0;
      for (int i = 0; i <= n; ++i) {
        if (suf[i].a != suf[j].a) {
          sort(suf.begin() + j, suf.begin() + i);
          j = i;
        }
        int k = suf[i].i + t;
        suf[i].b = k > n ? -1 : suf[idx[k]].a;
      }
      sort(suf.begin() + j, suf.end());
      t <<= 1;
    }
    _suf.resize(n + 1);
    for (int i = 0; i <= n; ++i) _suf[i] = suf[i].i;
  }
  void compute_lcp() {
    int n = _s.size();
    _sufinv.resize(n + 1);
    for (int i = 0; i <= n; ++i) _sufinv[_suf[i]] = i;
    _lcp.resize(n + 1);
    int k = 0;
    for (int i = 0, j; i <= n; ++i) {
      if (_sufinv[i] == n) {
        k = 0;
        continue;
      }
      j = _suf[_sufinv[i] + 1];
      while (i + k < n && j + k < n && _s[i + k] == _s[j + k]) ++k;
      _lcp[_sufinv[i]] = k;
      if (k) --k;
    }
    _rmq = new RMQ(_lcp);
  }

 private:
  const string& _s;
  vector<int> _suf, _sufinv, _lcp;
  RMQ* _rmq;
};
void f() {
  int n;
  string s;
  cin >> n >> s;
  SA sa(s);
  vector<int> r(n >> 1, -1);
  for (int i = 0, j = n - 1; i < j; ++i, --j) {
    if (s[i] != s[j]) continue;
    int a = 0, b = i + 1;
    while (a + 1 < b) {
      int c = (a + b) >> 1;
      if (sa.lcp(i - c, j - c) >= 2 * c + 1)
        a = c;
      else
        b = c;
    }
    r[i - a] = max(r[i - a], 2 * a + 1);
  }
  for (int i = 0; i < n >> 1; ++i) {
    if (i) r[i] = max(r[i], r[i - 1] - 2);
    cout << r[i] << " ";
  }
  if (n & 1) cout << "-1";
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  f();
  return 0;
}

```