训练　度度熊学队列

题目描述（HDU6375）：度度熊正在学习双端队列，它对翻转和合并产生了很大的兴趣。初始时有n个空的双端队列（编号为1～n），度度熊的m次操作有3种类型。

操作①1 u w val：在双端队列u中添加一个元素val（w=0表示添加在最前面，w=1表示添加在最后面）。

操作②2 u w：查询双端队列u中的某个元素并删除它（w=0表示查询并删除最前面的元素，w=1表示查询并删除最后面的元素）。

操作③3 u v w ：将双端队列v拼接在双端队列u的后面。w=0表示顺序拼接（将双端队列v的开头和双端队列u的结尾连在一起，将双端队列v的结尾作为新双端队列的结尾），w=1表示逆序拼接（首先将双端队列v翻转，再将其顺序拼接在双端队列u的后面）。在该操作完成后，原双端队列v被清空。

输入：输入多组数据。每组数据的第1行都为两个整数n和m。接下来有m行，每行都有3或4个数，含义如上。n≤1.5×105，m≤4×105，1≤u，v≤n，0≤w≤1，1≤val≤105；所有数据里m的和都不超过5×105。

输出：对于每组数据的每个操作②，都输出一行表示答案。若操作②的双端队列是空的，则输出-1且不执行删除操作。

提示：由于读入的数据量过大，所以建议进行读入优化。一个简单的读入优化代码模板如下。

1.算法设计

本题描述的是双端队列，可以用deque解决。

（1）定义一个双端队列类型的数组d［］。

（2）判断并分别执行3种操作。对于操作②，需要输出结果。

（3）对于操作③，由于双端队列不支持翻转，因此用反向迭代器实现翻转。

对本题也可以用list来处理。list是双向链表，双向链表支持翻转和拼接。首先定义一个双向链表类型的数组ls［］，对于操作③，双向链表支持翻转，其拼接函数splice（）可以将另一个链表v拼接到当前链表的pos位置之前，并自动清空原双向链表v，而且时间复杂度为常数。

2.算法实现