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 double Pi = acos(-1.0), E = exp(1.0);
const long double Lucky_Number =
    E * (pow((E + Pi) * (E + E + Pi), E)) +
    (E / ((pow(Pi, E) - E) * (E + pow(E, Pi) - pow(Pi, E))));
char Buf[1 << 22], *P1 = Buf, *P2 = Buf;
inline int read() {
  int x = 0, f = 1;
  char ch =
      (P1 == P2 && (P2 = (P1 = Buf) + fread(Buf, 1, (1 << 22) - 10, stdin),
                    P1 == P2)
           ? EOF
           : *P1++);
  while (!isdigit(ch)) {
    f -= (ch == '-') << 1;
    ch = (P1 == P2 && (P2 = (P1 = Buf) + fread(Buf, 1, (1 << 22) - 10, stdin),
                       P1 == P2)
              ? EOF
              : *P1++);
  }
  while (isdigit(ch)) {
    x = x * 10 + (ch ^ 48);
    ch = (P1 == P2 && (P2 = (P1 = Buf) + fread(Buf, 1, (1 << 22) - 10, stdin),
                       P1 == P2)
              ? EOF
              : *P1++);
  }
  return x * f;
}
inline char input_char() {
  char c = (P1 == P2 && (P2 = (P1 = Buf) + fread(Buf, 1, (1 << 22) - 10, stdin),
                         P1 == P2)
                ? EOF
                : *P1++);
  while (c < 'a' || c > 'z')
    c = (P1 == P2 && (P2 = (P1 = Buf) + fread(Buf, 1, (1 << 22) - 10, stdin),
                      P1 == P2)
             ? EOF
             : *P1++);
  return c;
}
const int Max = 5e5 + 100;
struct edge {
  int u, v, w, nxt;
} e[Max];
int en, h[Max];
inline void add(int u, int v, int w) {
  ++en;
  e[en].u = u, e[en].v = v, e[en].w = w;
  e[en].nxt = h[u], h[u] = en;
}
int n, siz[Max], depth[Max], son[Max];
void init(int u) {
  siz[u] = 1;
  for (int i = h[u]; i; i = e[i].nxt) {
    int v = e[i].v;
    depth[v] = depth[u] + 1;
    init(v);
    siz[u] += siz[v];
    if (siz[v] > siz[son[u]]) son[u] = v;
  }
}
int buc[1 << 23], ans[Max];
void clear(int u, int cur) {
  buc[cur] = -INT_MAX / 3;
  for (int i = h[u]; i; i = e[i].nxt) {
    int v = e[i].v, w = e[i].w;
    clear(v, cur ^ w);
  }
}
void update(int u, int cur) {
  buc[cur] = max(buc[cur], depth[u]);
  for (int i = h[u]; i; i = e[i].nxt) {
    int v = e[i].v, w = e[i].w;
    update(v, cur ^ w);
  }
}
int query(int u, int cur) {
  int ans = buc[cur] + depth[u];
  for (int i = 0; i < 22; ++i) ans = max(ans, buc[(1 << i) ^ cur] + depth[u]);
  for (int i = h[u]; i; i = e[i].nxt) {
    int v = e[i].v, w = e[i].w;
    ans = max(ans, query(v, cur ^ w));
  }
  return ans;
}
void dfs(int u, int cur) {
  int val = 0;
  for (int i = h[u]; i; i = e[i].nxt) {
    int v = e[i].v, w = e[i].w;
    if (v == son[u]) {
      val = w;
      continue;
    }
    dfs(v, cur ^ w);
    ans[u] = max(ans[u], ans[v]);
    clear(v, cur ^ w);
  }
  if (son[u]) {
    dfs(son[u], cur ^ val);
    ans[u] = max(ans[u], ans[son[u]]);
  }
  buc[cur] = max(buc[cur], depth[u]);
  int res = 0;
  res = max(res, buc[cur] + depth[u]);
  for (int i = 0; i < 22; ++i) res = max(res, buc[cur ^ (1 << i)] + depth[u]);
  for (int i = h[u]; i; i = e[i].nxt) {
    int v = e[i].v, w = e[i].w;
    if (v == son[u]) continue;
    res = max(res, query(v, cur ^ w));
    update(v, cur ^ w);
  }
  ans[u] = max(ans[u], res - depth[u] * 2);
}
int main() {
  memset(buc, 0xcf, sizeof(buc));
  n = read();
  for (int i = 2; i <= n; ++i) {
    int f = read();
    add(f, i, 1 << (input_char() - 'a'));
  }
  depth[1] = 1;
  init(1);
  dfs(1, 0);
  for (int i = 1; i <= n; ++i) printf("%d ", ans[i]);
  putchar('\n');
  return 0;
}
