#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const long long MOD1 = 1000000007;
const int INF = 1000000007;
const long long LINF = 1LL * INF * INF;
const int MAXN = 1000047;
const double EPS = 1e-6;
const double PI = acos(-1.0);
const int P = 47;
const int MOD2 = 1000000009;
string S;
set<int> Se;
pair<long long, long long> PP[MAXN], H[MAXN];
vector<int> ANS;
pair<long long, long long> operator+(pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return make_pair((a.first + b.first) % MOD1, (a.second + b.second) % MOD2);
}
pair<long long, long long> operator-(pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return make_pair(((a.first - b.first) % MOD1 + MOD1) % MOD1,
                   ((a.second - b.second) % MOD2 + MOD2) % MOD2);
}
pair<long long, long long> operator*(long long a,
                                     pair<long long, long long> p) {
  return make_pair((a * p.first) % MOD1, (a * p.second) % MOD2);
}
pair<long long, long long> operator*(pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return make_pair((a.first * b.first) % MOD1, (a.second * b.second) % MOD2);
}
bool eq(int l1, int r1, int l2, int r2) {
  return PP[l2 - l1] * (H[r1] - H[l1 - 1]) == H[r2] - H[l2 - 1];
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n;
  cin >> n >> S;
  reverse(S.begin(), S.end());
  S.push_back('#');
  reverse(S.begin(), S.end());
  PP[0] = make_pair(1, 1);
  for (int i = (1); i < (n + 1); ++i) PP[i] = P * PP[i - 1];
  for (int i = (1); i < (n + 1); ++i)
    H[i] = H[i - 1] + (S[i] - 'a' + 1) * PP[i];
  for (int k = (n + 1) >> 1; k >= 1; --k) {
    while (!Se.empty() &&
           !eq(k, -2 * *Se.begin() - k, n + 1 + k + 2 * *Se.begin(), n + 1 - k))
      Se.erase(Se.begin());
    if (S[k] == S[n + 1 - k] && 2 * k != n + 1) Se.insert(-k);
    ANS.push_back(Se.empty() ? -1 : 2 * (-*Se.begin() - k) + 1);
  }
  for (int i = ((int)((ANS).size())) - 1; i >= (0); --i) cout << ANS[i] << ' ';
  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>
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
using namespace std;
const long long MOD1 = 1000000007;
const int INF = 1000000007;
const long long LINF = 1LL * INF * INF;
const int MAXN = 1000047;
const double EPS = 1e-6;
const double PI = acos(-1.0);
const int P = 47;
const int MOD2 = 1000000009;
string S;
set<int> Se;
pair<long long, long long> PP[MAXN], H[MAXN];
vector<int> ANS;
pair<long long, long long> operator+(pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return make_pair((a.first + b.first) % MOD1, (a.second + b.second) % MOD2);
}
pair<long long, long long> operator-(pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return make_pair(((a.first - b.first) % MOD1 + MOD1) % MOD1,
                   ((a.second - b.second) % MOD2 + MOD2) % MOD2);
}
pair<long long, long long> operator*(long long a,
                                     pair<long long, long long> p) {
  return make_pair((a * p.first) % MOD1, (a * p.second) % MOD2);
}
pair<long long, long long> operator*(pair<long long, long long> a,
                                     pair<long long, long long> b) {
  return make_pair((a.first * b.first) % MOD1, (a.second * b.second) % MOD2);
}
bool eq(int l1, int r1, int l2, int r2) {
  return PP[l2 - l1] * (H[r1] - H[l1 - 1]) == H[r2] - H[l2 - 1];
}
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int n;
  cin >> n >> S;
  reverse(S.begin(), S.end());
  S.push_back('#');
  reverse(S.begin(), S.end());
  PP[0] = make_pair(1, 1);
  for (int i = (1); i < (n + 1); ++i) PP[i] = P * PP[i - 1];
  for (int i = (1); i < (n + 1); ++i)
    H[i] = H[i - 1] + (S[i] - 'a' + 1) * PP[i];
  for (int k = (n + 1) >> 1; k >= 1; --k) {
    while (!Se.empty() &&
           !eq(k, -2 * *Se.begin() - k, n + 1 + k + 2 * *Se.begin(), n + 1 - k))
      Se.erase(Se.begin());
    if (S[k] == S[n + 1 - k] && 2 * k != n + 1) Se.insert(-k);
    ANS.push_back(Se.empty() ? -1 : 2 * (-*Se.begin() - k) + 1);
  }
  for (int i = ((int)((ANS).size())) - 1; i >= (0); --i) cout << ANS[i] << ' ';
  return 0;
}

```