← 返回题目列表

AtCoder · abc458_d

G. 黑板中位数

中文机器翻译题面 查看原题

分数: 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