珅泽教育的小婷老师正在组织一项队列实践，她请小泽按下面的规则完成记录。

请维护一个整数序列，处理以下操作：push_front x 把 x 放最前；push_back x 放最后；push_middle x 把 x 插入下标 $(k+1)/2$，其中 k 是插入前长度、下标从0开始；get i 输出下标 i 的元素。

操作数很大，需要所有操作接近常数时间。

输入格式

第一行输入操作数 N。

接下来 N 行每行一个操作。

输出格式

每次 get 输出一行。

9
push_front 100
push_back 101
get 0
push_middle 102
push_front 103
get 0
push_back 104
push_middle 105
get 0

100
103
103

10
push_front 200
push_back 201
get 1
push_middle 202
push_front 203
get 1
push_back 204
push_middle 205
get 1
push_front 206

201
200
200

12
push_front 300
push_back 301
get 0
push_middle 302
push_front 303
get 2
push_back 304
push_middle 305
get 2
push_front 306
push_back 307
get 2

300
302
302
300

数据范围与约定

• $1 \le N \le 10^6$
• $0 \le i<k$
• $|x| \le 10^9$