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;
struct data {
  struct hash_table {
    static const int n = 5000010, mod = 15000007;
    int h[n];
    int val[n];
    int f, p, c, link[n], last[mod];
    hash_table() : f(0), p(0), c(0) { memset(last, -1, sizeof last); }
    int *find(int hash) {
      for (f = -1, p = last[hash % mod]; p != -1; f = p, p = link[p])
        if (h[p] == hash) return &val[p];
      return NULL;
    }
    void set(int hash, int num) {
      if (find(hash) != NULL)
        val[p] = num;
      else {
        h[c] = hash;
        val[c] = num;
        hash %= mod;
        link[c] = last[hash];
        last[hash] = c++;
      }
    }
    void erase(int hash) {
      if (find(hash) == NULL) return;
      if (f == -1)
        last[hash % mod] = link[p];
      else
        link[f] = link[p];
    }
  } mp;
  int a, x;
  data() : a(0), x(0) {}
} dp;
struct data2 {
  int a, x;
  vector<pair<int, int>> mp;
  data2() : a(0), x(0) {}
};
const int oo = -1e9;
const int N = 5 * 1e5 + 5;
int ans[N], sz[N];
vector<pair<int, int>> adj[N];
pair<int, int> bigch[N];
void getsz(int u, int p) {
  sz[u] = 1;
  int mx = 0;
  for (auto v : adj[u])
    if (v.first != p) {
      getsz(v.first, u);
      sz[u] += sz[v.first];
      if (sz[v.first] > mx) mx = sz[v.first], bigch[u] = v;
    }
}
vector<pair<int, int>> *rec[N];
data2 *mp[N];
int *it;
void dfs(int u, int f, bool keep) {
  for (auto v : adj[u])
    if (v.first != f && v.first != bigch[u].first) {
      dfs(v.first, u, false);
      ans[u] = max(ans[u], ans[v.first]);
    }
  int id = bigch[u].first, m = bigch[u].second;
  if (id != -1) {
    dfs(id, u, true);
    mp[u] = mp[id];
    rec[u] = rec[id];
    ans[u] = max(ans[u], max(1, ans[id]));
    dp.x ^= m, ++dp.a;
    mp[u]->x ^= m, ++mp[u]->a;
    it = dp.mp.find(m ^ dp.x);
    if (it == NULL || *it < 1 - dp.a) {
      rec[u]->push_back({m ^ dp.x, (it == NULL ? oo : *it)});
      dp.mp.set(m ^ dp.x, 1 - dp.a);
      mp[u]->mp.push_back({m ^ mp[u]->x, 1 - mp[u]->a});
    }
    for (auto k : adj[u])
      if (k.first != id && k.first != f) {
        auto &ch = *mp[k.first];
        for (auto i : ch.mp) {
          it = dp.mp.find(i.first ^ ch.x ^ k.second ^ dp.x);
          if (it != NULL)
            ans[u] = max(ans[u], *it + dp.a + i.second + ch.a + 1);
          for (int j = 0; j < 26; ++j) {
            it = dp.mp.find(i.first ^ ch.x ^ k.second ^ 1 << j ^ dp.x);
            if (it != NULL)
              ans[u] = max(ans[u], *it + dp.a + i.second + ch.a + 1);
          }
        }
        for (int j = 0; j < 26; ++j) {
          it = dp.mp.find(k.second ^ 1 << j ^ dp.x);
          if (it != NULL) ans[u] = max(ans[u], *it + dp.a + 1);
        }
        it = dp.mp.find(k.second ^ dp.x);
        if (it != NULL) ans[u] = max(ans[u], *it + dp.a + 1);
        if (it == NULL || *it < 1 - dp.a) {
          rec[u]->push_back({k.second ^ dp.x, (it == NULL ? oo : *it)});
          dp.mp.set(k.second ^ dp.x, 1 - dp.a);
          mp[u]->mp.push_back({k.second ^ mp[u]->x, 1 - mp[u]->a});
        }
        for (auto i : ch.mp) {
          it = dp.mp.find(i.first ^ ch.x ^ dp.x ^ k.second);
          if (it == NULL || *it < i.second + ch.a + 1 - dp.a) {
            rec[u]->push_back(
                {i.first ^ ch.x ^ dp.x ^ k.second, (it == NULL ? oo : *it)});
            dp.mp.set(i.first ^ ch.x ^ dp.x ^ k.second,
                      i.second + ch.a + 1 - dp.a);
            mp[u]->mp.push_back({i.first ^ ch.x ^ mp[u]->x ^ k.second,
                                 i.second + ch.a + 1 - mp[u]->a});
          }
        }
      }
    it = dp.mp.find(dp.x);
    if (it != NULL) ans[u] = max(ans[u], *it + dp.a);
    for (int i = 0; i < 26; ++i) {
      it = dp.mp.find(1 << i ^ dp.x);
      if (it != NULL) ans[u] = max(ans[u], *it + dp.a);
    }
  } else {
    rec[u] = new vector<pair<int, int>>();
    mp[u] = new data2();
  }
  if (!keep) {
    if (id != -1) dp.x ^= m, --dp.a;
    for (auto i = rec[u]->rbegin(); i != rec[u]->rend(); ++i) {
      if (i->second == oo)
        dp.mp.erase(i->first);
      else
        dp.mp.set(i->first, i->second);
    }
  }
};
int main() {
  ios_base::sync_with_stdio(0), cin.tie(0);
  int n;
  cin >> n;
  char c;
  for (int i = 1, u; i < n; ++i) {
    cin >> u >> c;
    adj[--u].push_back({i, 1 << (c - 'a')});
    adj[i].push_back({u, 1 << (c - 'a')});
    bigch[i].first = -1;
  }
  bigch[0].first = -1;
  getsz(0, -1);
  dfs(0, -1, true);
  for (int i = 0; i < n; ++i) cout << ans[i] << " \n"[i == n];
  return 0;
}
