Deque

整数を保持する可変長配列$A = \{a_0, a_1, ...\}$に対して、以下の操作を行ってください。

• push($d$, $x$): $d$が0の場合、$A$の先頭に整数$x$を挿入する。$d$が1の場合、末尾に$x$を挿入する。
• randomAccess($p$): $A$の要素$a_p$の値を出力する。
• pop($d$): $d$が0の場合、$A$の先頭の要素を削除する。$d$が1の場合、末尾の要素を削除する。

$A$は0-オリジンでインデックスが付けられ、初期状態では空とします。

Input

入力は以下の形式で与えられます。

$q$
$query_1$
$query_2$
:
$query_q$

各クエリ$query_i$は

0 $d$ $x$

または

1 $p$

または

2 $d$

の形式で与えられます。最初の数字0, 1, 2 は操作の種類を示し、それぞれpush、randomAccess、popを表します。

空の配列に対して、randomAccess、pop操作が行われることはありません。

Output

各randomAccess操作ごとに、$a_p$の値を１行に出力してください。

Constraints

• $1 \leq q \leq 400,000$
• $0 \leq p < $ 可変長配列$A$の要素数
• $-1,000,000,000 \leq x \leq 1,000,000,000$

Sample Input 1

11
0 0 1
0 0 2
0 1 3
1 0
1 1
1 2
2 0
2 1
0 0 4
1 0
1 1

Sample Output 1

2
1
3
4
1

---