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 int maxn = 500005;
int n, m, i, j, t, k, s, fa[maxn], N, head[maxn], a[maxn], son[maxn], dep[maxn],
    siz[maxn], buc[(1 << 22) + 5], ans, an[maxn];
struct Edge {
  int nxt, aim, len;
} edge[maxn];
inline void add_edge(int x, int y, int z) {
  edge[++N] = (Edge){head[x], y, z};
  head[x] = N;
}
inline void dfs_get_a(int x) {
  siz[x] = 1;
  for (int i = head[x]; i; i = edge[i].nxt) {
    int des = edge[i].aim;
    a[des] = (a[x] ^ (1 << edge[i].len));
    dep[des] = dep[x] + 1;
    dfs_get_a(des);
    siz[x] += siz[des];
    if (siz[des] > siz[son[x]] || !son[x]) son[x] = des;
  }
}
void dfs_gain_ans(int x) {
  for (int i = 0; i < 22; ++i) ans = max(ans, dep[x] + buc[a[x] ^ (1 << i)]);
  ans = max(ans, dep[x] + buc[a[x]]);
  for (int i = head[x]; i; i = edge[i].nxt) {
    int des = edge[i].aim;
    dfs_gain_ans(des);
  }
}
void dfs_push(int x) {
  buc[a[x]] = max(buc[a[x]], dep[x]);
  for (int i = head[x]; i; i = edge[i].nxt) {
    int des = edge[i].aim;
    dfs_push(des);
  }
}
void dfs_empt(int x) {
  buc[a[x]] = buc[(1 << 22) + 2];
  for (int i = head[x]; i; i = edge[i].nxt) {
    int des = edge[i].aim;
    dfs_empt(des);
  }
}
void dfs_solve(int x) {
  for (int i = head[x]; i; i = edge[i].nxt) {
    int des = edge[i].aim;
    if (des == son[x]) continue;
    dfs_solve(des);
    dfs_empt(des);
    an[x] = max(an[x], an[des]);
  }
  if (son[x]) {
    dfs_solve(son[x]);
    ans = (dep[x] << 1);
    an[x] = max(an[x], an[son[x]]);
    buc[a[x]] = max(buc[a[x]], dep[x]);
    for (int i = head[x]; i; i = edge[i].nxt) {
      int des = edge[i].aim;
      if (des == son[x]) continue;
      dfs_gain_ans(des);
      dfs_push(des);
    }
    ans -= (dep[x] << 1);
    an[x] = max(an[x], ans);
  }
  buc[a[x]] = max(buc[a[x]], dep[x]);
  for (int i = 0; i < 22; ++i)
    an[x] = max(an[x], buc[a[x] ^ (1 << i)] - dep[x]);
  an[x] = max(an[x], buc[a[x]] - dep[x]);
}
int main() {
  scanf("%d", &n);
  for (i = 2; i <= n; ++i) {
    char op[2];
    scanf("%d%s", &fa[i], op);
    add_edge(fa[i], i, op[0] - 'a');
  }
  dep[1] = 1;
  memset(buc, -0x3f3f3f3f, sizeof(buc));
  dfs_get_a(1);
  dfs_solve(1);
  for (i = 1; i <= n; ++i) printf("%d ", an[i]);
  puts("");
  return 0;
}
