#include <stdio.h>
#include <string.h>

#define MAXSIZE 11

typedef char ElemType[8];
typedef struct {
  ElemType data;
  int cur;        /* index of next node */
} NodeType;

NodeType space[MAXSIZE];

typedef struct {
  int elem;       /* index of head node */
  int length;
  int listsize;
} SLinkList;

void InitSpace_SL(void)
{
  int i;
  memset(space, 0, sizeof(space));
  for (i = 0; i < MAXSIZE - 1; ++i) {
    space[i].cur = i + 1;
  }
  space[MAXSIZE-1].cur = 0;
}

int LocateElem_SL(SLinkList *S, ElemType e)
{
  int i;
  i = S->elem;
  while (i && strcmp(space[i].data, e)) {
    i = space[i].cur;
  }
  return i;
}

int Malloc_SL(void)
{
  int i;

  i = space[0].cur;
  if (i) {
    space[0].cur = space[i].cur;
  }
  return i;
}

void Free_SL(int k)
{
  space[k].cur = space[0].cur;
  space[0].cur = k;
}

void InitList(SLinkList *S)
{
  InitSpace_SL();
  S->elem = Malloc_SL();
  space[S->elem].cur = 0;
  S->length = 0;
  S->listsize = MAXSIZE - 2;
}

void ListInsert_SL(SLinkList *S, int i, ElemType e)
{
  int j, k, count;

  if (i < 1 || i > S->length+1) { return; }
  k = Malloc_SL();
  if (k) {
    sprintf(space[k].data, "%s", e);
    j = S->elem;
    for (count = 1; count < i; ++count) {
      j = space[j].cur;
    }
    space[k].cur = space[j].cur;
    space[j].cur = k;
    S->length += 1;
  }
}

void ListDelete_SL(SLinkList *S, int i)
{
  int j, k, count;

  if (i < 1 || i > S->length) { return; }
  j = S->elem;
  for (count = 1; count < i; ++count) {
    j = space[j].cur;
  }
  k = space[j].cur;
  space[j].cur = space[k].cur;
  Free_SL(k);
  S->length -= 1;
}

void ListPrint_SL(SLinkList *S)
{
  int i;

  for (i = 0; i < MAXSIZE; ++i) {
    printf("%-8s%2d\n", space[i].data, space[i].cur);
  }
  for (i = 0; i < 20; ++i) {
    printf("*");
  }
  printf("\n");
}

int main(void)
{
  char cmd[10];
  ElemType name;
  int i;
  SLinkList S;

  InitList(&S);
  while (scanf("%s", cmd) != EOF) {
    switch (cmd[2]) {
    case 's':  /* insert */
      scanf("%d", &i);
      scanf("%s", name);
      ListInsert_SL(&S, i, name);
      break;
    case 'l':  /* delete */
      scanf("%d", &i);
      ListDelete_SL(&S, i);
      break;
    case 'a':  /* search */
      scanf("%s", name);
      i = LocateElem_SL(&S, name);
      printf("%2d\n", i);
      for (i = 0; i < 20; ++i) {
        printf("*");
      }
      printf("\n");
      break;
    case 'o':  /* show */
      ListPrint_SL(&S);
      break;
    }
  }
  return 0;
}

/**************************************************************
	Problem: 2139
	User: admin
	Language: C
	Result: Accepted
	Time:17 ms
	Memory:1148 kb
****************************************************************/