Implement Queue using Stacks

Problem statement

A device firmware offers stack storage but needs a first-in-first-out queue for incoming jobs. Jobs must leave in their arrival order even when arrivals and removals are interleaved. Your task Implement push x, pop, peek and empty using only two stacks. push enqueues x; pop removes and returns the front; peek returns it without removal; empty reports whether the queue has no entries. Important details Use only stack push, pop, top and emptiness operations internally. pop and peek are called only on nonempty queues. Amortized O(1) time per operation is expected. Repeated values remain separate jobs. Worked example After push 4, push 7, peek, pop, peek, the outputs are 4, 4 and 7. Reading the front does not remove it, but pop does.

Input format

First line: q. Next q lines contain operations.

Output format

Print answers for pop and peek, and true/false for empty, one per line. Print EMPTY if no query produces output.

Constraints

1 <= q <= 10000; -1000000000 <= pushed values <= 1000000000.

Sample input

5
push 4
push 7
peek
pop
peek

Sample output

4
4
7