덱

처음에 비어 있는 정수 수열 $a=()$이 있다. $Q$개의 쿼리를 처리한다.

• 0 $x$: 정수 $x$을 수열 $a$의 맨 앞에 추가한다.
• 1 $x$: 정수 $x$을 수열 $a$의 맨 뒤에 추가한다.
• 2: 수열 $a$의 맨 앞에 있는 정수를 제거한다.
• 3: 수열 $a$의 맨 뒤에 있는 정수를 제거한다.
• 4 $i$: 이때 $a = (a_0, \ldots, a_{n-1})$이라 하자. $a_i$을 출력한다.

제약 조건

• $1 \leq Q \leq 500000$
• $0 \leq x \leq 1000000000$
• 쿼리 $2$, 쿼리 $3$, 또는 쿼리 $4$가 주어질 때 수열 $a$은 비어 있지 않다.
• 쿼리 $4$가 주어질 때 $0\leq i < |a|$가 성립한다.

$Q$
$\textrm{Query}_0$
$\textrm{Query}_1$
:
$\textrm{Query}_{Q - 1}$

4 $i$: 이때 $a = (a_0, \ldots, a_{n-1})$이라 하자. $a_i$을 출력한다.