Description

Implement a first-in-first-out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue.

Operations:

• push(x) — Push element x to the back of queue
• pop() — Removes the element from the front
• peek() — Get the front element
• empty() — Return whether the queue is empty

Input format:

Each line contains a queue operation.

Example

Input:
push 1
push 2
peek
pop
empty

Output:
1
1
false

Note:

Print outputs only for peek, pop, and empty.