以下题面由 AI 翻译。

丹尼尔刚刚解决了问题 运行中位数。

问题的第一行说：“你将得到一组按非递减顺序排列的整数”。该问题要求每次查询时报告并删除列表中的中位数。

解决完这个问题后，丹尼尔开始思考如何处理输入不在非递减排列的情况下（如题目所述）。

你能帮助他吗？

你的任务是将一组正整数作为输入。每当-1被给出时，你必须输出当前列表的中位数，并将其删除。如果元素个数为偶数，则取较小的那个元素作为中位数。

输入

输入包含多个测试用例。

第一个整数t表示测试用例的数量。

每个测试用例的每一行都包含一个整数n（<=10^9）。如果n为正，则将其添加到列表中。n=-1表示一个中位数查询（如果列表为空，就不会有中位数查询）。测试用例在n=0时结束。

每个测试用例最多可以有10^5个整数被添加到列表中，并且最多有10^5次中位数查询。</h3>

输出

对于每次描述中的中位数查询，按新行输出中位数。

示例

输入：
1
9
10
2
5
1
18
-1
-1
4
3
-1
8
7
-1
0
输出：
5
9
3
7