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;
inline int readChar();
template <class T = int>
inline T readInt();
template <class T>
inline void writeInt(T first, char end = 0);
inline void writeChar(int first);
inline void writeWord(const char *s);
static const int buf_size = 4096;
inline int getChar() {
  static char buf[buf_size];
  static int len = 0, pos = 0;
  if (pos == len) pos = 0, len = fread(buf, 1, buf_size, stdin);
  if (pos == len) return -1;
  return buf[pos++];
}
inline int readChar() {
  int c = getChar();
  while (c <= 32) c = getChar();
  return c;
}
template <class T>
inline T readInt() {
  int s = 1, c = readChar();
  T first = 0;
  if (c == '-') s = -1, c = getChar();
  while ('0' <= c && c <= '9') first = first * 10 + c - '0', c = getChar();
  return s == 1 ? first : -first;
}
static int write_pos = 0;
static char write_buf[buf_size];
inline void writeChar(int first) {
  if (write_pos == buf_size)
    fwrite(write_buf, 1, buf_size, stdout), write_pos = 0;
  write_buf[write_pos++] = first;
}
template <class T>
inline void writeInt(T first, char end) {
  if (first < 0) writeChar('-'), first = -first;
  char s[24];
  int n = 0;
  while (first || !n) s[n++] = '0' + first % 10, first /= 10;
  while (n--) writeChar(s[n]);
  if (end) writeChar(end);
}
inline void writeWord(const char *s) {
  while (*s) writeChar(*s++);
}
struct Flusher {
  ~Flusher() {
    if (write_pos) fwrite(write_buf, 1, write_pos, stdout), write_pos = 0;
  }
} flusher;
int main(void) {
  srand(time(0));
  cout << fixed << setprecision(7);
  cerr << fixed << setprecision(7);
  int n;
  n = readInt();
  static vector<pair<int, char> > s[1 << 20];
  for (int i = 2; i <= n; ++i) {
    int fr = readInt();
    char ch = readChar();
    s[fr].push_back(make_pair(i, ch));
  }
  static int ans[1 << 20];
  static pair<int, int> add[1 << 20];
  static unordered_map<int, int> M[1 << 20];
  const int lim = 1 << 22;
  auto Merge = [&](int a, int b, int up) {
    if (M[b].count(add[b].first))
      ans[up] = max(ans[up], M[b][add[b].first] + add[b].second);
    for (int k = 1; k < lim; k <<= 1) {
      const int b_mask = k ^ add[b].first;
      if (M[b].count(b_mask))
        ans[up] = max(ans[up], M[b][b_mask] + add[b].second);
    }
    if (M[a].size() < M[b].size()) swap(M[a], M[b]), swap(add[a], add[b]);
    for (auto it : M[b]) {
      const int real_mask = it.first ^ add[b].first;
      const int real_len = it.second + add[b].second;
      const int amask = real_mask ^ add[a].first;
      if (M[a].count(amask))
        ans[up] = max(ans[up], real_len + M[a][amask] + add[a].second);
      for (int k = 1; k < lim; k <<= 1)
        if (M[a].count(k ^ amask))
          ans[up] = max(ans[up], M[a][k ^ amask] + add[a].second + real_len);
    }
    for (auto it : M[b]) {
      const int real_mask = it.first ^ add[b].first;
      const int real_len = it.second + add[b].second;
      const int next_mask = real_mask ^ add[a].first;
      if (!M[a].count(next_mask))
        M[a][next_mask] = real_len - add[a].second;
      else
        M[a][next_mask] = max(M[a][next_mask], real_len - add[a].second);
    }
    M[b].clear();
  };
  function<void(int, int)> dfs = [&](int node, int prev) {
    for (auto it : s[node])
      if (it.first != prev) {
        dfs(it.first, node);
        ans[node] = max(ans[node], ans[it.first]);
        add[it.first].first ^= 1 << (it.second - 'a');
        add[it.first].second++;
        Merge(node, it.first, node);
      }
    if (!M[node].count(add[node].first))
      M[node][add[node].first] = -add[node].second;
  };
  dfs(1, 0);
  for (int i = 1; i <= n; ++i) writeInt(ans[i], " \n"[i == n]);
  return 0;
}
