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

Limits: 1s, 512 MB

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 ≤ 104
  • 1 ≤ Q ≤ 5*104
  • 1 ≤ i, j ≤ N
  • 1 ≤ x ≤ 105

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

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

Author
  • faiyaz26's Avatar

    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.
Discussion
Submit

Login to submit