#include<stdio.h>
#include<stdlib.h>

struct dlist {
    int number; // stores a number
    int frequency; // stores the frequency of the number
    struct dlist *next; // pointer to next cell
    struct dlist *prev; // pointer to previous cell
};
typedef struct dlist DList;

DList *insert_dlist(int number, DList *L);
DList *search_dlist(int number, DList *L);
DList *delete_dlist(int number, DList *L);
void print_dlist(DList *L);

int main()
{
	DList *L;
	L=NULL;

	char c;
	int n;
	do
	{
		scanf("%c", &c);
		switch(c)
		{
			case 'i':
			{
				scanf("%d", &n);
				L=insert_dlist(n, L);
				break;
			}
			case 's':
			{
				scanf("%d", &n);
				if(search_dlist(n, L) != NULL)
					printf("Number found\n");
				break;
			}
			case 'd':
			{
				scanf("%d", &n);
				L=delete_dlist(n, L);
				break;
			}
			case 'p':
			{
				print_dlist(L);
				break;
			}
			case 'e':
			{
				break;
			}
		}
	}
	while(c != 'e');
}

DList *insert_dlist(int number, DList *L)
{

	if(L == NULL)
	{
		L=(DList *)malloc(sizeof(DList));
		L->number=number;
		L->frequency=1;
		L->prev=NULL;
		L->next=NULL;
		return L;
	}
	DList *P;
	if((P=search_dlist(number, L)) != NULL)
	{
		(P->frequency)++;
		return L;
	}
	else
	{	
		DList *tmp;
		tmp=(DList *)malloc(sizeof(DList));
		tmp->number=number;
		tmp->frequency=1;
		tmp->prev=NULL;
		tmp->next=L;
		L->prev=tmp;
		return tmp;
	}
}
		
					
DList *search_dlist(int number, DList *L)
{
	if(L == NULL)
		return NULL;
	DList *P;
	P=L;
	while(P->next != NULL && P->number != number)
		P=P->next;
	if(P->number==number)
		return P;
	else
		return NULL;
	
}

DList *delete_dlist(int number, DList *L)
{
	DList *P;
	if((P=search_dlist(number, L)) == NULL)
		return L;
	else if(P==L && P->next==NULL)
	{
		free(P);
		return NULL;
	}
	else if(P != L && P->next !=NULL)
	{
		if(P->frequency==1)
		{
			P->prev->next=P->next;
			P->next->prev=P->prev;
			free(P);
			return L;
		}
		else
		{
			(P->frequency)--;
			return L;
		}
	}
	else if(P==L)
	{
		if(P->frequency==1)
		{
			DList *tmp;
			P->next->prev=NULL;
			tmp=P->next;
			free(P);
			return tmp;
		}
		
		else
		{
			(P->frequency)--;
			return L;
		}
	}
	else if(P->next==NULL)
	{
		if(P->frequency==1)
		{
			P->prev->next=NULL;
			free(P);
			return L;
		}
		
	}	
}

	
void print_dlist(DList *L)
{

	DList *P;
	P=L;
	while(P != NULL)
	{
		printf("number=%d frequency=%d\n", P->number, P->frequency);
		P=P->next;
	}
}