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;
template <class T>
using vc = vector<T>;
template <class T>
using vvc = vc<vc<T>>;
template <class T>
void mkuni(vector<T>& v) {
  sort(v.begin(), v.end());
  v.erase(unique(v.begin(), v.end()), v.end());
}
long long rand_int(long long l, long long r) {
  static mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());
  return uniform_int_distribution<long long>(l, r)(gen);
}
template <class T>
void print(T x, int suc = 1) {
  cout << x;
  if (suc == 1)
    cout << '\n';
  else
    cout << ' ';
}
template <class T>
void print(const vector<T>& v, int suc = 1) {
  for (int i = 0; i < v.size(); i++)
    print(v[i], i == (int)(v.size()) - 1 ? suc : 2);
}
const int INF = 0x3f3f3f;
const int maxn = 2e6 + 7;
const int mod = 1e9 + 7;
const long long inf = 1e18;
struct edge {
  int to, nxt, weight;
} e[maxn << 1];
int n, sz[maxn], tim;
int head[maxn << 1], tot;
int parent[maxn], hson[maxn], dis[maxn], in[maxn], out[maxn], dep[maxn],
    id[maxn];
int ans[maxn];
int book[1 << 24];
void init() {
  tot = 0;
  memset(head, -1, sizeof(head));
}
void add(int u, int v, int w) {
  e[tot].to = v;
  e[tot].nxt = head[u];
  e[tot].weight = w;
  head[u] = tot++;
}
void dfs1(int u, int fa) {
  parent[u] = fa;
  sz[u] = 1;
  in[u] = ++tim, dep[u] = dep[fa] + 1, id[tim] = u;
  for (int i = head[u], v; i != -1; i = e[i].nxt) {
    v = e[i].to;
    dis[v] = dis[u] ^ e[i].weight;
    dfs1(v, u);
    sz[u] += sz[v];
    if (sz[v] > sz[hson[u]]) hson[u] = v;
  }
  out[u] = tim;
}
void dfs2(int u, bool keep) {
  for (int i = head[u]; ~i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == hson[u]) continue;
    dfs2(v, 0);
    ans[u] = max(ans[u], ans[v]);
  }
  if (hson[u]) dfs2(hson[u], 1), ans[u] = max(ans[u], ans[hson[u]]);
  if (book[dis[u]]) ans[u] = max(ans[u], book[dis[u]] - dep[u]);
  for (int i = 0; i <= 21; ++i)
    if (book[dis[u] ^ (1 << i)])
      ans[u] = max(ans[u], book[dis[u] ^ (1 << i)] - dep[u]);
  book[dis[u]] = max(book[dis[u]], dep[u]);
  for (int i = head[u]; ~i; i = e[i].nxt) {
    int v = e[i].to;
    if (v == hson[u]) continue;
    for (int j = in[v]; j <= out[v]; ++j) {
      int x = id[j];
      if (book[dis[x]])
        ans[u] = max(ans[u], book[dis[x]] + dep[x] - 2 * dep[u]);
      for (int k = 0; k <= 21; ++k)
        if (book[dis[x] ^ (1 << k)])
          ans[u] = max(ans[u], book[dis[x] ^ (1 << k)] + dep[x] - 2 * dep[u]);
    }
    for (int j = in[v]; j <= out[v]; ++j) {
      book[dis[id[j]]] = max(book[dis[id[j]]], dep[id[j]]);
    }
  }
  if (!keep)
    for (int i = in[u]; i <= out[u]; ++i) book[dis[id[i]]] = 0;
}
int main() {
  init();
  cin >> n;
  int x;
  char ch;
  for (int i = 2; i <= n; ++i) {
    cin >> x >> ch;
    add(x, i, 1ll << (ch - 'a'));
  }
  dfs1(1, 0);
  for (int i = 1; i <= n; ++i) {
    ;
  }
  dfs2(1, 1);
  for (int i = 1; i <= n; ++i) cout << ans[i] << " ";
}
