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 N = 5E5 + 10, B = 22;
int w[N];
vector<pair<int, int>> edge[N];
int son[N], sz[N], depth[N];
void dfs1(int x, int fa, int c) {
  sz[x] = 1, depth[x] = depth[fa] + 1;
  w[x] = w[fa] ^ (1 << c);
  for (auto& [to, val] : edge[x]) {
    if (to == fa) continue;
    dfs1(to, x, val);
    sz[x] += sz[to];
    if (sz[to] > sz[son[x]]) son[x] = to;
  }
}
int res[N];
int lca;
vector<int> v;
int mp[1 << B];
void calc(int x, int fa) {
  v.push_back(x);
  if (mp[w[x]]) res[lca] = max(res[lca], depth[x] + mp[w[x]] - 2 * depth[lca]);
  for (int i = 0; i < B; ++i) {
    int target = 1 << i;
    int need = target ^ w[x];
    if (mp[need])
      res[lca] = max(res[lca], depth[x] + mp[need] - 2 * depth[lca]);
  }
  for (auto& [to, val] : edge[x]) {
    if (to == fa) continue;
    calc(to, x);
  }
}
void del(int x, int fa) {
  mp[w[x]] = 0;
  for (auto& [to, val] : edge[x]) {
    if (to == fa) continue;
    del(to, x);
  }
}
void dfs2(int x, int fa, int tp) {
  for (auto& [to, val] : edge[x]) {
    if (to == fa or to == son[x]) continue;
    dfs2(to, x, 0);
    res[x] = max(res[x], res[to]);
  }
  if (son[x]) {
    dfs2(son[x], x, 1);
    res[x] = max(res[x], res[son[x]]);
  }
  mp[w[x]] = max(mp[w[x]], depth[x]);
  lca = x;
  for (auto& [to, val] : edge[x]) {
    if (to == fa or to == son[x]) continue;
    calc(to, x);
    for (auto& op : v) mp[w[op]] = max(mp[w[op]], depth[op]);
    v.clear();
  }
  if (mp[w[x]]) res[lca] = max(res[lca], depth[x] + mp[w[x]] - 2 * depth[lca]);
  for (int i = 0; i < B; ++i) {
    int target = 1 << i;
    int need = target ^ w[x];
    if (mp[need]) {
      res[x] = max(res[x], mp[need] - depth[x]);
    }
  }
  if (!tp) del(x, fa);
}
int main() {
  int n;
  cin >> n;
  for (int i = 2; i <= n; ++i) {
    int p;
    char s[2];
    scanf("%d %s", &p, s);
    s[0] -= 'a';
    edge[p].push_back({i, *s}), edge[i].push_back({p, *s});
  }
  dfs1(1, 0, 0);
  dfs2(1, 0, 1);
  for (int i = 1; i <= (n); ++i) printf("%d%c", res[i], " \n"[i == n]);
  return 0;
}
