AT_arc175_c [ARC175C] Jumping Through Intervals

[problemUrl]: https://atcoder.jp/contests/arc175/tasks/arc175_c $ N $ 個の整数組 $ (L_1,\ R_1),\ (L_2,\ R_2),\ \dots,\ (L_N,\ R_N) $ が与えられます．ここで，全ての $ 1\leq\ i\leq\ N $ に対して $ L_i\ \leq\ R_i $ が満たされています． $ N $ 個の整数からなる列 $ A\ =\ (A_1,\ A_2,\ \ldots,\ A_N) $ であって，以下の条件を満たすものを**良い整数列**と呼びます． - 全ての $ 1\leq\ i\leq\ N $ に対して，$ L_i\ \leq\ A_i\ \leq\ R_i $ である． $ \displaystyle\ \sum_{i\ =\ 1}^{N-1}\ |A_{i+1}\ -\ A_{i}| $ を最小にするような**良い整数列** $ A $ のうち，辞書順で最小のものを求めてください． 数列の辞書順とは数列 $ S\ =\ (S_1,S_2,\ldots,S_{|S|}) $ が数列 $ T\ =\ (T_1,T_2,\ldots,T_{|T|}) $ より**辞書順で小さい**とは，下記の 1. と 2. のどちらかが成り立つことを言います． ここで，$ |S|,\ |T| $ はそれぞれ $ S,\ T $ の長さを表します． 1. $ |S|\ \lt\ |T| $ かつ $ (S_1,S_2,\ldots,S_{|S|})\ =\ (T_1,T_2,\ldots,T_{|S|}) $． 2. ある整数 $ 1\ \leq\ i\ \leq\ \min\lbrace\ |S|,\ |T|\ \rbrace $ が存在して，下記の $ 2 $ つがともに成り立つ． - $ (S_1,S_2,\ldots,S_{i-1})\ =\ (T_1,T_2,\ldots,T_{i-1}) $． - $ S_i $ が $ T_i $ より（数として）小さい．

入力は以下の形式で標準入力から与えられる． > $ N $ $ L_1 $ $ R_1 $ $ L_2 $ $ R_2 $ $ \vdots $ $ L_N $ $ R_N $

答えを以下の形式で $ 1 $ 行に出力せよ． > $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $

### 制約 - 入力される数値は全て整数 - $ 2\ \leq\ N\ \leq\ 5\ \times\ 10^5 $ - $ 0\ \leq\ L_i\ \leq\ R_i\ \leq\ 10^9 $ ### Sample Explanation 1 $ (A_1,\ A_2,\ A_3,\ A_4)\ =\ (8,\ 8,\ 4,\ 5) $ は良い整数列です．このとき $ \sum_{i\ =\ 1}^{N-1}\ |A_{i+1}\ -\ A_{i}|\ =\ |8\ -\ 8|\ +\ |4\ -\ 8|\ +\ |5\ -\ 4|\ =\ 5 $ となり，これが $ \sum_{i\ =\ 1}^{N-1}\ |A_{i+1}\ -\ A_{i}| $ の最小の値です． ### Sample Explanation 2 $ \sum_{i\ =\ 1}^{N-1}\ |A_{i+1}\ -\ A_{i}| $ が最小となる良い数列 $ A $ が複数あるときは，そのうち辞書順で最小のものを出力することに注意してください．