URAL 1992

#include <cstdio>  
#include <cstring>  
#include <algorithm>  
#include <vector>  
#define N 500010  
using namespace std;  
  
int lehead[N],rehead[N];  
struct Node{  
    int val,next;  
}node[N];  
int cnt;  
  
void addedge(int u,int val,int * lehead){  
    node[cnt].val=val;  
    node[cnt].next=lehead[u];  
    lehead[u]=cnt++;  
}  
  
int main(){  
    int n,m,now=1;  
    int c,p;  
    char s[20];  
    scanf("%d %d",&n,&m);  
    memset(lehead,-1,sizeof(lehead));  
    memset(rehead,-1,sizeof(rehead));  
    cnt=0;  
    for(int j=1;j<=n;j++){  
        scanf("%s",s);  
        if(!strcmp(s,"learn")){  
            scanf("%d %d",&c,&p);  
            addedge(c,p,lehead);  
        }  
        else if(!strcmp(s,"rollback")){  
            scanf("%d",&c);  
            addedge(c,node[lehead[c]].val,rehead);  
            lehead[c]=node[lehead[c]].next;  
        }  
        else if(!strcmp(s,"relearn")){  
            scanf("%d",&c);  
            addedge(c,node[rehead[c]].val,lehead);  
            rehead[c]=node[rehead[c]].next;  
        }  
        else if(!strcmp(s,"clone")){  
            scanf("%d",&c);  
            now++;  
            lehead[now]=lehead[c];  
            rehead[now]=rehead[c];  
        }  
        else{  
            scanf("%d",&c);  
            if(lehead[c]==-1) printf("basic\n");  
            else printf("%d\n",node[lehead[c]].val);  
        }  
    }  
    return 0;  
}