push 와 pop 연산을 제공하는 큐를 구현해보자. 명세는 다음과 같다.

1. push x : 큐에 정수 ~x (1 ≤ x ≤ 100 000)~를 추가한다.
2. pop : 큐에서 원소를 하나 제거하고 출력한다. 만약 큐가 비어있다면 -1을 출력한다.

입력

첫째 줄에 연산의 개수 N (1 ≤ N ≤ 100 000) 이 주어진다.

둘째 줄 부터 N 개의 줄에 연산이 주어진다.

출력

N 개의 줄에 연산의 결과를 출력한다.

예제 입력

10
push 4
pop
pop
push 1
pop
push 3
push 2
pop
pop
pop

예제 출력

4
-1
1
3
2
-1