很多人，都有着奋力挣扎的当下。
车水马龙，人来人往。有很多人渐渐进入你的生活，也有很多人陆续淡出你的视野。
为了方便，用整数来标识每个人。你的思绪可以类比成一根绳索，而每个人就像穿上去的珍珠。每一天，可能有一颗“珍珠”从最左侧或最右侧加入了这条绳索；也有可能会有一颗“珍珠”被你从最左侧或最右侧取下；甚至也有可能发生了些变故，致使你的整个“项链”左右翻转了过来。
每当一个人离开的时候，你总会缅怀一下他，输出标识他的数字来结束这一段关系。
最开始你的思绪中空无一人。在接下来的这 $n$ 天中，你又会先后缅怀哪些人呢？

第一行一个整数 $n,id$，表示需要处理的天数和测试点编号，测试点编号是为了方便获取部分分，但是 icpc 赛制并没有部分分，所以它没用，但是我懒得删了（x）。
接下来 $n$ 行，每行的格式是以下 $5$ 种之一：
$0\ x$：从最左侧加入标识为 $x$ 的人（$x$ 是一个整数）
$1$：移除并缅怀最左侧的人（要求输出其标识）。若不存在，输出 $0$
$2\ x$：从最右侧加入标识为 $x$ 的人（$x$ 是一个整数）
$3$：移除并缅怀最右侧的人（要求输出其标识）。若不存在，输出 $0$
$4$：使思绪颠倒（整条“项链”左右翻转）
$0\le n_i\le{10}^5,0\le x\le{10}^9$

每当操作为 $1$ 或 $3$ 时，输出一行一个整数，表示被移除的人的标识数（若不存在则输出 $0$）。