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 maxc = 22;
const int maxn = (int)5e5;
int tin[maxn], tout[maxn], _t = 0, ver[maxn], n;
vector<int> g[maxn];
int deep[maxn], maxh[1 << maxc];
unsigned mask[maxn];
int sz[maxn], ans[maxn];
unsigned char s[maxn];
int dfs_size(int v, unsigned m) {
  mask[v] = m;
  sz[v] = 1;
  ver[tin[v] = _t++] = v;
  for (auto u : g[v]) {
    deep[u] = 1 + deep[v];
    sz[v] += dfs_size(u, m ^ (1U << s[u]));
  }
  tout[v] = _t;
  return sz[v];
}
const int INF = (int)1e9;
int calc(int u, int v) {
  int res = maxh[mask[u]] + deep[u] - 2 * deep[v];
  for (int i = 0; i < maxc; ++i) {
    int m = mask[u] ^ (1U << i);
    res = max(res, maxh[m] + deep[u] - 2 * deep[v]);
  }
  return res;
}
void dfs(int v, bool flag) {
  int heavy = -1;
  for (auto u : g[v])
    if (heavy == -1 || sz[heavy] < sz[u]) heavy = u;
  for (auto u : g[v])
    if (heavy != u) {
      dfs(u, 0);
      ans[v] = max(ans[v], ans[u]);
    }
  if (heavy != -1) {
    dfs(heavy, 1);
    ans[v] = max(ans[v], ans[heavy]);
  }
  for (auto u : g[v])
    if (u != heavy) {
      for (int t = tin[u]; t < tout[u]; ++t)
        ans[v] = max(ans[v], calc(ver[t], v));
      for (int t = tin[u]; t < tout[u]; ++t)
        maxh[mask[ver[t]]] = max(maxh[mask[ver[t]]], deep[ver[t]]);
    }
  ans[v] = max(ans[v], calc(v, v));
  maxh[mask[v]] = max(maxh[mask[v]], deep[v]);
  if (!flag)
    for (int t = tin[v]; t < tout[v]; ++t) maxh[mask[ver[t]]] = -INF;
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int v;
    cin >> v >> s[i];
    g[v - 1].push_back(i);
    s[i] -= 'a';
  }
  dfs_size(0, 0);
  fill(maxh, maxh + (1 << maxc), -INF);
  dfs(0, 1);
  for (int i = 0; i < n; ++i) cout << ans[i] << ' ';
  return 0;
}
