#include <stdio.h>
#include <stdlib.h>
struct Element **AM;
struct Element
{
struct Element *prev, *next;
int u,key;
};
struct Element* InitDoubleLinkedList()
{
struct Element *DL_List;
DL_List = malloc(sizeof(struct Element));
DL_List->prev=DL_List;
DL_List->next=DL_List;
DL_List->u=-999999;
DL_List->key=-999999;
return DL_List;
}
void InsertAfter(int h, struct Element* y)
{
struct Element* x=AM[h]->prev;
struct Element* z=AM[h];
x->next=y;
y->prev=x;
y->next=z;
z->prev=y;
}
void Assign(int k,int u,int m)
{
struct Element *check;
struct Element *new;
int h=k%m;
if(AM[h]->next!=AM[h])
{
for(check = AM[h]->next; check != AM[h] && k!=check->key; check=check->next);
if(check==AM[h])
{
new=malloc(sizeof(struct Element));
new->u=u;
new->key=k;
InsertAfter(h,new);
}
else
{
check->u=u;
}
}
else
{
new=malloc(sizeof(struct Element));
new->u=u;
new->key=k;
InsertAfter(h,new);
}
}
void AT(int k,int m)
{
int h=k%m;
struct Element *find;
for (find=AM[h]->next;find!=AM[h] && k!=find->key;find=find->next);
if (find==AM[h])
{
printf("0\n");
}
else
{
printf("%d\n",find->u);
}
}
int main (int argc, char const *argv[])
{
int n,m,k=0,El=0,i;
char str[7];
scanf("%d", &n);
scanf("%d", &m);
AM = malloc(m * sizeof(struct Element*));
for(i = 0; i < m;i++)
{
AM[i]=InitDoubleLinkedList();
}
for(i = 0; i < n; i++)
{
scanf("%s",str);
scanf("%d",&k );
if(str[2]=='\0')
{
AT(k,m);
}
else
{
scanf("%d",&El );
Assign(k,El,m);
}
}
return 0;
}