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;
int read() {
  int x = 0, f = 1, ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) x = (x << 1) + (x << 3) + ch - '0', ch = getchar();
  return x * f;
}
int n;
struct edge {
  int to, w, nxt;
  edge() {}
  edge(int tt, int ww, int nn) { to = tt, w = ww, nxt = nn; }
} e[500005 << 1];
int head[500005], k = 0;
void add(int u, int v, int w) {
  e[k] = edge(v, w, head[u]);
  head[u] = k++;
}
int ans[500005], size[500005], son[500005], dfn[500005], maxx[500005],
    id[500005];
int dep[500005], dis[500005], tot = 0;
void dfs1(int u) {
  size[u] = 1;
  dfn[u] = ++tot;
  id[tot] = u;
  for (int i = head[u]; ~i; i = e[i].nxt) {
    register int v = e[i].to;
    dep[v] = dep[u] + 1;
    dis[v] = dis[u] ^ e[i].w;
    dfs1(v);
    size[u] += size[v];
    if (size[son[u]] < size[v]) son[u] = v;
  }
  maxx[u] = tot;
}
int judge[1 << 22];
void check(int x, int v) {
  for (int i = head[v]; ~i; i = e[i].nxt) {
    register int u = e[i].to;
    if (judge[dis[u]])
      ans[x] = max(ans[x], judge[dis[u]] + dep[u] - 2 * dep[x]);
    for (int j = 0; j < 22; j++)
      if (judge[dis[u] ^ (1 << j)])
        ans[x] = max(ans[x], judge[dis[u] ^ (1 << j)] + dep[u] - 2 * dep[x]);
  }
  for (int i = head[v]; ~i; i = e[i].nxt)
    judge[dis[e[i].to]] = max(judge[dis[e[i].to]], dep[e[i].to]);
}
void dfs2(int u, bool keep) {
  for (int i = head[u]; ~i; i = e[i].nxt) {
    register int v = e[i].to;
    if (v != son[u]) dfs2(v, 0), ans[u] = max(ans[u], ans[v]);
  }
  if (son[u]) dfs2(son[u], 1), ans[u] = max(ans[u], ans[son[u]]);
  if (judge[dis[u]]) ans[u] = max(ans[u], judge[dis[u]] - dep[u]);
  for (int i = 0; i < 22; i++)
    if (judge[dis[u] ^ (1 << i)])
      ans[u] = max(ans[u], judge[dis[u] ^ (1 << i)] - dep[u]);
  judge[dis[u]] = max(judge[dis[u]], dep[u]);
  for (int i = head[u]; ~i; i = e[i].nxt) {
    register int v = e[i].to;
    if (v == son[u]) continue;
    for (int j = dfn[v]; j <= maxx[v]; j++) {
      register int x = id[j];
      if (judge[dis[x]])
        ans[u] = max(ans[u], judge[dis[x]] + dep[x] - 2 * dep[u]);
      for (int k = 0; k < 22; k++)
        if (judge[dis[x] ^ (1 << k)])
          ans[u] = max(ans[u], judge[dis[x] ^ (1 << k)] + dep[x] - 2 * dep[u]);
    }
    for (int j = dfn[v]; j <= maxx[v]; j++)
      judge[dis[id[j]]] = max(judge[dis[id[j]]], dep[id[j]]);
  }
  if (!keep)
    for (int i = dfn[u]; i <= maxx[u]; i++) judge[dis[id[i]]] = 0;
}
signed main() {
  memset(head, -1, sizeof head);
  n = read();
  char op;
  for (int i = 2, v; i <= n; i++)
    v = read(), cin >> op, add(v, i, 1 << (op - 'a'));
  dfs1(1);
  dfs2(1, 1);
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  return 0;
}
