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 = 5e5 + 10;
const int maxm = 5e6 + 10;
struct node {
  int v, w, next;
};
node edge[2 * maxn];
int book[maxm];
int first[maxn], val[maxn], sum[maxn], son[maxn], deep[maxn], mp1[maxn],
    mp2[maxn], ans[maxn];
int n, num;
void addedge(int u, int v, int w) {
  edge[num].v = v;
  edge[num].w = w;
  edge[num].next = first[u];
  first[u] = num++;
}
void dfsI(int cur, int fa) {
  int i, v, w;
  sum[cur] = 1, son[cur] = -1;
  num++;
  mp1[cur] = num, mp2[num] = cur;
  for (i = first[cur]; i != -1; i = edge[i].next) {
    v = edge[i].v, w = edge[i].w;
    if (v != fa) {
      deep[v] = deep[cur] + 1;
      val[v] = val[cur] ^ w;
      dfsI(v, cur);
      sum[cur] += sum[v];
      if (son[cur] == -1 || sum[son[cur]] < sum[v]) son[cur] = v;
    }
  }
}
void dfsII(int cur, int fa, int flag) {
  int i, j, k, v, bc, tmp1, tmp2;
  for (i = first[cur]; i != -1; i = edge[i].next) {
    v = edge[i].v;
    if (v != fa && v != son[cur]) dfsII(v, cur, 0);
  }
  if (son[cur] != -1) dfsII(son[cur], cur, 1), ans[cur] = ans[son[cur]];
  for (i = first[cur]; i != -1; i = edge[i].next) {
    v = edge[i].v;
    if (v != fa && v != son[cur]) {
      ans[cur] = max(ans[cur], ans[v]);
      for (j = mp1[v]; j <= mp1[v] + sum[v] - 1; j++) {
        tmp1 = mp2[j];
        if (book[val[tmp1]])
          ans[cur] =
              max(ans[cur], deep[tmp1] + book[val[tmp1]] - 2 * deep[cur]);
        for (k = 0; k < 22; k++) {
          tmp2 = val[mp2[j]] ^ (1 << k);
          if (book[tmp2])
            ans[cur] = max(ans[cur], deep[tmp1] + book[tmp2] - 2 * deep[cur]);
        }
      }
      for (j = mp1[v]; j <= mp1[v] + sum[v] - 1; j++) {
        tmp1 = mp2[j];
        book[val[tmp1]] = max(book[val[tmp1]], deep[tmp1]);
      }
    }
  }
  if (book[val[cur]]) ans[cur] = max(ans[cur], book[val[cur]] - deep[cur]);
  for (k = 0; k < 22; k++) {
    tmp2 = (val[cur]) ^ (1 << k);
    if (book[tmp2]) ans[cur] = max(ans[cur], book[tmp2] - deep[cur]);
  }
  book[val[cur]] = max(book[val[cur]], deep[cur]);
  if (!flag) {
    for (j = mp1[cur]; j <= mp1[cur] + sum[cur] - 1; j++) {
      tmp1 = mp2[j];
      book[val[tmp1]] = 0;
    }
  }
}
void dfsIII(int cur, int fa) {
  int i, v;
  for (i = first[cur]; i != -1; i = edge[i].next) {
    v = edge[i].v;
    if (v != fa) {
      ans[cur] = max(ans[cur], ans[v]);
      dfsIII(v, cur);
    }
  }
}
void dfsIV(int cur, int fa) {
  int i, v;
  val[cur] = (val[fa] ^ val[cur]);
  for (i = first[cur]; i != -1; i = edge[i].next) {
    v = edge[i].v;
    if (v != fa) {
      dfsIV(v, cur);
    }
  }
}
int main() {
  int i, u, v, w;
  char ch[10];
  scanf("%d", &n);
  memset(first, -1, sizeof(first));
  for (v = 2; v <= n; v++) {
    scanf("%d%s", &u, ch);
    w = 1 << (ch[0] - 'a');
    addedge(u, v, w), addedge(v, u, w);
  }
  num = 0;
  dfsI(1, 0);
  dfsII(1, 0, 0);
  for (i = 1; i <= n; i++) printf("%d ", ans[i]);
  printf("\n");
  return 0;
}
