题目描述

黑板上最初写着一个整数 $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

5
3
2 3
1 2
8 9

输出示例 1

3
2
3

示例 1 说明

第 $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

约束条件

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