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;
const long long mod = 1000000007;
long long powmod(long long a, long long b) {
  long long res = 1;
  a %= mod;
  assert(b >= 0);
  for (; b; b >>= 1) {
    if (b & 1) res = res * a % mod;
    a = a * a % mod;
  }
  return res;
}
const int V = 2000003, N = 500100;
vector<int> s[N];
int sta[V], ky[V];
bitset<(1 << 26) + 10> has;
struct Hash_table {
  int fst[V], nxt[V];
  int T, p;
  void init() {
    T = 1;
    p = 0;
  }
  void insert(int s) {
    int S = s % V, j;
    for (j = fst[S]; j; j = nxt[j])
      if (sta[j] == s) break;
    if (j == 0) {
      nxt[T] = fst[S], fst[S] = T, sta[T] = s, ky[T++] = p++;
    }
  }
  int query(int s) {
    for (int j = fst[s % V]; j; j = nxt[j])
      if (sta[j] == s) return ky[j];
    assert(0);
    return -1;
  }
} Hash;
int n, l[N], r[N], tot, id[N], ret[N], st[N], p;
int Qt[N], Q[N][28], dep[N], sz[N], ms[N];
char c;
struct table {
  int T, mt[N], mv[N];
  void init() { T++; }
  int query(int x) {
    if (mt[x] != T) mt[x] = T, mv[x] = -10000000;
    return mv[x];
  }
  void add(int x, int v) {
    if (mt[x] != T) mt[x] = T, mv[x] = -10000000;
    if (mv[x] < v) mv[x] = v;
  }
} tb[21];
void dfs(int u) {
  sz[u] = 1;
  ms[u] = -1;
  for (auto v : s[u]) {
    dep[v] = dep[u] + 1;
    dfs(v);
    sz[u] += sz[v];
    if (ms[u] == -1 || sz[ms[u]] < sz[v]) ms[u] = v;
  }
}
void solve(int u, int d) {
  assert(d <= 20);
  id[l[u] = ++tot] = u;
  if (ms[u] == -1) {
    tb[d].add(Q[u][0], dep[u]);
    r[u] = tot;
    return;
  }
  for (auto v : s[u])
    if (v != ms[u]) {
      tb[d + 1].init();
      solve(v, d + 1);
      ret[u] = max(ret[u], ret[v]);
    }
  solve(ms[u], d);
  ret[u] = max(ret[u], ret[ms[u]]);
  r[u] = tot;
  int tmp = 0;
  for (auto v : s[u])
    if (v != ms[u]) {
      for (int j = l[v]; j < r[v] + 1; j++) {
        for (int k = 0; k < Qt[id[j]]; k++)
          tmp = max(tmp, tb[d].query(Q[id[j]][k]) + dep[id[j]]);
      }
      for (int j = l[v]; j < r[v] + 1; j++) tb[d].add(Q[id[j]][0], dep[id[j]]);
    }
  for (int k = 0; k < Qt[u]; k++) tmp = max(tmp, tb[d].query(Q[u][k]) + dep[u]);
  tb[d].add(Q[u][0], dep[u]);
  ret[u] = max(ret[u], tmp - 2 * dep[u]);
}
int main() {
  scanf("%d", &n);
  Hash.init();
  Hash.insert(st[1]);
  for (int i = 2; i < n + 1; i++) {
    scanf("%d %c", &p, &c);
    st[i] = st[p] ^ (1 << (c - 'a'));
    s[p].push_back(i);
    has[st[i]] = 1;
    Hash.insert(st[i]);
  }
  for (int i = 1; i < n + 1; i++) {
    Q[i][Qt[i]++] = Hash.query(st[i]);
    for (int j = 0; j < 26; j++)
      if (has[st[i] ^ (1 << j)]) Q[i][Qt[i]++] = Hash.query(st[i] ^ (1 << j));
  }
  dfs(1);
  tb[0].init();
  solve(1, 0);
  for (int i = 1; i < n + 1; i++) printf("%d ", ret[i]);
  puts("");
}
