Stack Overflow

Stack is a basic data structure. Where 3 operations can be done:

• Push: You can push object to the stack
• Pop: You can pop the object to the stack
• Top: You can check the value of the top object.

For further details you can get idea here (if you really don’t know): https://en.wikibooks.org/wiki/Data_Structures/Stacks_and_Queues

Now we have a problem here, there are $N$ stacks in front of you. they are numbered from 1 to $N$. Each of them are initially empty. Now you will have $Q$ operations. Each operation can be one the below 4 types:

• push i x, Push a value of $x$ to stack numbered $i$
• pop i, Pop value from the stack numbered $i$, if stack is empty discard the operation
• put i j, Put the $j$-th stack on top of the $i$-th stack. So there will be no element left on the $j$-th stack.
• top i, Print the value of the top element of $i$-th stack. If stack is empty print “Empty!”

Input

Input starts with an integer $T$ ($1 ≤ T ≤ 5$), denoting the number of test cases.

The next line contains two integers $N$ ($1 ≤ N ≤ 10^4$), $Q$ ($1 ≤ Q ≤ 5 \times 10^4$). The next $Q$ lines will contain an operation like above mentioned.

Other constraints:

• $1 ≤ i, j ≤ N$
• $1 ≤ x ≤ 10^5$

Output

For each test case, print the case number in a single line. Then for each 4th type operation you should print the value or “Empty!” if the stack is empty.

Sample

1
3 18
push 1 1
push 2 2
push 3 3
push 3 4
top 1
top 2
top 3
put 1 3
pop 2
top 1
top 2
top 3
pop 1
top 1
pop 1
top 1
pop 1
top 1

Case 1:
1
2
4
4
Empty!
Empty!
3
1
Empty!