Queueueue

지금까지 세상에 존재하지 않았던 새로운 자료구조 Queueueue를 소개한다. 자료구조 Queueueue는 가로 Queue와 세로 Queue로 구성되어 있으며, 두 Queue가 십자가로 겹친 형태이다. 즉, 원소 1개에 대해서 중간 지점을 공유하고 있다. Queueueue의 정확한 정의는 다음과 같다.

• 가로 Queue의 원소 개수를 $n_h$, 세로 Queue의 원소 개수를 $n_v$로 정의한다.
• 가로 Queue의 $\left\lceil \frac{n_h}{2} \right\rceil$번째 원소와 세로 Queue의 $\left\lceil \frac{n_v}{2} \right\rceil$번째 원소는 서로 공유하는 같은 원소이다. 이 원소를 공유 원소라고 정의한다.
• Queueueue는 명령을 수행하고 나서 매번 공유 원소를 새로 갱신한다.
• 비어있는 Queueueue에는 공유 원소가 없다. 비어있는 Queueueue에 원소를 넣으면 그 원소가 공유 원소가 되며 $n_h = 1$, $n_v = 1$이다.
  • $n_h = 0$, $n_v = 0$인 경우를 제외하고 $n_h \times n_v = 0$인 경우는 없다. 따라서 Queueueue가 비어있지 않다면 항상 $n_h \ge 1$, $n_v \ge 1$이다.

처음에 Queueueue는 비어있으며 Queueueue는 다음 13가지 명령을 할 수 있다.

• hpush x : 가로 Queue의 맨 뒤에 정수 $x$를 넣는다. $(1 \le x \le 100\,000)$
• hpop : 가로 Queue에 정수가 있다면 맨 앞에 있는 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
• hfront : 가로 Queue에 정수가 있다면 맨 앞에 있는 정수를 출력한다. 없다면 -1을 대신 출력한다.
• hback : 가로 Queue에 정수가 있다면 맨 뒤에 있는 정수를 출력한다. 없다면 -1을 대신 출력한다.
• hsize : 가로 Queue에 들어있는 정수의 개수를 출력한다.
• vpush x : 세로 Queue의 맨 뒤에 정수 $x$를 넣는다. $(1 \le x \le 100\,000)$
• vpop : 세로 Queue에 정수가 있다면 맨 앞에 있는 정수를 빼고 출력한다. 없다면 -1을 대신 출력한다.
• vfront : 세로 Queue에 정수가 있다면 맨 앞에 있는 정수를 출력한다. 없다면 -1을 대신 출력한다.
• vback : 세로 Queue에 정수가 있다면 맨 뒤에 있는 정수를 출력한다. 없다면 -1을 대신 출력한다.
• vsize : 세로 Queue에 들어있는 정수의 개수를 출력한다.
• size : Queueueue에 들어있는 정수의 개수를 출력한다.
• empty : Queueueue가 비어있으면 1, 아니면 0을 출력한다.
• middle : Queueueue에 정수가 있다면 Queueueue의 공유 원소에 해당하는 정수를 출력한다. 없다면 -1을 대신 출력한다.

첫 번째 줄에 명령의 수 $N$이 주어진다. $(1 \le N \le 2\,000\,000)$

두 번째 줄부터 $N$개의 줄에 걸쳐 명령이 하나씩 주어진다.

출력을 요구하는 명령이 주어질 때마다, 명령의 결과를 한 줄에 하나씩 출력한다.