問題文

AtCoder さんには、N 件の会議の予定が入っています。

会議は優先度の高い順に 1 から N までの番号が付けられており、 会議 i は時刻 L_i から時刻 R_i までの時間帯に完全に含まれる、連続する好きな 1 単位時間を選んで行うことができます。 ただし、同時に複数の会議に出席することはできません。

AtCoder さんはできるだけ長い睡眠時間を確保したいので、出席する最初の会議が始まってから、出席する最後の会議が終わるまでの時間を最小化したいです。 また、最小化する方法が複数ある場合、最後の会議が終わる時刻をできるだけ早くしたいです。

k = 1, 2, \dots, N について、次の問いに答えてください。

• 会議 1 から k までに出席するとき、k 件すべての会議に出席できるかどうかを判定し、もし可能であれば最適な戦略をとった場合における、最初の会議が始まる時刻と最後の会議が終わる時刻をそれぞれ求めよ。

制約

• 1 \leq N \leq 180\,000
• 0 \leq L_i < R_i \leq 180\,000
• 入力はすべて整数

入力例 1

3
5 7
2 4
1 6

出力例 1

5 6
3 6
3 6

たとえば、会議 1, 2, 3 すべてに出席する場合、以下のような戦略が最適になります。

• 会議 2 の開始時刻を 3、終了時刻を 4 に設定する。
• 会議 3 の開始時刻を 4、終了時刻を 5 に設定する。
• 会議 1 の開始時刻を 5、終了時刻を 6 に設定する。

入力例 2

2
0 1
179999 180000

出力例 2

0 1
0 180000

入力例 3

7
10 15
10 15
10 15
10 15
10 15
10 15
10 15

出力例 3

10 11
10 12
10 13
10 14
10 15
Impossible
Impossible

入力例 4

8
15 18
17 20
15 20
15 20
10 13
11 15
11 13
10 13

出力例 4

15 16
16 18
15 18
15 19
12 19
12 19
11 19
10 19

入力例 5

20
6 13
5 20
9 15
23 24
7 10
10 11
6 13
6 17
7 21
12 22
9 17
7 19
7 18
6 22
20 24
11 13
16 24
14 18
12 25
19 21

出力例 5

6 7
5 7
7 10
12 24
9 24
9 24
9 24
9 24
9 24
9 24
9 24
9 24
9 24
9 24
9 24
8 24
7 24
6 24
5 24
5 25