Problem B: Funny Queue

Problem B: Funny Queue

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 138  Solved: 27
[Submit] [Status] [Web Board] [Creator:]

Description

 zser学长现在拥有一个Queue,在这个队列中,会存在M个物品,每个物品上都有一个标号,这个标号代表着第i个小姐姐(没错,是那么多姑娘送给他的,并且标号是1到M的之间的一个数,并且不会重复),现在有q次操作:

        他需要从这队列中从任意位置取出来一个编号为d的物品(注意,不单单是从头尾取,他可以取到任意一个位置的物品),然后选择放在队列的队头,或者队尾,

现在问你操作完毕后,按存在队列中的序列顺序输出物品的标号所对应的人名

Input

第一行输入一个t,代表测试数据的组数  (t <= 10)

每组第一行输入一个m,代表原始队列中物品的个数,(1 <= m <= 100000)

下一行存在m个整数a[i],代表每个物品的编号,(1~m)

接下来一行有m个人名,str[1],str[2],,,,str[i],str[m], 代表的是标号为a[i]的这个礼物是由名字为 str[i]小姐姐送的(1 <= |str[i]| <= 10,人名由小写字母组成)

下面有q次查询: (1 <= q <= 100000)

        对于每次插入输入 s 、id  ,s∈(‘first','second'),first代表操作完之后,插入对头,second代表插入队尾,id代表要取出来的物品标号

Output

输出有单独一行,打印当前队列中所放物品的顺序的小姐姐的名字,m个人名,以空格分开,最后一个不得有空格

Sample Input Copy

1
5
1 5 3 2 4 
col siri rose men jsan 
5
first 3
second 3
second 5
first 4
second 1

Sample Output Copy

jsan men rose siri col