#include<stdio.h>
#include<string.h>
char s1[10]="pushLeft",s2[10]="pushRight",s3[10]="popLeft",s4[10]="popRight";
int main(void)
{
	int n,m,i,b,sum,left[101],right[101],l,r,l1,r1;
	char a[11];
	scanf("%d%d",&n,&m);
	sum=0;l=0;r=0;l1=0;r1=0;
	while(m--)
	{
		scanf("%s",&a);
		if(strstr(a,s1))
		{
			scanf("%d",&b);
			if(sum<n){left[l]=b;l++;sum++;printf("Pushed in left: %d\n",b);}
			else printf("The queue is full\n");
		}
		else if(strstr(a,s2))
		{
			scanf("%d",&b);
			if(sum<n){right[r]=b;r++;sum++;
			printf("Pushed in right: %d\n",b);}
			else printf("The queue is full\n");
		}
		else if(strstr(a,s3))
		{
			if(sum==0)printf("The queue is empty\n");
			else
			{
				if(l>l1)
				{
					printf("Popped from left: %d\n",left[l-1]);
					l--;sum--;
				}
				else if(r>r1)
				{
					printf("Popped from left: %d\n",right[r1]);
					sum--;r1++;
				}
			}

		}
		else if(strstr(a,s4))
		{
			if(sum==0)printf("The queue is empty\n");
			else
			{
				if(r>r1)
				{
					printf("Popped from right: %d\n",right[r-1]);
					r--;sum--;
				}
				else if(l>l1)
				{
					printf("Popped from right: %d\n",left[l1]);
					sum--;l1++;
				}
			}
		}
	}
}