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

#define TRUE 1
#define FALSE 0

typedef struct node{
	int item;
	struct node *prox;
	struct node *ant;

} NO;

typedef struct lista{
	NO *ini;
	NO *fim;
	int tam;

} LISTA;

LISTA *criaLista(){
	LISTA *lista = NULL;

	lista = (LISTA *) malloc(sizeof(LISTA));
	if(lista == NULL) printf("ERRO DE CRIACAO DE LISTA\n\tREINICIE O PROGRAMA\n\n");
	else{
		lista->ini = NULL;
		lista->fim = NULL;
		lista->tam = 0;
	}

	return lista;
}

void insere_no_inicio(LISTA *l){
	NO *p = NULL;
	int item;

	//recebendo item
	scanf("%d", &item);
	fgetc(stdin);

	p = (NO *) malloc(sizeof(NO));
	if(p != NULL){
		p->item = item;
		p->ant = NULL;
		p->prox = l->ini;

		if(l->ini == NULL){
			l->fim = p;
		}
		else{
			l->ini->ant = p;
		}

		l->ini = p;
		l->tam++;
	}
}

void insere_no_fim(LISTA *l){
	NO *p = NULL;
	int item;

	//recebendo item
	scanf("%d", &item);
	fgetc(stdin);

	p = (NO *) malloc(sizeof(NO));
	if(p != NULL){
		p->item = item;
		p->prox = NULL;
		p->ant = l->fim;

		if(l->ini == NULL){
			l->ini = p;
		}
		else{
			l->fim->prox = p;
		}

		l->fim = p;
		l->tam++;
	}
}

void remove_do_fim(LISTA *l){
	NO *p = NULL;

	p = l->fim;
	if(p != NULL){
		l->fim = p->ant;
		if(p->ant != NULL) p->ant->prox = NULL;
		else l->ini = NULL;
		p->ant = NULL;

		printf("%d\n", p->item);

		free(p);
		l->tam--;
	}
}

void remove_do_inicio(LISTA *l){
	NO *p = NULL;

	p = l->ini;
	if(p != NULL){
		l->ini = p->prox;
		if(p->prox != NULL) p->prox->ant = NULL;
		else l->fim = NULL;
		p->prox = NULL;

		printf("%d\n", p->item);

		free(p);
		l->tam--;
	}
}

int remove_valor(LISTA *l, int valor){
	NO *p = NULL;
	int ocorrencias;

	ocorrencias = 0;
	p = l->ini;
	while(p != NULL){
		if(p->item == valor){
			if(p != l->ini) p->ant->prox = p->prox;
			else l->ini = p->prox;

			if(p != l->fim) p->prox->ant = p->ant;
			else l->fim = p->ant;

			l->tam--;
			free(p);
			ocorrencias++;
		}
		p = p->prox;
	}

	return ocorrencias;
}

void remove_por_valor(LISTA *l){
	int valor;
	int ocorrencias;

	scanf("%d", &valor);
	fgetc(stdin);

	ocorrencias = remove_valor(l, valor);
	printf("%d\n", ocorrencias);
}

int remove_por_posicao(LISTA *l){
	NO *p = NULL;
	int valor = 0;
	int pos;
	int i;

	scanf("%d", &pos);
	fgetc(stdin);

	i = 1;
	p = l->ini;
	while(p != NULL){
		if(i == pos) break;
		i++;
		p = p->prox;
	}

	if(p == NULL){
		return FALSE;
	}

	valor = p->item;

	if(p != l->ini) p->ant->prox = p->prox;
	else l->ini = p->prox;

	if(p != l->fim) p->prox->ant = p->ant;
	else l->fim = p->ant;
	free(p);
	l->tam--;
	printf("%d\n", valor);
	return valor;
}

void substitui_por_valor(LISTA *l){
	NO *p = NULL;
	int valor;
	int item;

	scanf("%d %d", &item, &valor);
	fgetc(stdin);

	p = l->ini;
	while(p != NULL){
		if(p->item == item) break;
		p = p->prox;
	}

	if(p != NULL) p->item = valor;
}

int ocorrencias_por_valor(LISTA *l){
	NO *p = NULL;
	int valor;
	int ocorrencias;

	scanf("%d", &valor);
	fgetc(stdin);

	ocorrencias = 0;
	p = l->ini;
	while(p != NULL){
		if(p->item == valor) ocorrencias++;
		p = p->prox;
	}

	printf("%d\n", ocorrencias);
	return ocorrencias;
}

void printL(LISTA *l){
	NO *p = NULL;

	printf("\n");

	p = l->ini;
	while(p != NULL){
		printf("%d\n", p->item);
		p = p->prox;
	}
}

void apagarLista(LISTA *l){
	NO *p = NULL;
	NO *aux = NULL;

	p = l->ini;
	while(p != NULL){
		aux = p;
		p = p->prox;
		free(aux);
	}
	free(l);
}

int main (int argc, char *argv[]){
	LISTA *l = NULL;
	char opt;

	l = criaLista();
	while(opt != 'X'){
		opt = getc(stdin);
		fgetc(stdin);

		if(opt == 'I'){
			insere_no_inicio(l);
			continue;
		}

		if(opt == 'F'){
			insere_no_fim(l);
			continue;
		}

		if(opt == 'P'){
			remove_do_fim(l);
			continue;
		}

		if(opt == 'D'){
			remove_do_inicio(l);
			continue;
		}

		if(opt == 'V'){
			remove_por_valor(l);
			continue;
		}

		if(opt == 'E'){
			remove_por_posicao(l);
			continue;
		}

		if(opt == 'T'){
			substitui_por_valor(l);
			continue;
		}

		if(opt == 'C'){
			ocorrencias_por_valor(l);
			continue;
		}
	}

	printL(l);
	apagarLista(l);
	return 0;
}