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 INF = 1e9 + 7;
int n;
int ans[500010];
vector<int> V[500010];
int h[500010];
int e[500010];
int c[500010];
int s[500010];
int t[500010][2];
int et[500010];
vector<int> D;
int data[1 << ('v' - 'a' + 1)];
int r;
void del() {
  for (vector<int>::iterator it = D.begin(); it != D.end(); ++it) {
    data[*it] = -INF;
  }
  D.clear();
  r = 0;
}
void dfs(int p, int q, bool b) {
  int big = -1;
  for (int i = (int)(0); i < (int)(V[q].size()); ++i) {
    if (V[q][i] != p && (big < 0 || s[big] < s[V[q][i]])) big = V[q][i];
  }
  for (int i = (int)(0); i < (int)(V[q].size()); ++i) {
    if (V[q][i] != p && V[q][i] != big) {
      dfs(q, V[q][i], 1);
      ans[q] = max(ans[q], ans[V[q][i]]);
    }
  }
  if (big >= 0) {
    dfs(q, big, 0);
    ans[q] = max(ans[q], ans[big]);
  }
  for (int i = (int)(0); i < (int)(V[q].size()); ++i) {
    if (V[q][i] == p || V[q][i] == big) continue;
    for (int j = (int)(t[V[q][i]][0]); j < (int)(t[V[q][i]][1]); ++j) {
      ans[q] = max(ans[q], data[e[et[j]] ^ r ^ e[q]] + h[et[j]] - 2 * h[q]);
      for (int k = (int)(0); k < (int)('v' - 'a' + 1); ++k) {
        ans[q] = max(
            ans[q], data[e[et[j]] ^ (1 << k) ^ r ^ e[q]] + h[et[j]] - 2 * h[q]);
      }
    }
    for (int j = (int)(t[V[q][i]][0]); j < (int)(t[V[q][i]][1]); ++j) {
      data[e[et[j]] ^ r ^ e[q]] = max(data[e[et[j]] ^ r ^ e[q]], h[et[j]]);
      D.push_back(e[et[j]] ^ r ^ e[q]);
    }
  }
  ans[q] = max(ans[q], data[r] - h[q]);
  for (int k = (int)(0); k < (int)('v' - 'a' + 1); ++k) {
    ans[q] = max(ans[q], data[(1 << k) ^ r] - h[q]);
  }
  data[r] = max(data[r], h[q]);
  D.push_back(r);
  r ^= c[q];
  if (b) del();
}
void predfs(int q) {
  static int x = 0;
  t[q][0] = x;
  et[x] = q;
  ++x;
  s[q] = 1;
  for (int i = (int)(0); i < (int)(V[q].size()); ++i) {
    h[V[q][i]] = h[q] + 1;
    e[V[q][i]] = e[q] ^ c[V[q][i]];
    predfs(V[q][i]);
    s[q] += s[V[q][i]];
  }
  t[q][1] = x;
}
int main() {
  scanf("%d", &n);
  for (int i = (int)(2); i < (int)(n + 1); ++i) {
    char y;
    scanf("%d %c", e + i, &y);
    c[i] = (1 << (y - 'a'));
    V[e[i]].push_back(i);
  }
  h[1] = 0;
  e[1] = 0;
  predfs(1);
  fill(data, data + (1 << ('v' - 'a' + 1)), -INF);
  dfs(-1, 1, 0);
  for (int i = (int)(1); i < (int)(n + 1); ++i) {
    printf("%d%c", ans[i], i == n ? '\n' : ' ');
  }
  return 0;
}
