AT_abc458_d [ABC458D] Chalkboard Median

There is one integer $ X $ written on a blackboard. You are given $ Q $ queries to process in order. The $ i $ -th query $ (1 \le i \le Q) $ is as follows. > Two integers $ A_i $ and $ B_i $ are given. Write two new integers $ A_i $ and $ B_i $ on the blackboard. > > Then, output the median of the $ 2i+1 $ integers written on the blackboard.

The input is given from Standard Input in the following format: > $ X $ $ Q $ > > $ A_1 $ $ B_1 $ > > $ A_2 $ $ B_2 $ > > $ \vdots $ > > $ A_Q $ $ B_Q $

Output $ Q $ lines. The $ i $ -th line should contain the answer to the $ i $ -th query.

### Sample Explanation 1 In the first query, the integers written on the blackboard become $ 5, 2, 3 $ , and their median is $ 3 $ . In the second query, the integers written on the blackboard become $ 5, 2, 3, 1, 2 $ , and their median is $ 2 $ . In the third query, the integers written on the blackboard become $ 5, 2, 3, 1, 2, 8, 9 $ , and their median is $ 3 $ . ### Constraints - $ 1 \le X \le 10^9 $ - $ 1 \le Q \le 2 \times 10^5 $ - $ 1 \le A_i, B_i \le 10^9 $ - All input values are integers.