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>
const int oo = 0x3f3f3f3f;
template <typename T>
inline bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
template <typename T>
inline bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
std::string procStatus() {
  std::ifstream t("/proc/self/status");
  return std::string(std::istreambuf_iterator<char>(t),
                     std::istreambuf_iterator<char>());
}
template <typename T>
T read(T &first) {
  int f = 1;
  char ch = getchar_unlocked();
  for (; !isdigit(ch); ch = getchar_unlocked())
    if (ch == '-') f = -1;
  for (first = 0; isdigit(ch); ch = getchar_unlocked())
    first = 10 * first + ch - '0';
  return first *= f;
}
template <typename T>
void write(T first) {
  if (first == 0) {
    putchar_unlocked('0');
    return;
  }
  if (first < 0) {
    putchar_unlocked('-');
    first = -first;
  }
  static char s[20];
  int top = 0;
  for (; first; first /= 10) s[++top] = first % 10 + '0';
  while (top) putchar_unlocked(s[top--]);
}
const int MAXN = 5e5 + 5, SIGMA = 'z' - 'a', SIZE = (1 << SIGMA) + 5;
struct Edge {
  int v, next;
  int w;
  Edge() {}
  Edge(int v_, int next_, int w_) : v(v_), next(next_), w(w_) {}
};
int N;
int tote, head[MAXN];
Edge edge[MAXN];
int dep[MAXN], size[MAXN], hson[MAXN];
int val[MAXN];
int maxdep[SIZE];
int ans[MAXN];
int curval;
inline void addEdge(int u, int v, int w) {
  edge[++tote] = Edge(v, head[u], w);
  head[u] = tote;
}
void initdfs(int u) {
  size[u] = 1;
  for (int i = head[u]; i; i = edge[i].next) {
    int v = edge[i].v;
    int w = edge[i].w;
    val[v] = val[u] ^ w;
    dep[v] = dep[u] + 1;
    initdfs(v);
    if (size[v] > size[hson[u]]) hson[u] = v;
    size[u] += size[v];
  }
}
inline void add(int u) { chkmax(maxdep[val[u]], dep[u]); }
inline void clear(int u) { maxdep[val[u]] = -oo; }
inline void contrib(int u) {
  chkmax(curval, maxdep[val[u]] + dep[u]);
  for (int i = 0; i < SIGMA; ++i) {
    chkmax(curval, maxdep[val[u] ^ (1 << i)] + dep[u]);
  }
}
template <void (*op)(int)>
void foreach (int u) {
  op(u);
  for (int i = head[u]; i; i = edge[i].next) {
    int v = edge[i].v;
    foreach
      <op>(v);
  }
}
void dfs(int u, bool keep) {
  for (int i = head[u]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (v != hson[u]) {
      dfs(v, false);
      chkmax(ans[u], ans[v]);
    }
  }
  if (hson[u]) {
    dfs(hson[u], true);
    chkmax(ans[u], ans[hson[u]]);
  }
  curval = 0;
  for (int i = head[u]; i; i = edge[i].next) {
    int v = edge[i].v;
    if (v != hson[u]) {
      foreach
        <contrib>(v);
      foreach
        <add>(v);
    }
  }
  contrib(u);
  add(u);
  chkmax(ans[u], curval - 2 * dep[u]);
  if (!keep) foreach
      <clear>(u);
}
void input() {
  read(N);
  for (int i = 2; i <= N; ++i) {
    int p;
    char c;
    read(p);
    c = getchar_unlocked();
    addEdge(p, i, 1 << (c - 'a'));
  }
}
void solve() {
  initdfs(1);
  memset(maxdep, -oo, sizeof(maxdep));
  dfs(1, true);
  for (int i = 1; i <= N; ++i) {
    write(ans[i]);
    putchar_unlocked(' ');
  }
  putchar_unlocked('\n');
}
int main() {
  input();
  solve();
  return 0;
}
