AT_ajo2024_final_b Meetings

AtCoder さんには、 $ N $ 件の会議の予定が入っています。 会議は**優先度の高い順に** $ 1 $ から $ N $ までの番号が付けられており、 会議 $ i $ は時刻 $ L_i $ から時刻 $ R_i $ までの時間帯に完全に含まれる、連続する好きな $ 1 $ 単位時間を選んで行うことができます。 ただし、同時に複数の会議に出席することはできません。 AtCoder さんはできるだけ長い睡眠時間を確保したいので、出席する最初の会議が始まってから、出席する最後の会議が終わるまでの時間を最小化したいです。 また、最小化する方法が複数ある場合、最後の会議が終わる時刻をできるだけ早くしたいです。 $ k = 1, 2, \dots, N $ について、次の問いに答えてください。 - 会議 $ 1 $ から $ k $ までに出席するとき、 $ k $ 件すべての会議に出席できるかどうかを判定し、もし可能であれば最適な戦略をとった場合における、最初の会議が始まる時刻と最後の会議が終わる時刻をそれぞれ求めよ。

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

$ N $ 行にわたって出力してください。 $ k $ 行目 $ (1 \leq k \leq N) $ には、会議 $ 1 $ から会議 $ k $ まで出席するケースについて、以下の形式で出力してください。 - $ k $ 件すべての会議に出席できる場合: 最初の会議の開始時刻と、最後の会議の終了時刻を空白区切りで出力 - $ k $ 件すべての会議に出席できない場合: `Impossible` を出力

### Sample Explanation 1 たとえば、会議 $ 1, 2, 3 $ すべてに出席する場合、以下のような戦略が最適になります。 - 会議 $ 2 $ の開始時刻を $ 3 $ 、終了時刻を $ 4 $ に設定する。 - 会議 $ 3 $ の開始時刻を $ 4 $ 、終了時刻を $ 5 $ に設定する。 - 会議 $ 1 $ の開始時刻を $ 5 $ 、終了時刻を $ 6 $ に設定する。 ### Constraints - $ 1 \leq N \leq 180\,000 $ - $ 0 \leq L_i < R_i \leq 180\,000 $ - 入力はすべて整数