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>
#pragma comment(linker, "/STACK:256000000")
using namespace std;
const int maxN = 510000;
int n;
vector<int> g[maxN], w[maxN];
unordered_map<int, int> *s[maxN];
int shift[maxN], len[maxN];
int res[maxN];
bool cmp(pair<int, int> x, pair<int, int> y) {
  return s[x.first]->size() > s[y.first]->size();
}
void dfs(int v) {
  for (int i = 0; i < g[v].size(); ++i) {
    dfs(g[v][i]);
    res[v] = max(res[v], res[g[v][i]]);
  }
  if (g[v].size() == 0) {
    s[v] = new unordered_map<int, int>();
    (*s[v])[0] = 0;
    shift[v] = 0;
    res[v] = 0;
    return;
  }
  vector<pair<int, int> > children;
  for (int i = 0; i < g[v].size(); ++i) {
    children.push_back(make_pair(g[v][i], w[v][i]));
  }
  sort(children.begin(), children.end(), cmp);
  s[v] = s[children[0].first];
  shift[v] = shift[children[0].first];
  shift[v] ^= (1 << children[0].second);
  len[v] = len[children[0].first];
  ++len[v];
  reverse(children.begin(), children.end());
  for (int i = 0; i + 1 < children.size(); ++i) {
    int u = children[i].first;
    int c = children[i].second;
    shift[u] ^= (1 << c);
    ++len[u];
    for (unordered_map<int, int>::iterator it = s[u]->begin();
         it != s[u]->end(); ++it) {
      int current = (shift[v] ^ shift[u] ^ (it->first));
      int l = len[u] + len[v] + it->second;
      unordered_map<int, int>::iterator jt = s[v]->find(current);
      if (jt != s[v]->end()) {
        res[v] = max(res[v], jt->second + l);
      }
      for (int j = 0; j <= 'v' - 'a'; ++j) {
        jt = s[v]->find(current ^ (1 << j));
        if (jt != s[v]->end()) {
          res[v] = max(res[v], jt->second + l);
        }
      }
    }
    for (unordered_map<int, int>::iterator it = s[u]->begin();
         it != s[u]->end(); ++it) {
      int current = (shift[u] ^ shift[v] ^ it->first);
      int value = it->second + len[u] - len[v];
      if (s[v]->count(current)) {
        (*s[v])[current] = max((*s[v])[current], value);
      } else {
        (*s[v])[current] = value;
      }
    }
  }
  unordered_map<int, int>::iterator it = s[v]->find(shift[v]);
  if (it != s[v]->end()) {
    res[v] = max(res[v], it->second + len[v]);
  }
  for (int j = 0; j <= 'v' - 'a'; ++j) {
    it = s[v]->find(shift[v] ^ (1 << j));
    if (it != s[v]->end()) {
      res[v] = max(res[v], len[v] + it->second);
    }
  }
  if (s[v]->count(shift[v])) {
    (*s[v])[shift[v]] = max((*s[v])[shift[v]], -len[v]);
  } else {
    (*s[v])[shift[v]] = -len[v];
  }
}
void gen() {
  n = 500000;
  for (int i = 1; i < n; ++i) {
    int v = rand() % i + 1;
    g[v].push_back(i + 1);
    w[v].push_back(rand() % ('v' - 'a' + 1));
  }
}
char ss[15];
int main() {
  scanf("%d\n", &n);
  for (int i = 1; i < n; ++i) {
    for (int j = 0; j < 15; ++j) {
      ss[j] = 0;
    }
    gets(ss);
    int l = strlen(ss);
    int v = 0;
    char c = ss[l - 1];
    for (int j = 0; j < l - 2; ++j) {
      v = v * 10 + (ss[j] - '0');
    }
    g[v].push_back(i + 1);
    w[v].push_back(c - 'a');
  }
  dfs(1);
  for (int i = 1; i <= n; ++i) {
    printf("%d ", res[i]);
  }
  printf("\n");
  cerr << clock() << endl;
  return 0;
}
