分数: 400 点
问题陈述
有一个整数 X 写在黑板上。
你被给予 Q 查询按顺序处理。的 i第一个查询 (1 \le i \le Q) 如下。
两个整数 给出了 A_i 和 B_i 。写入两个新整数 黑板上的 A_i 和 B_i 。
然后,输出 2i+1 整数写在黑板上。
约束
- 1 \le X \le 10^9
- 1 \le Q \le 2 \times 10^5
- 1 \le A_i, B_i \le 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
X Q A_1 B_1 A_2 B_2 \vdots A_Q B_Q
输出
输出 Q 行。
的 i- 第行应包含以下问题的答案 i-第一个查询。
示例输入 1
5 3 2 3 1 2 8 9
示例输出 1
3 2 3
在第一个查询中,黑板上写的整数变成 5, 2, 3,它们的中位数是 3.
在第二个查询中,黑板上写的整数变成 5, 2, 3, 1, 2,它们的中位数是 2.
在第三个查询中,黑板上写的整数变成 5, 2, 3, 1, 2, 8, 9,它们的中位数是 3.
示例输入 2
1 4 2 3 4 5 6 7 8 9
示例输出 2
2 3 4 5
示例输入 3
278117031 7 167642909 517897721 148434323 567739597 319926999 481642530 659199879 252516557 49913403 798318034 89701408 892537201 199166668 742285869
示例输出 3
278117031 278117031 319926999 319926999 319926999 319926999 319926999