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>
int k, u, t[500000 + 1], ans[500000 + 1];
int a[500000 + 1], s[500000 + 1], h[500000 + 1];
int fiuMare[500000 + 1], hMare[500000 + 1];
int best[1 << 22], last[1 << 22];
std::vector<int> e[500000 + 1];
std::vector<std::pair<int, char> > v[500000 + 1];
int pos = 1 << 17;
char buf[1 << 17];
inline char nextch() {
  if (pos == 1 << 17) fread(buf, 1 << 17, 1, stdin), pos = 0;
  return buf[pos++];
}
inline int read() {
  int first = 0;
  char ch = nextch();
  while (!isdigit(ch)) ch = nextch();
  while (isdigit(ch)) {
    first = 10 * first + ch - '0';
    ch = nextch();
  }
  return first;
}
inline void add(int first) {
  if (last[a[first]] != u) {
    last[a[first]] = u;
    best[a[first]] = h[first];
  } else if (h[first] > best[a[first]])
    best[a[first]] = h[first];
}
inline void query(int first, int root) {
  if ((last[a[first]] == u) &&
      (h[first] + best[a[first]] - 2 * h[root] > ans[root]))
    ans[root] = h[first] + best[a[first]] - 2 * h[root];
  for (int i = 0; i < 22; i++)
    if ((last[a[first] ^ (1 << i)] == u) &&
        (h[first] + best[a[first] ^ (1 << i)] - 2 * h[root] > ans[root]))
      ans[root] = h[first] + best[a[first] ^ (1 << i)] - 2 * h[root];
}
void goq(int first, int root) {
  query(first, root);
  for (auto second : v[first])
    if (second.first != t[first]) goq(second.first, root);
}
void god(int first) {
  add(first);
  for (auto second : v[first])
    if (second.first != t[first]) god(second.first);
}
void dfs(int first) {
  s[first] = 1;
  for (auto second : v[first]) {
    if (second.first != t[first]) {
      t[second.first] = first;
      a[second.first] = a[first] ^ (1 << second.second);
      h[second.first] = h[first] + 1;
      dfs(second.first);
      s[first] += s[second.first];
      if (s[second.first] > s[fiuMare[first]]) fiuMare[first] = second.first;
    }
  }
  if (fiuMare[first])
    hMare[first] = hMare[fiuMare[first]];
  else
    fiuMare[first] = first, hMare[first] = h[first];
}
void hpd(int first) {
  k++;
  int acum = k;
  int l = hMare[first] - h[first] + 1;
  for (int i = 0; i < l; i++) {
    e[acum].push_back(first);
    for (auto second : v[first])
      if ((second.first != t[first]) && (second.first != fiuMare[first]))
        hpd(second.first);
    first = fiuMare[first];
  }
}
void era(int first) {
  for (auto second : v[first]) {
    if (second.first != t[first]) {
      era(second.first);
      if (ans[second.first] > ans[first]) ans[first] = ans[second.first];
    }
  }
}
int main() {
  int n = read();
  for (int i = 2; i <= n; i++) {
    int first = read();
    char ch = nextch();
    v[i].push_back(std::make_pair(first, ch - 'a'));
    v[first].push_back(std::make_pair(i, ch - 'a'));
  }
  dfs(1);
  hpd(1);
  for (u = 1; u <= k; u++) {
    add(e[u][e[u].size() - 1]);
    for (int i = e[u].size() - 2; i >= 0; i--) {
      int first = e[u][i];
      query(first, first);
      add(first);
      for (auto second : v[first]) {
        if ((second.first != t[first]) && (second.first != fiuMare[first])) {
          goq(second.first, first);
          god(second.first);
        }
      }
    }
  }
  era(1);
  for (int i = 1; i <= n; i++) printf("%d ", ans[i]);
  return 0;
}
