Problem C: Library

Problem C: Library

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 2753  Solved: 462
[Submit][Status][Web Board]

Description

In the library, LowbieH is learning the double-ended queue, which is also called deque. He thinks that it is very interesting and invites you to join him. Now there are \(n\) empty deques numbered from \(1\) to \(n\), you need to implement three types of operations that LowbieH asks you.

Type-1: \(1\ u\ w\ val\). Insert \(val\) to the deque numbered by \(u\). (\(w=0\) means that the insertion is done in the front, \(w=1\) means that the insertion is done in the rear)

Type-2: \(2\ u\ w\). Query the front or the rear element in the deque numbered by \(u\) and pop it out. (\(w=0\) means the front, \(w=1\) means the rear)

Type-3: \(3\ u\ v\ w\). Connect the deque numbered by \(v\) to the rear of the deque numbered by \(u(u \neq v)\). (\(w=0\) means a direct connection, \(w=1\) means a reversed connection, that is to say you need to first reverse the deque numbered by \(v\) and then connect them) The deque numbered by \(v\) will be cleared after the connection.

Input

Multiple test cases. Please process to the end of file.

For each test case, the first line contains two integers \(n(1\leq n \leq 10^5)\) and \(q(1\leq q \leq 10^5)\), denoting the number of the deques and the number of the operations. The following \(q\) lines will be the three types of operations that have been explained.

\(1\leq u,v \leq n\), \(0\leq w \leq 1\), \(1\leq val \leq 10^5\).

It is guaranteed that the total number of operations will not exceed \(3*10^5\).

Output

Print one line an integer denoting the answer for each type-2 operation. If the deque is empty, then print \(-1\) instead.

Sample Input

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
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

Sample Output

23
-1
2333
233
23333
23
-1
2333
233
23333

HINT


The data is randomly generated, so you can assume that the expected length of each deque is very small.



You are encouraged to self-study the implementation of deque.

[Submit][Status]