题目描述

黑板上初始写有一个整数 $X$。

给定 $Q$ 个查询,按顺序处理。第 $i$ 个查询($1 \le i \le Q$)格式如下:

给定两个整数 $A_i, B_i$。将 $A_i$ 和 $B_i$ 新写到黑板上。

之后,输出黑板上 $2i+1$ 个整数的中位数(从小到大排序后的第 $i+1$ 个数)。

输入格式

X
Q
A_1 B_1
A_2 B_2
...
A_Q B_Q

输出格式

输出 $Q$ 行。第 $i$ 行包含第 $i$ 个查询的答案。

数据范围

• $1 \le X \le 10^9$
• $1 \le Q \le 2 \times 10^5$
• $1 \le A_i, B_i \le 10^9$
• 所有输入值均为整数

样例 1 输入

5
3
2 3
1 2
8 9

样例 1 输出

3
2
3

• 第 1 次查询后黑板为 5, 2, 3,中位数为 $3$。
• 第 2 次查询后黑板为 5, 2, 3, 1, 2,中位数为 $2$。
• 第 3 次查询后黑板为 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