AT_abc458_d [ABC458D] Chalkboard Median

黒板に整数 $ X $ が $ 1 $ つ書かれています。 $ Q $ 個のクエリが与えられるので、順に処理してください。 $ i $ 個目 $ (1\le i\le Q) $ のクエリは以下の通りです。 > $ 2 $ つの整数 $ A_i,B_i $ が与えられる。黒板に新たに $ 2 $ つの整数 $ A_i,B_i $ を書く。 > > その後、黒板に書かれた $ 2i+1 $ 個の整数の中央値を出力する。

入力は以下の形式で標準入力から与えられる。 > $ X $ $ Q $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_Q $ $ B_Q $

$ Q $ 行出力せよ。 $ i $ 行目には、 $ i $ 番目のクエリに対する答えを出力せよ。

### Sample Explanation 1 $ 1 $ つ目のクエリでは黒板に書かれた整数は $ 5,2,3 $ となり、これらの整数の中央値は $ 3 $ です。 $ 2 $ つ目のクエリでは黒板に書かれた整数は $ 5,2,3,1,2 $ となり、これらの整数の中央値は $ 2 $ です。 $ 3 $ つ目のクエリでは黒板に書かれた整数は $ 5,2,3,1,2,8,9 $ となり、これらの整数の中央値は $ 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 $ - 入力される値は全て整数