题目描述

现有一个初始时为空的队列，对其进行\(K\)次操作。操作共有3类：
push \(\phantom{x} x\)：将整数\(x\)添加到队列的末尾；
pop：将队列头部的元素弹出（如果有的话）；
median：输出队列中所有元素的中位数。如果此时队列中元素个数\(n\)为偶数，则规定中位数为第\(n/2\)小的数。
输入\(K\)次操作并依次执行，按照“输出格式”部分的要求输出每次操作的结果。

输入格式

第一行是一个正整数\(K\)，表示操作次数；
之后\(K\)行，每行先是1个字符串，表示操作类型，该字符串只可能是push，pop，median中的某一个；如果是push操作，则之后还有一个整数\(x\)，表示添加到队列末尾的数；否则后面没有其他内容。

输出格式

依次执行每个操作并按照如下要求输出结果，每次输出一行：
对于push操作，输出Size = x，其中x用操作后队列中的元素个数代替，=前后各有一个空格；
对于pop操作，如果操作前队列为空，则输出Empty!，否则输出Popped = x，其中x用此次弹出队列的值代替；
对于median操作，如果此时队列为空则输出Empty!，否则输出Median = x，其中x用此时队列内的中位数代替。

样例

输入

12
push 1
push 2
push 4
median
pop
pop
push -3
median
pop
pop
pop
median

输出

Size = 1
Size = 2
Size = 3
Median = 2
Popped = 1
Popped = 2
Size = 2
Median = -3
Popped = 4
Popped = -3
Empty!
Empty!

数据范围及约定

50%的数据：\(K \le 1000\)；
100%的数据：\(K \le 10^5\), 每次push操作插入的数均在闭区间\([-10^5, 10^5]\)内。
时间限制1s，空间限制64MB。