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 = 500000;
const int A = 22;
vector<array<int, 2>> adj[N];
int sub[N];
void dfs_sub(int u) {
  sub[u] = 1;
  for (auto [c, w] : adj[u]) {
    dfs_sub(c);
    sub[u] += sub[c];
  }
  for (auto &e : adj[u]) {
    if (sub[e[0]] > sub[adj[u].back()[0]]) {
      swap(e, adj[u].back());
    }
  }
}
int max_length[1 << A];
int value;
int key;
int dfs_update(int u, int path, int depth) {
  int res = max_length[path ^ key] + value + depth;
  for (int i = 0; i < A; ++i) {
    res = max(res, max_length[path ^ key ^ (1 << i)] + value + depth);
  }
  for (auto [c, w] : adj[u]) {
    res = max(res, dfs_update(c, path ^ (1 << w), depth + 1));
  }
  return res;
}
void dfs_insert(int u, int path, int depth) {
  max_length[path ^ key] = max(max_length[path ^ key], depth - value);
  for (auto [c, w] : adj[u]) {
    dfs_insert(c, path ^ (1 << w), depth + 1);
  }
}
void dfs_erase(int u, int path) {
  max_length[path ^ key] = INT_MIN;
  for (auto [c, w] : adj[u]) {
    dfs_erase(c, path ^ (1 << w));
  }
}
int ans[N];
void dfs_dsu(int u) {
  for (auto [c, w] : adj[u]) {
    dfs_dsu(c);
    ans[u] = max(ans[u], ans[c]);
    if (c != adj[u].back()[0]) {
      dfs_erase(c, 0);
    } else {
      key ^= 1 << w;
      ++value;
    }
  }
  max_length[key] = max(max_length[key], -value);
  for (auto [c, w] : adj[u]) {
    if (c != adj[u].back()[0]) {
      ans[u] = max(ans[u], dfs_update(c, 1 << w, 1));
      dfs_insert(c, 1 << w, 1);
    }
  }
  ans[u] = max(ans[u], max_length[key] + value);
  for (int i = 0; i < A; ++i) {
    ans[u] = max(ans[u], max_length[key ^ (1 << i)] + value);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int n;
  cin >> n;
  for (int i = 1; i < n; ++i) {
    int p;
    char c;
    cin >> p >> c;
    adj[p - 1].push_back({i, c - 'a'});
  }
  fill(max_length, max_length + (1 << A), INT_MIN);
  dfs_sub(0);
  dfs_dsu(0);
  for (int i = 0; i < n; ++i) {
    cout << ans[i] << " ";
  }
  cout << "\n";
}
