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 GCC optimize("Ofast")
using namespace std;
vector<pair<int, char>> adj[500001];
int ans[500001], lazy[500001], lazy2[500001];
unordered_map<int, int>* maps[500001];
void dfs(int cur, int par) {
  if (adj[cur].size() == 1 and cur != 1) {
    maps[cur] = new unordered_map<int, int>;
    (*maps[cur])[0] = 0;
    return;
  }
  pair<int, int> ind = {-1, -1};
  bool BAD = 1;
  for (auto [j, c] : adj[cur]) {
    if (j == par) continue;
    dfs(j, cur);
    if (BAD || (*maps[j]).size() > (*maps[cur]).size()) {
      BAD = 0;
      maps[cur] = maps[j];
      ind = {j, c};
    }
  }
  auto [J, C] = ind;
  lazy2[cur] = lazy2[J] + 1;
  lazy[cur] = lazy[J] ^ (1 << (C - 'a'));
  ans[cur] = max(ans[J], (int)1);
  if ((*maps[cur]).count((1 << (C - 'a')) ^ lazy[cur]))
    (*maps[cur])[(1 << (C - 'a')) ^ lazy[cur]] =
        max((*maps[cur])[(1 << (C - 'a')) ^ lazy[cur]], (int)1 - lazy2[cur]);
  else
    (*maps[cur])[(1 << (C - 'a')) ^ lazy[cur]] = 1 - lazy2[cur];
  for (auto [j, c] : adj[cur]) {
    if (j == par) continue;
    {
      int v = lazy[j] ^ (1 << (c - 'a'));
      int m = lazy2[j] + 1;
      int Query = 0;
      for (int k = 0; k < 22; k++) {
        if (v & (1 << k)) Query |= (1 << k);
      }
      if ((*maps[j]).count(Query))
        ans[cur] = max(ans[cur], (*maps[j])[Query] + m);
      for (int k = 0; k < 22; k++) {
        if ((*maps[j]).count(Query ^ (1 << k)))
          ans[cur] = max(ans[cur], (*maps[j])[Query ^ (1 << k)] + m);
      }
    }
    ans[cur] = max(ans[cur], ans[j]);
    if (j == J) {
      continue;
    }
    {
      int v = (1 << (c - 'a'));
      int m = 1;
      int Query = 0;
      for (int k = 0; k < 22; k++) {
        if (v & (1 << k)) Query |= (1 << k);
      }
      if ((*maps[cur]).count(Query ^ lazy[cur]))
        ans[cur] =
            max(ans[cur], (*maps[cur])[Query ^ lazy[cur]] + m + lazy2[cur]);
      for (int k = 0; k < 22; k++) {
        if ((*maps[cur]).count(Query ^ (1 << k) ^ lazy[cur]))
          ans[cur] = max(ans[cur], (*maps[cur])[Query ^ (1 << k) ^ lazy[cur]] +
                                       m + lazy2[cur]);
      }
    }
    for (auto [_v, _m] : (*maps[j])) {
      int v = _v, m = _m;
      v ^= lazy[j] ^ (1 << (c - 'a'));
      m += lazy2[j] + 1;
      int Query = 0;
      for (int k = 0; k < 22; k++)
        if (v & (1 << k)) Query |= (1 << k);
      if ((*maps[cur]).count(Query ^ lazy[cur]))
        ans[cur] =
            max(ans[cur], (*maps[cur])[Query ^ lazy[cur]] + m + lazy2[cur]);
      for (int k = 0; k < 22; k++) {
        if ((*maps[cur]).count(Query ^ lazy[cur] ^ (1 << k)))
          ans[cur] = max(ans[cur], (*maps[cur])[Query ^ lazy[cur] ^ (1 << k)] +
                                       m + lazy2[cur]);
      }
    }
    if ((*maps[cur]).count((1 << (c - 'a')) ^ lazy[cur]))
      (*maps[cur])[(1 << (c - 'a')) ^ lazy[cur]] =
          max((*maps[cur])[(1 << (c - 'a')) ^ lazy[cur]], (int)1 - lazy2[cur]);
    else
      (*maps[cur])[(1 << (c - 'a')) ^ lazy[cur]] = 1 - lazy2[cur];
    for (auto [_v, _m] : (*maps[j])) {
      int v = _v, m = _m;
      v ^= lazy[j] ^ (1 << (c - 'a'));
      m += lazy2[j] + 1;
      if ((*maps[cur]).count(v ^ lazy[cur]))
        (*maps[cur])[v ^ lazy[cur]] =
            max((*maps[cur])[v ^ lazy[cur]], m - lazy2[cur]);
      else
        (*maps[cur])[v ^ lazy[cur]] = m - lazy2[cur];
    }
    (*maps[j]).clear();
  }
}
signed main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  int n;
  int j;
  char c;
  cin >> n;
  for (int i = 2; i <= n; i++) {
    cin >> j >> c;
    adj[i].push_back({j, c});
    adj[j].push_back({i, c});
  }
  if (n > 1) dfs(1, 0);
  for (int i = 1; i <= n; i++) {
    cout << ans[i] << " ";
  }
}
