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

Input	Output
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!