#include <bits/stdc++.h>
using namespace std;
const double EPS = -1e8;
const double Pi = acos(-1);
bool inline equ(double a, double b) { return fabs(a - b) < EPS; }
const int MAXN = 100010;
struct BIT {
  int sz;
  long long dat[MAXN];
  void init(int _sz) {
    sz = _sz;
    fill(dat, dat + sz + 1, 0ll);
  }
  void upd(int id, long long x) {
    for (int i = id; i <= sz; i += i & -i) dat[i] += x;
  }
  long long qry(int id) {
    long long res = 0ll;
    for (int i = id; i > 0; i -= i & -i) res += dat[i];
    return res;
  }
} bit1, bit2;
struct Tree {
  int n;
  int mom[19][MAXN];
  vector<pair<int, char> > g[MAXN];
  int ch[MAXN];
  Tree() : n(1) { ch[0] = -1; }
  void add(int v, char c) {
    mom[0][++n] = v;
    ch[n] = c;
    g[v].push_back({n, c});
  }
  void yutruli() {
    for (int k = (1); k <= (18); k++)
      for (int i = (1); i <= (n); i++) mom[k][i] = mom[k - 1][mom[k - 1][i]];
  }
  int anc(int u, int len) const {
    int v = u;
    for (int k = (0); k <= (18); k++)
      if (len & (1 << k)) v = mom[k][v];
    return v;
  }
  int sa[MAXN], rk[MAXN];
  void mkSA() {
    static int trk[MAXN];
    for (int i = (1); i <= (n); i++) sa[i] = i;
    auto cmp = [&](int a, int b) { return ch[a] < ch[b]; };
    sort(sa + 1, sa + 1 + n, cmp);
    for (int i = 1, cnt = 0; i <= n; i++) {
      if (cmp(sa[i - 1], sa[i])) cnt++;
      rk[sa[i]] = cnt;
    }
    for (int k = (0); k <= (18); k++) {
      auto cmp2 = [&](int a, int b) {
        return tie(rk[a], rk[mom[k][a]]) < tie(rk[b], rk[mom[k][b]]);
      };
      sort(sa + 1, sa + 1 + n, cmp2);
      for (int i = 1, cnt = 0; i <= n; i++) {
        if (cmp2(sa[i - 1], sa[i])) cnt++;
        trk[sa[i]] = cnt;
      }
      for (int i = (1); i <= (n); i++) rk[i] = trk[i];
    }
    for (int i = (1); i <= (n); i++) rk[sa[i]] = i;
  }
  int L[MAXN], R[MAXN];
  void dfs(int u, int p, int len, const Tree& t) {
    int tl = L[p], tr = R[p];
    if (tl > tr) {
      L[u] = 1, R[u] = 0;
    } else {
      L[u] = -1, R[u] = -1;
      int lb = tl, ub = tr;
      while (lb <= ub) {
        int mid = (lb + ub) / 2;
        int v = t.anc(t.sa[mid], len - 1);
        if (ch[u] <= t.ch[v]) {
          L[u] = mid;
          ub = mid - 1;
        } else
          lb = mid + 1;
      }
      lb = tl, ub = tr;
      while (lb <= ub) {
        int mid = (lb + ub) / 2;
        int v = t.anc(t.sa[mid], len - 1);
        if (t.ch[v] <= ch[u]) {
          R[u] = mid;
          lb = mid + 1;
        } else
          ub = mid - 1;
      }
      if (L[u] == -1 || R[u] == -1 || L[u] > R[u]) L[u] = 1, R[u] = 0;
    }
    for (pair<int, char> e : g[u]) dfs(e.first, u, len + 1, t);
  }
  void mkLR(const Tree& t) {
    L[1] = 1;
    R[1] = t.n;
    for (pair<int, char> e : g[1]) dfs(e.first, 1, 1, t);
  }
} tree[2];
struct Q {
  int t, v;
  char c;
};
int q;
Q qs[MAXN];
int main() {
  scanf("%d", &q);
  for (int i = (1); i <= (q); i++) {
    int t, v;
    char c[2];
    scanf("%d%d%s", &t, &v, c);
    t--;
    tree[t].add(v, *c);
    qs[i] = Q{t, v, *c};
  }
  tree[1].yutruli();
  tree[1].mkSA();
  tree[0].mkLR(tree[1]);
  bit1.init(tree[1].n);
  bit2.init(tree[1].n);
  long long ans = 1ll;
  bit1.upd(tree[0].L[1], 1);
  bit1.upd(tree[0].R[1] + 1, -1);
  bit2.upd(tree[1].rk[1], 1);
  int cnt[2] = {1, 1};
  for (int i = (1); i <= (q); i++) {
    if (qs[i].t == 0) {
      cnt[0]++;
      ans += bit2.qry(tree[0].R[cnt[0]]) - bit2.qry(tree[0].L[cnt[0]] - 1);
      bit1.upd(tree[0].L[cnt[0]], 1);
      bit1.upd(tree[0].R[cnt[0]] + 1, -1);
    } else {
      cnt[1]++;
      ans += bit1.qry(tree[1].rk[cnt[1]]);
      bit2.upd(tree[1].rk[cnt[1]], 1);
    }
    cout << ans << '\n';
  }
}
