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;
#pragma GCC optimize("Ofast")
#pragma GCC target( \
    "fma,sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#pragma GCC optimize("unroll-loops")
template <typename T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << '{';
  string sep;
  for (const auto &x : v) os << sep << x, sep = ", ";
  return os << '}';
}
template <typename T, size_t size>
ostream &operator<<(ostream &os, const array<T, size> &arr) {
  os << '{';
  string sep;
  for (const auto &x : arr) os << sep << x, sep = ", ";
  return os << '}';
}
template <typename A, typename B>
ostream &operator<<(ostream &os, const pair<A, B> &p) {
  return os << '(' << p.first << ", " << p.second << ')';
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << ' ' << H;
  debug_out(T...);
}
const int MAX_N = 5e5 + 5;
const int MAX_Z = 22;
vector<vector<pair<int, int>>> g(MAX_N);
multiset<int> best_way[1 << MAX_Z];
vector<int> sub(MAX_N), depth(MAX_N), mask(MAX_N), ans(MAX_N);
int dfs(int node) {
  sub[node] = 1;
  for (auto to : g[node]) {
    depth[to.first] = depth[node] + 1;
    mask[to.first] = mask[node] ^ to.second;
    sub[node] += dfs(to.first);
  }
  return sub[node];
}
int longest_path = 0;
int lca = -1;
void update_answer(int cur_mask, int cur_depth) {
  if (!best_way[cur_mask].empty()) {
    longest_path =
        max(longest_path, cur_depth + *best_way[cur_mask].rbegin() - 2 * lca);
  }
  for (int i = 0; i < MAX_Z; i++) {
    int other = cur_mask ^ (1 << i);
    if (best_way[other].empty()) continue;
    longest_path =
        max(longest_path, cur_depth + *best_way[other].rbegin() - 2 * lca);
  }
}
void add(int node, bool task, bool act_add) {
  if (task) {
    if (act_add)
      best_way[mask[node]].insert(depth[node]);
    else
      update_answer(mask[node], depth[node]);
  } else {
    best_way[mask[node]].erase(best_way[mask[node]].lower_bound(depth[node]));
  }
  for (auto to : g[node]) add(to.first, task, act_add);
}
void solve(int node, bool keep) {
  int mx = -1, big = -1;
  for (auto to : g[node])
    if (sub[to.first] > mx) mx = sub[to.first], big = to.first;
  for (auto to : g[node])
    if (to.first != big) {
      solve(to.first, false);
      ans[node] = max(ans[node], ans[to.first]);
    }
  if (~big) {
    solve(big, true);
    ans[node] = max(ans[node], ans[big]);
  }
  lca = depth[node];
  longest_path = 0;
  update_answer(mask[node], depth[node]);
  best_way[mask[node]].insert(depth[node]);
  for (auto to : g[node]) {
    if (to.first != big) {
      add(to.first, true, false);
      add(to.first, true, true);
    }
  }
  if (node == 0) 47;
  ans[node] = max(ans[node], longest_path);
  if (!keep) {
    best_way[mask[node]].erase(best_way[mask[node]].lower_bound(depth[node]));
    for (auto to : g[node]) add(to.first, false, false);
  }
}
int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin >> n;
  for (int i = 1; i < n; i++) {
    int st;
    char c;
    cin >> st >> c;
    --st;
    g[st].emplace_back(i, 1 << (c - 'a'));
  }
  dfs(0);
  solve(0, true);
  for (int i = 0; i < n; i++) cout << ans[i] << ' ';
  cout << '\n';
  return 0;
}
