Implement Queue Using Two Stacks

You are given the task to implement a queue using two stacks. A queue supports two operations:

• enqueue x: Insert the integer x at the end of the queue.
• dequeue: Remove the element from the front of the queue and print it. If the queue is empty, print -1.

Your implementation must simulate the behavior of a queue by using two stacks. One stack is used for enqueuing elements and the other for dequeuing.

Internally, for a dequeue operation, if the second stack is empty, transfer all elements from the first stack to the second stack, then pop the top element from the second stack.

The mathematical relation behind the number of operations is as follows:

\( O(1) \ amortized \ time \ per \ operation \)

Note: Design your solution to read from stdin and print to stdout.

inputFormat

The first line of input contains an integer Q, representing the number of operations. The next Q lines each contain an operation in one of the following two formats:

• enqueue x: where x is an integer to be added to the queue.
• dequeue: to remove the element at the front of the queue and output it.

outputFormat

For every dequeue operation, output the returned value on a new line. If the queue is empty during a dequeue operation, output -1.

## sample

10
enqueue 1
enqueue 2
dequeue
enqueue 3
enqueue 4
dequeue
dequeue
enqueue 5
dequeue
dequeue

1
2
3
4
5

</p>