Just in case somebody missed it: we have wonderful girls in Arpa’s land.

Arpa has a rooted tree (connected acyclic graph) consisting of n vertices. The vertices are numbered 1 through n, the vertex 1 is the root. There is a letter written on each edge of this tree. Mehrdad is a fan of Dokhtar-kosh things. He call a string Dokhtar-kosh, if we can shuffle the characters in string such that it becomes palindrome.

<image>

He asks Arpa, for each vertex v, what is the length of the longest simple path in subtree of v that form a Dokhtar-kosh string.

Input

The first line contains integer n (1 ≤ n ≤ 5·105) — the number of vertices in the tree.

(n - 1) lines follow, the i-th of them contain an integer pi + 1 and a letter ci + 1 (1 ≤ pi + 1 ≤ i, ci + 1 is lowercase English letter, between a and v, inclusively), that mean that there is an edge between nodes pi + 1 and i + 1 and there is a letter ci + 1 written on this edge.

Output

Print n integers. The i-th of them should be the length of the longest simple path in subtree of the i-th vertex that form a Dokhtar-kosh string.

Examples

Input

4
1 s
2 a
3 s


Output

3 1 1 0 

Input

5
1 a
2 h
1 a
4 h


Output

4 1 0 1 0 
#include <bits/stdc++.h>
using namespace std;
long long modpow(long long b, long long e, long long mod) {
  long long ans = 1;
  for (; e; b = b * b % mod, e /= 2)
    if (e & 1) ans = ans * b % mod;
  return ans;
}
const int N = 500005;
int sz[N], d[N], mask[N], n;
vector<pair<int, int> > g[N];
int f[1 << 22];
int ans[N], in[N], out[N], tin = 0, old[N], rin[N];
void process(int x, int p = -1, int msk = 0, int dep = 0) {
  sz[x] = 1, mask[x] = msk, d[x] = dep;
  for (auto& w : g[x]) {
    if (w.first == p) continue;
    process(w.first, x, msk ^ (1 << w.second), dep + 1);
    sz[x] += sz[w.first];
    if (g[x][0].first == p || sz[w.first] > sz[g[x][0].first]) swap(g[x][0], w);
  }
}
void ett(int x, int p = -1) {
  in[x] = ++tin;
  rin[in[x]] = x;
  for (auto w : g[x]) {
    if (w.first == p) continue;
    ett(w.first, x);
  }
  out[x] = tin;
}
void dfs(int x, int p = -1, bool keep = 1) {
  for (auto w : g[x]) {
    if (w.first == p || w.first == g[x][0].first) continue;
    dfs(w.first, x, 0);
    ans[x] = max(ans[x], ans[w.first]);
  }
  if ((int)(g[x]).size() && g[x][0].first != p)
    dfs(g[x][0].first, x, 1), ans[x] = max(ans[x], ans[g[x][0].first]);
  for (auto w : g[x]) {
    if (w.first == p || w.first == g[x][0].first) continue;
    for (int i = in [w.first]; i <= out[w.first]; i++) {
      int ms = mask[rin[i]];
      if (f[ms] >= 0) ans[x] = max(ans[x], f[ms] + d[rin[i]] - 2 * d[x]);
      for (int j = 0; j < 22; j++) {
        if (f[ms ^ (1 << j)] >= 0)
          ans[x] = max(ans[x], f[ms ^ (1 << j)] + d[rin[i]] - 2 * d[x]);
      }
    }
    for (int i = in [w.first]; i <= out[w.first]; i++) {
      int ms = mask[rin[i]];
      f[ms] = max(f[ms], d[rin[i]]);
    }
  }
  int ms = mask[x];
  f[ms] = max(f[ms], d[x]);
  ans[x] = max(ans[x], f[ms] - d[x]);
  for (int j = 0; j < 22; j++) {
    if (f[ms ^ (1 << j)] >= 0) ans[x] = max(ans[x], f[ms ^ (1 << j)] - d[x]);
  }
  if (!keep) {
    for (int i = in[x]; i <= out[x]; i++) {
      f[mask[rin[i]]] = -1;
    }
  }
}
int32_t main() {
  for (int i = 0; i < (1 << 22); ++i) f[i] = -1;
  ios::sync_with_stdio(!cin.tie(0));
  cin >> n;
  for (int i = 2; i <= n; i++) {
    int p;
    char c;
    cin >> p >> c;
    g[p].push_back({i, (int)c - 'a'});
    g[i].push_back({p, (int)c - 'a'});
  }
  process(1);
  ett(1);
  dfs(1);
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
}
