#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, DList);
DList search_dlist(int , DList );
DList delete_dlist(int , DList );
void print_dlist(DList );
main()
{
	char c;
	DList p;
	DList head;
	int number;
	scanf("%c",&c);
	if (c=='i')
	{	scanf("%d",&number);
        	p=(DList)(malloc(sizeof (struct dlist)));
        	p->number=number;
		p->prev=NULL;
		head=p;
		p->next=NULL;
		p->frequency=1;
	}	
	else 
	{	printf("The List is empty");
		return;
	}
	for(;1;)
	{
		scanf("%c",&c);
		if (c== 'i')
		{	
			scanf("%d",&number);
		//	p=(Dlist)(malloc(sizeof (struct dlist)));	
			head=insert_dlist(number,head);
		}
		if (c=='s')
		{
			scanf("%d",&number);
			if( search_dlist(number, head)->number==number)
			printf("The number is found");
			else 
			printf("The number is not found");
		}
		if( c=='d')
		{
			scanf("%d",&number);
			head= delete_dlist( number, head);
		}
		if(c=='p')
		 print_dlist(head);
		if(c=='e')
		return;
	}
}

DList insert_dlist(int number,DList head)
{
	DList p;
	DList l;
	p=  search_dlist( number, head);
	if(p==NULL)
	{
		l = (DList)malloc(sizeof(struct dlist));
		l->next=NULL;
		l->prev=NULL;
		l->frequency =1;
		l->number=number;
		head=l;
	}		
	else if(p->next==NULL&&p->number!=number)	
	{	l=(DList)(malloc(sizeof (struct dlist)));
		l->number=number;
		l->next=head;
		head=l;
		l->prev=NULL;
		l->next->prev=l;
		l->frequency=1;
		return head;
	}
	else
		p->frequency+=1;
		return head;
}
	
DList search_dlist( int number, DList head)
{
	DList p;
	p=head;
	if(p==NULL||p->number==number||p->next==NULL)
	return p;
	else
	return  search_dlist( number, p->next);
	
}

DList delete_dlist( int number,DList head)
{
	DList p;
	p=search_dlist(number,head);
	if(p->next==NULL&&p->number!=number)
	{
		printf("Number not found\n");
		return;
	}
	else if(p->frequency>1)
	p->frequency-=1;
	else if(p->next==NULL&&p->prev==NULL)
	{
		head=NULL;
	}
	else if(p->next==NULL)
	{
		p->prev->next=NULL;
	}
	else if(p->prev==NULL)
	{
		printf("hello %d\n",p->next->number);
		p->next->prev=NULL;
		head = p->next;
	}
	else
	{
		p->prev->next=p->next;
		p->next->prev=p->prev;
	}
	
	/*if(p->next==NULL&&p->number!=number)
	printf("Number not found");
	else if(p->frequency==1&&p->next!=NULL&&p->prev!=NULL)
	{	p->next->prev=p->prev;
		p->prev->next=p->next;
		free(p); 
		
	}
	else
	p->frequency-=1;
	*/
return head;
}
void print_dlist(DList head)
{
	if(head==NULL)
	return;
	printf("(%-3d %3d)",head->number,head->frequency);
	if(head->next==NULL)
	return;
	print_dlist(head->next);
}