PRJAN15F - Stack Overflow

no tags 

Stack is a basic data structure. Where 3 operation can be done-

  1. Push: You can push object to the stack,
  2. Pop: You can pop the object to the stack,
  3. Top: You can check the value of the top object.

For further details you can get idea here (if you really don’t know): 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:

  1. push i x, Push a value of x to stack numbered i,
  2. pop i, Pop value from the stack numbered i, if stack is empty discard the operation,
  3. 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,
  4. top i, Print the value of the top element of ith stack. If stack is empty print “Empty!”.

Check the Sample IO for further understanding...

Input

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

The first line of a case is a blank line. The next line contains two integers N (1 ≤ N ≤ 104), Q(1 ≤ Q ≤ 5*104).

The next Q lines will contain an operation as mentioned above. (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.

Example

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

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

Judge data is huge so use faster IO like scanf/printf.

Problem-setter: Ahmad Faiyaz


hide comments
nimphy: 2018-05-23 10:15:50

Notice the Details!

nadstratosfer: 2017-11-09 03:23:44

When solving with Python, note that input contains blanklines other than the ones mentioned in statement. Also, optimize or TLE.

Last edit: 2018-01-05 06:25:57
mahmud2690: 2017-07-16 15:01:57

Skip if i = j in "put" operation.

topke: 2016-02-12 10:29:07

@numerix Thats wierd i got WA by not checking put operation validity. Guess that should be stated in problem statement or removed from test cases

Rishav Goyal: 2015-08-08 19:57:43

that "i=j" helped alot to avoid WA. thanks shiva

n3gativ3: 2015-05-31 16:03:09

just remember to print Case No. :P

aky: 2015-03-04 10:03:31

Getting sigsegv... Is there any tricky test case?

(Tjandra Satria Gunawan)(曾毅昆): 2015-02-27 00:07:04

Yo Dawg, getting Stack Overflow on Stack Overflow problem, so I can debug my buggy Stack Overflow code for this Stack Overflow problem :p :p

numerix: 2015-02-13 22:56:01

@Takanori MAEHARA: Thanks.
I got accepted with the assumption that "put i i" doubles the stack. Ignoring that command results also in AC.
But anyway: The problem description is not clear for that case and it shouldn't be necessary to consult other sources than the problem description to get a complete and unambiguous description.
And (referring to the second question you quoted): Why shouldn't it be possible to put a stack onto itself?

Takanori MAEHARA: 2015-02-13 10:32:54

I found the following clarifications in the contest site.

Q. Can i, j be equal in 'put i j'?
A. Yes, It can be.

Q. If the command is 'put i i', what to do? A stack can't be put onto itself. Should I ignore the command?
A. Yes, you can ignore that.


Added by:Shafaet
Date:2015-01-31
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 JS-MONKEY
Resource:Progkriya Contest January 2015