dlist dlist_create ()
{
	dlist r = (dlist) malloc (sizeof (dlist_node));
    r->next = r;
    r->prev = r;
    return r;
}

dlist dlist_put_first (int x, dlist s)
{
    dlist r = (dlist) malloc (sizeof (dlist_node));
    r->value = x;
    r->prev = s;
	r->next = s->next;
	s -> next -> prev = r;
	s -> next = r;
    return r;
}

dlist dlist_put_last (int x, dlist s)
{
    dlist r = (dlist) malloc (sizeof (dlist_node));
    r->value = x;
    r->next = s;
	r->prev = s->prev;
	s -> prev -> next = r;
	s -> prev = r;
    return r;
}

void dlist_write_forward (dlist s)
{
	dlist z= s->next;
	while ( z != s)
	{
		printf("%d",z->value);
		z = z->next;
		if (z!=s)
			printf(" ");
	}
}

void dlist_write_backward (dlist s)
{
	dlist z= s->prev;
	while ( z != s)
	{
		printf("%d",z->value);
		z = z->prev;
		if (z!=s)
			printf(" ");
	}
}

void dlist_remove_first (dlist s)
{
	dlist t = s -> next;
	s->next = t->next;
	(t->next)->prev = s;
	free(t);
}

void dlist_remove_last (dlist s)
{
	dlist t = s -> prev;
	s->prev = t->prev;
	(t->prev)->next = s;
	free(t);
}

dlist dlist_find_first (int x, dlist s)
{
    dlist p = s->next;
    if(p != NULL)
    {
        while(p->next != NULL)
        {
            if(p->value == x)
                return p;
            p = p->next;
        }
    }
    return NULL;
}

dlist dlist_find_last (int x, dlist s)
{
    dlist p = s->prev;
    if(p != NULL)
    {
        while(p->prev != NULL)
        {
            if(p->value == x)
                return p;
            p = p->prev;
        }
    }
    return NULL;
}

void dlist_put_after (int x, dlist s, dlist p)
{
	if (p==NULL)
	{
		dlist_put_first (x, s);
	}
	else
	{
		dlist r = (dlist) malloc (sizeof (dlist_node));
		while (s !=p)
		{
			s=s->next;
		}
		r->value = x;
		r->prev = s;
		r->next = s->next;
		s -> next -> prev = r;
		s -> next = r;
	}
}

void dlist_put_before (int x, dlist s, dlist p)
{
    if (p==NULL)
	{
		dlist_put_last (x, s);
	}
	else
	{
		dlist r = (dlist) malloc (sizeof (dlist_node));
		while (s !=p)
		{
			s=s->prev;
		}
		r->value = x;
		r->next = s;
		r->prev = s->prev;
		s -> prev -> next = r;
		s -> prev = r;
	}
}

void dlist_remove (dlist s, dlist p)
{
	if (p != NULL)
	{
		while (p != s->next)
			s=s->next;
		p = s->next;
		s->next = p->next;
		(p->next)->prev = s;
		free(p);
	}
}

void dlist_prune (int x, dlist s)
{
	dlist_remove(s, (dlist_find_first (x, s)));
}


void dlist_cat (dlist s, dlist u)
{
	dlist t=u;
	u->next->prev = s->prev;
	u->prev->next = s;
	s->prev->next = u->next;
	s->prev = u->prev;
	free (t);
}

void dlist_clear (dlist s)
{
	while(s->next != s)
		dlist_remove_first(s);
}

void task_d (void)
{
	char op;
	int value, listas=0;
	dlist s[100], p=NULL;
	while (fscanf (stdin, "%c", &op) != EOF)
	{
		switch (op)
		{
			case 'C':
				s[listas] = dlist_create ();
				break;
			case 'P':
			{
				fscanf(stdin, "%d",&value);
				dlist_put_first (value, s[listas]);
				break;
			}
			case 'S':
				printf ("%d\n",dlist_size (s[listas]));
				break;
			case 'F':
			{
				dlist_write_forward (s[listas]);
				printf("\n");
				break;
			}
			case 'B':
			{
				dlist_write_backward (s[listas]);
				printf("\n");
				break;
			}
			case 'L':
			{
				fscanf(stdin, "%d",&value);
				dlist_put_last(value, s[listas]);
				break;
			}
			case 'R':
				dlist_remove_first (s[listas]);
				break;
			case 'T':
				dlist_remove_last (s[listas]);
				break;
			case 'D':
			{
				fscanf(stdin, "%d",&value);
				p=(dlist_find_first (value, s[listas]));
				break;
			}
			case 'E':
			{
				fscanf(stdin, "%d",&value);
				p=(dlist_find_last (value, s[listas]));
				break;
			}
			case 'A':
			{
				fscanf(stdin, "%d",&value);
				dlist_put_after (value, s[listas], p);
				break;
			}
			case 'G':
			{
				fscanf(stdin, "%d",&value);
				dlist_put_before (value, s[listas], p);
				break;
			}
			case 'Z':
			{
				fscanf(stdin, "%d",&listas);
				break;
			}
			case 'H':
				dlist_remove (s[listas], p);
				break;
			case 'I':
			{
				fscanf(stdin, "%d",&value);
				dlist_prune (value, s[listas]);
				break;
			}
			case 'J':
			{
				fscanf(stdin, "%d", &value);
				dlist_cat (s[listas], s[value]);
				break;
			}
			case 'M':
				dlist_clear (s[listas]);
				break;

		}
	}
}