AT_abc458_d [ABC458D] Chalkboard Median

黑板上最初写着一个整数 $ X $ 。 接下来会有 $ Q $ 个查询，请你依次处理。第 $ i $ 个查询（$1\le i\le Q$）内容如下： > 给出两个整数 $ A_i,B_i $，将这两个数写到黑板上。 > > 然后，输出黑板上目前所有 $ 2i+1 $ 个整数的中位数。

输入从标准输入给出，格式如下： > $ X $ > $ Q $ > $ A_1 $ $ B_1 $ > $ A_2 $ $ B_2 $ > ... > $ A_Q $ $ B_Q $

输出 $ Q $ 行。 第 $ i $ 行输出第 $ i $ 个查询的答案，也就是当前黑板上所有数的中位数。

### 样例解释 1 第 $ 1 $ 个查询后，黑板上的数是 $ 5,2,3 $，中位数是 $ 3 $。 第 $ 2 $ 个查询后，黑板上的数是 $ 5,2,3,1,2 $，中位数是 $ 2 $。 第 $ 3 $ 个查询后，黑板上的数是 $ 5,2,3,1,2,8,9 $，中位数是 $ 3 $。 ### 约束条件 - $ 1\le X\le 10^9 $ - $ 1\le Q\le 2\times 10^5 $ - $ 1\le A_i,B_i\le 10^9 $ - 输入的所有数均为整数 翻译由 ChatGPT 4.1 完成。