1191: 度度熊学队列

度度熊正在学习双端队列，他对其翻转和合并产生了很大的兴趣。初始时有N个空的双端队列（编号为1到N），你要支持度度熊的Q次不同种类的操作（共3种），分别为：

① 1 u w val：在编号为u的队列里加入一个值为val的元素，w等于0表示加在最前面，w等于1表示加在最后面。

那么操作完成后，2号队列里的元素为：2 5

例如：2 1 0，并假设1号队列里的元素为：7 1 3 4。

•第一个2表示这一行输入的是操作类型②的相关信息；

•第二个1表示对编号为1的队列进行操作；

•第三个0表示需要输出并删除1号队列最前面的元素；

那么操作完成后，会输出7并删除它，1号队列的元素为：1 3 4。

③ 3 u v w：把编号为v的队列接在编号为u的队列的最后面，w等于0表示将队列v按原顺序接在队列u之后；w等于1表示将队列v翻转顺序（逆序）后接在队列u之后。完成后队列v将变成空的。

例如：3 1 2 1，并假设1号队列的元素为：1 3 4；2号队列的元素为：2 5。

•第一个3表示这一行输入的是操作类型③的相关信息；

•第二个1和第三个2表示把2号队列接在1号队列后面；

•第四个1表示需要把2号队列的元素翻转顺序；

那么操作完成后，1号队列的元素为：1 3 4 5 2；而2号队列变为空的（没有任何元素）。

第一行读入两个数N和Q。接下来有Q行，每行3~4个数，意义如题中所述。

N≤150,000,Q≤400,000,1≤u,v≤N,0≤w≤1,1≤val≤100,000。

每执行一次操作类型②，都会输出一个数（单独一行）。

注意，如果某次操作②涉及的队列是空的话，就输出−1（且不执行删除操作）。

2 10
1 1 1 23
1 1 0 233
2 1 1
1 2 1 2333
1 2 1 23333
3 1 2 1
2 2 0
2 1 1
2 1 0
2 1 1

23
-1
2333
233
23333