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;
struct edge {
  long long next, to;
  long long w;
} e[500100 * 2];
long long head[500100], bian;
void add(long long x, long long y, long long w) {
  bian++;
  e[bian].next = head[x], head[x] = bian;
  e[bian].to = y, e[bian].w = w;
}
long long siz[500100], son[500100], f[1 << 22], st[500100], de[500100];
void dfs1(long long x, long long pre, long long dep) {
  long long ma = 0;
  siz[x] = 1, son[x] = -1, de[x] = dep;
  for (long long i = head[x]; i != -1; i = e[i].next) {
    long long y = e[i].to;
    if (y == pre) continue;
    st[y] = st[x] ^ e[i].w;
    dfs1(y, x, dep + 1);
    siz[x] += siz[y];
    if (siz[y] > ma) ma = siz[y], son[x] = y;
  }
}
long long fal;
long long ans[500100];
long long solve(long long x, long long root) {
  long long ma = 0;
  if (f[st[x]] >= 0) ma = f[st[x]] + de[x] - 2 * de[root];
  for (long long i = 0; i <= 21; i++) {
    long long t = st[x] ^ (1 << i);
    if (f[t] >= 0) {
      ma = max(ma, f[st[x] ^ (1 << i)] + de[x] - 2 * de[root]);
    }
  }
  return ma;
}
long long mas;
void dfs3(long long x, long long pre, long long root) {
  mas = max(mas, solve(x, root));
  for (long long i = head[x]; i != -1; i = e[i].next) {
    long long y = e[i].to;
    if (y == pre) continue;
    dfs3(y, x, root);
  }
}
void dfs4(long long x, long long pre, long long dep) {
  f[st[x]] = max(f[st[x]], dep);
  for (long long i = head[x]; i != -1; i = e[i].next) {
    long long y = e[i].to;
    if (y == pre) continue;
    dfs4(y, x, dep + 1);
  }
}
void coun(long long x, long long pre) {
  f[st[x]] = -1;
  for (long long i = head[x]; i != -1; i = e[i].next) {
    long long y = e[i].to;
    if (y == pre) continue;
    coun(y, x);
  }
}
void dfs2(long long x, long long pre, long long dep, long long q) {
  ans[x] = 0;
  for (long long i = head[x]; i != -1; i = e[i].next) {
    long long y = e[i].to;
    if (y == pre || y == son[x]) continue;
    dfs2(y, x, dep + 1, 0);
    ans[x] = max(ans[x], ans[y]);
  }
  if (son[x] != -1)
    dfs2(son[x], x, dep + 1, 1), ans[x] = max(ans[x], ans[son[x]]);
  for (int i = head[x]; i != -1; i = e[i].next) {
    int y = e[i].to;
    if (y == pre || y == son[x]) continue;
    mas = 0;
    dfs3(y, x, x);
    ans[x] = max(ans[x], mas);
    dfs4(y, x, dep + 1);
  }
  ans[x] = max(ans[x], solve(x, x));
  f[st[x]] = max(f[st[x]], dep);
  if (q == 0) coun(x, pre);
}
int main() {
  long long n;
  memset(f, -1, sizeof(f));
  scanf("%lld", &n);
  memset(head, -1, sizeof(head)), bian = -1;
  for (long long i = 2; i <= n; i++) {
    long long a;
    char c[2];
    scanf("%lld %s", &a, &c);
    add(a, i, 1 << (c[0] - 'a'));
  }
  st[1] = 0;
  dfs1(1, -1, 0);
  dfs2(1, -1, 0, 0);
  printf("%lld", ans[1]);
  for (long long i = 2; i <= n; i++) printf(" %lld", ans[i]);
  printf("\n");
}
