#include <bits/stdc++.h>
using namespace std;
const int maxn = 100055, dig_max = 30;
struct ST {
  ST *ch[26];
  int val;
  ST() {
    for (int i = 0; i < (26); ++i) ch[i] = 0;
    val = 0;
  }
  ST(ST *b) {
    for (int i = 0; i < (26); ++i) ch[i] = b->ch[i];
    val = b->val;
  }
  void insert(char *s, int pri_val) {
    ST *p = this;
    for (int i = 0; s[i]; ++i) {
      int c = s[i] - 'a';
      if (p->ch[c] != NULL)
        p->ch[c] = new ST(p->ch[c]);
      else
        p->ch[c] = new ST;
      p = p->ch[c];
    }
    p->val = pri_val;
  }
  int query(char *s) {
    ST *p = this;
    for (int i = 0; s[i]; ++i) {
      int c = s[i] - 'a';
      if (p->ch[c] == NULL) return -1;
      p = p->ch[c];
    }
    return p->val <= 0 ? -1 : p->val;
  }
} st[maxn];
struct NT {
  NT *son[2];
  int val;
  NT() {
    son[0] = son[1] = NULL;
    val = 0;
  }
  NT(NT *b) {
    son[0] = b->son[0], son[1] = b->son[1];
    val = b->val;
  }
  void insert(int x, int del) {
    NT *p = this;
    for (int i = dig_max; i > (-1); --i) {
      int st = (x >> i) & 1;
      if (p->son[st] != NULL)
        p->son[st] = new NT(p->son[st]);
      else
        p->son[st] = new NT;
      p = p->son[st];
      p->val += del;
    }
  }
  int get_rk(int x) {
    int ans = 0;
    NT *p = this;
    for (int i = dig_max; i > (-1); --i) {
      int st = (x >> i) & 1;
      if (st == 1 && p->son[0] != NULL) ans += p->son[0]->val;
      p = p->son[st];
    }
    return ans;
  }
} nt[maxn];
char s[maxn], op[20];
int main() {
  int n;
  scanf("%d", &n);
  nt[0] = new NT;
  st[0] = new ST;
  for (int i = 1; i < (n + 1); ++i) {
    scanf("%s", op, s);
    if (op[0] == 's') {
      int x;
      scanf("%s %d", s, &x);
      st[i] = new ST(st[i - 1]);
      nt[i] = new NT(nt[i - 1]);
      int pre_v = st[i].query(s);
      if (pre_v != x) {
        if (pre_v != -1) nt[i].insert(pre_v, -1);
        nt[i].insert(x, 1);
        st[i].insert(s, x);
      }
    } else if (op[0] == 'q') {
      scanf("%s", s);
      st[i] = new ST(st[i - 1]);
      nt[i] = new NT(nt[i - 1]);
      int pre_v = st[i].query(s);
      if (pre_v != -1) pre_v = nt[i].get_rk(pre_v);
      printf("%d\n", pre_v);
    } else if (op[0] == 'r') {
      scanf("%s", s);
      st[i] = new ST(st[i - 1]);
      nt[i] = new NT(nt[i - 1]);
      int pre_v = st[i].query(s);
      if (pre_v != -1) {
        nt[i].insert(pre_v, -1);
        st[i].insert(s, 0);
      }
    } else {
      int x;
      scanf("%d", &x);
      st[i] = new ST(st[i - 1 - x]);
      nt[i] = new NT(nt[i - 1 - x]);
    }
    fflush(stdout);
  }
  return 0;
}
