Implement the following operations of a queue using stacks.

• enqueue(x) : Insert an item x to the rear of queue.
• dequeue() : Remove an item from front of queue
• peek() : Get the front item.
• empty() : Return whether the queue is empty.

Problem Note

• You must use only standard operations of a stack : which means only push to top, peek/pop from top, size, and isempty operations are valid.
• Depending on your language, stack may not be supported natively. You may simulate a stack by using a list or deque (double-ended queue), as long as you use only standard operations of a stack.
• You may assume that all operations are valid (for example, no pop or peek operations will be called on an empty queue).

Example

NewQueue queue = new NewQueue();

queue.enqueue(5);
queue.enqueue(10);  
queue.peek();  // returns 5
queue.dequeue();   // returns 5
queue.empty(); // returns false

Input Format:

First-line contains N, the total number of queries.

Each of the following N lines have a query of any of the 4 types, type 1(enqueue), type 2(dequeue), type 3(peek), type 4(empty).

Query for type 1 is of format: 1 v, where v is value

Query for type 2, 3 and 4 just mention the query type

For example, the input for the above example will be:

5
1 5
1 10
3
2
4