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 double eps = 1e-9;
int n, sol[500005], st[500005], gm[500005], lv[500005];
vector<pair<int, int> > g[500005];
int id[10000005], ids;
void dfs(int nod, int mask) {
  st[nod] = 1;
  gm[nod] = mask;
  if (!id[mask]) id[mask] = ++ids;
  for (pair<int, int> x : g[nod]) {
    lv[x.first] = lv[nod] + 1;
    dfs(x.first, mask ^ (1 << x.second));
    st[nod] += st[x.first];
  }
}
vector<int> *v[500005];
multiset<int> ms[500005];
void dsu(int nod, bool keep) {
  int bigchild = 0;
  for (pair<int, int> x : g[nod])
    if (st[x.first] > st[bigchild]) bigchild = x.first;
  for (pair<int, int> x : g[nod])
    if (x.first != bigchild) {
      dsu(x.first, 0);
      sol[nod] = max(sol[nod], sol[x.first]);
    }
  if (bigchild) {
    dsu(bigchild, 1);
    v[nod] = v[bigchild];
    sol[nod] = max(sol[nod], sol[bigchild]);
  } else
    v[nod] = new vector<int>();
  v[nod]->push_back(nod);
  if (ms[id[gm[nod]]].size() > 0)
    sol[nod] = max(sol[nod], *ms[id[gm[nod]]].rbegin() - lv[nod]);
  for (int i = 0; i < 22; i++)
    if (ms[id[gm[nod] ^ (1 << i)]].size() > 0)
      sol[nod] = max(sol[nod], *ms[id[gm[nod] ^ (1 << i)]].rbegin() - lv[nod]);
  ms[id[gm[nod]]].insert(lv[nod]);
  for (pair<int, int> x : g[nod])
    if (x.first != bigchild) {
      for (int u : *v[x.first]) {
        if (ms[id[gm[u]]].size() > 0)
          sol[nod] =
              max(sol[nod], *ms[id[gm[u]]].rbegin() + lv[u] - 2 * lv[nod]);
        for (int i = 0; i < 22; i++)
          if (ms[id[gm[u] ^ (1 << i)]].size() > 0)
            sol[nod] = max(sol[nod], *ms[id[gm[u] ^ (1 << i)]].rbegin() +
                                         lv[u] - 2 * lv[nod]);
      }
      for (int u : *v[x.first]) {
        ms[id[gm[u]]].insert(lv[u]);
        v[nod]->push_back(u);
      }
    }
  if (!keep) {
    for (int u : *v[nod]) ms[id[gm[u]]].erase(ms[id[gm[u]]].find(lv[u]));
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  srand(time(0));
  cin >> n;
  for (int i = 2; i <= n; i++) {
    int pi;
    char l[2];
    cin >> pi >> l;
    g[pi].push_back(pair<int, int>(i, l[0] - 'a'));
  }
  lv[1] = 1;
  dfs(1, 0);
  dsu(1, 0);
  for (int i = 1; i <= n; i++) cout << sol[i] << " \n"[i == n];
  return 0;
}
