시소 배열

비어 있는 배열 $A$가 있다. 다음 두 종류의 질의를 총 $Q$개 처리해야 한다.

• 1 $x$: 배열의 맨 뒤에 정수 $x$를 삽입한다.
• 2: 현재 배열의 길이를 $N$이라 하자. 배열을 앞 $\left\lfloor{N\over 2}\right\rfloor$개의 원소와 뒤 $\left\lceil{N\over 2}\right\rceil$개의 원소 두 부분으로 나눈다. 두 부분 중 원소의 합이 더 작은 부분을 배열에서 삭제한다. 두 부분의 합이 같으면 앞 $\left\lfloor{N\over 2}\right\rfloor$개의 원소를 삭제한다. 그다음 삭제된 부분의 원소의 합을 출력한다. 이 형식의 질의는 배열의 길이가 $2$ 이상일 때만 주어진다.

첫 번째 줄에 질의의 수 $Q$가 주어진다. ($3\le Q\le 500\ 000$)

두 번째 줄부터 $Q$개의 줄에 질의가 다음 형식 중 하나로 주어진다.

• 1 $x$: $(1\le x\le 1\,000)$, $x$는 정수
• 2

2번 질의는 1번 이상 주어지며, 모든 2번 질의는 배열의 길이가 $2$ 이상일 때 주어짐이 보장된다.

각 2번 질의에 대한 답을 차례대로 한 줄에 하나씩 출력한다. 그다음 줄에는 모든 질의를 처리한 후 배열 $A$에 남은 원소를 차례대로 출력한다.

어떤 실수 $x$에 대해, $\lfloor{x}\rfloor$는 $n \le x$를 만족하는 가장 큰 정수 $n$이다. 마찬가지로 $\lceil{x}\rceil$은 $n \ge x$를 만족하는 가장 작은 정수 $n$이다.