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 N = 500005, R = 22, status = (1 << R) - 1, INF = 1e9;
struct edge {
  int to, nxt;
} e[N];
int fa[N], n, head[N], cnt, dep[N], prefix[N], son[N], ans[N], size[N],
    bit[R + 5], f[(1 << R) + 5];
char ch;
class FileInputOutput {
 private:
  static const int S = 1 << 21;
  char Fin[S], Fout[S], *A, *B;
  int Ftop, pt[15];

 public:
  template <typename T>
  inline void read(T& x) {
    x = 0;
    char ch;
    while (!isdigit(
        ch = (A == B && (B = (A = Fin) + fread(Fin, 1, S, stdin), A == B)
                  ? EOF
                  : *A++)))
      ;
    while (x = (x << 3) + (x << 1) + (ch & 15),
           isdigit(
               ch = (A == B && (B = (A = Fin) + fread(Fin, 1, S, stdin), A == B)
                         ? EOF
                         : *A++)))
      ;
  }
  template <typename T>
  inline void write(T x) {
    if (!x)
      return (void)((Ftop < S ? Fout[Ftop++] = '0'
                              : (fwrite(Fout, 1, S, stdout),
                                 Fout[(Ftop = 0)++] = '0')),
                    (Ftop < S ? Fout[Ftop++] = ' '
                              : (fwrite(Fout, 1, S, stdout),
                                 Fout[(Ftop = 0)++] = ' ')));
    register int ptop = 0;
    while (x) pt[++ptop] = x % 10, x /= 10;
    while (ptop)
      (Ftop < S ? Fout[Ftop++] = pt[ptop--] + 48
                : (fwrite(Fout, 1, S, stdout),
                   Fout[(Ftop = 0)++] = pt[ptop--] + 48));
    (Ftop < S ? Fout[Ftop++] = ' '
              : (fwrite(Fout, 1, S, stdout), Fout[(Ftop = 0)++] = ' '));
  }
  inline void get_alpha(char& ch) {
    while (!isalpha(
        ch = (A == B && (B = (A = Fin) + fread(Fin, 1, S, stdin), A == B)
                  ? EOF
                  : *A++)))
      ;
  }
  inline void Fend(void) { fwrite(Fout, 1, Ftop, stdout); }
} F;
inline void maxer(int& x, const int& y) {
  if (y > x) x = y;
}
inline void DFS1(const int& now) {
  size[now] = 1;
  for (register int i = head[now]; i; i = e[i].nxt) {
    dep[e[i].to] = dep[now] + 1;
    prefix[e[i].to] ^= prefix[now];
    DFS1(e[i].to);
    size[now] += size[e[i].to];
    if (size[e[i].to] > size[son[now]]) son[now] = e[i].to;
  }
}
inline void calc(const int& now, const int& par) {
  register int i;
  for (i = 0; i <= R; ++i) maxer(ans[par], dep[now] + f[prefix[now] ^ bit[i]]);
  for (i = head[now]; i; i = e[i].nxt) calc(e[i].to, par);
}
inline void Add(const int& now) {
  maxer(f[prefix[now]], dep[now]);
  for (register int i = head[now]; i; i = e[i].nxt) Add(e[i].to);
}
inline void Del(const int& now) {
  f[prefix[now]] = -INF;
  for (register int i = head[now]; i; i = e[i].nxt) Del(e[i].to);
}
inline void DFS2(const int& now) {
  register int i;
  for (i = head[now]; i; i = e[i].nxt)
    if (e[i].to != son[now]) DFS2(e[i].to), Del(e[i].to);
  if (son[now]) DFS2(son[now]);
  maxer(f[prefix[now]], dep[now]);
  for (i = 0; i <= R; ++i) maxer(ans[now], dep[now] + f[prefix[now] ^ bit[i]]);
  for (i = head[now]; i; i = e[i].nxt)
    if (e[i].to != son[now]) calc(e[i].to, now), Add(e[i].to);
}
int main() {
  register int i;
  for (F.read(n), i = 2; i <= n; ++i)
    F.read(fa[i]), F.get_alpha(ch), e[++cnt] = (edge){i, head[fa[i]]},
                                    head[fa[i]] = cnt,
                                    prefix[i] = 1 << ch - 'a';
  for (i = 0; i <= status; ++i) f[i] = -INF;
  for (i = 0; i < R; ++i) bit[i] = 1 << i;
  for (DFS1(1), DFS2(1), i = 1; i <= n; ++i) ans[i] -= 2 * dep[i];
  for (i = n; i; --i) maxer(ans[fa[i]], ans[i]);
  for (i = 1; i <= n; ++i) F.write(ans[i]);
  return F.Fend(), 0;
}
