题目描述

你工作以后，$\text{KPI}$ 就是你的全部了. 我开发了一个服务，取得了很大的知名度。数十亿的请求被推到一个大管道后同时服务从管头拉取请求。让我们来定义每个请求都有一个重要值。我的 $\text{KPI}$ 是由当前管道内请求的重要值的中间值来计算。现在给你服务记录，有时我想知道当前管道内请求的重要值得中间值。

输入格式

有大约 $100$ 组数据。

每组数据第一行有一个 $n$ ，代表服务记录数。

接下来有 $n$ 行，每一行有 $3$ 种形式“

"in x": 代表重要值为 $x$ 的请求被推进管道。

"out": 代表服务拉取了管道头部的请求。

"query: 代表我想知道当前管道内请求重要值的中间值. 那就是说，如果当前管道内有 $m$ 条请求, 我想知道，升序排序后第 $floor(m/2)+1 ~th$ 条请求的重要值.

为了让题目简单，所有的x都不同，并且如果管道内没有值，就不会有"out"和"query"操作。

输出格式

对于每组数据，先输出一行 Case #i:

然后每一次"query"，输出当前管道内重要值的中间值。

6
in 874
query
out
in 24622
in 12194
query

Case #1:
874
24622

样例分析

如上所述。

数据范围与提示

$100\%$ 的数据：$1 \le n \le 10000$，$|x| \leq 10^9$。

注意：数据需要离散化。