#include<stdio.h>
#include<string.h>
int main()
{
int n,front,rear,temp,m,stack[1000],top;
char a[10],b[10];
scanf("%d",&n);
while(n--)
{
top=0;
front=0;
rear=0;
scanf("%d %s",&m,b);
while(m--)
{
scanf("%s",a);
if(strcmp(b,"FIFO")==0)
{
if(strcmp(a,"IN")==0)
{
scanf("%d",&temp);
stack[rear++]=temp;
}
else
{
if(rear-front<=0)
printf("None\n");
else
printf("%d\n",stack[front++]);
}
}
else
{
if(strcmp(a,"IN")==0)
{
scanf("%d",&temp);
stack[top++]=temp;
}
else
{
if(top<0)
printf("None\n");
else
printf("%d\n",stack[--top]);
}
}
}
}
return 0;
}