配点 : 1000 点
問題文
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
- 所有输入均为整数
入力
输入是按以下格式从标准输入给出的。 请输出超过
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输出
入力例 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