# Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

## 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 stack 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!”

Check the Sample IO for further understanding

#### Input

Input starts with an integer T, denoting the number of test cases.

The next line contains two integers N, Q. The next Q lines will contain an operation like above mentioned.

Constraints:

- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 10
^{4} - 1 ≤ Q ≤ 5*10
^{4} - 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.

#### Samples

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

#### faiyaz26

Faiyaz refers to himself as a lazy software engineer. He likes coffee, sleep and solving problems. He qualified to ACM-ICPC World Finals 2016 from North South University and secured top ranks in numerous national contests. →

Login to submit