AT_ajo2024_final_b.Meetings

AtCoder 先生有 $N$ 个会议的日程安排。

会议按优先级从高到低编号为 $1$ 到 $N$。第 $i$ 个会议可以选择在时刻 $L_i$ 到 $R_i$ 之间的任意连续 $1$ 个单位时间内进行。但同一时刻只能参加一场会议，不能同时参加多场会议。

因为 AtCoder 先生想尽可能多地休息，所以他希望将自己出席的最早一场会议的开始时间到最后一场会议的结束时间的时长最小化。如果有多种最优方案，他希望最后一场会议结束的时间尽量早。

请你分别回答 $k = 1, 2, \dots, N$ 时的如下问题：

• 出席会议 $1$ 到 $k$ 时，是否能够全部参加？如能，请求出采取最优策略时，最早一场会议的开始时刻与最后一场会议的结束时刻。

输入为以下格式，通过标准输入读入。

$N$
$L_1$ $R_1$
$L_2$ $R_2$
$\vdots$
$L_N$ $R_N$

请输出 $N$ 行。

第 $k$ 行对应出席会议 $1$ 到 $k$ 的情况：

• 如果 $k$ 场会议都能参加，输出最早一场会议的开始时间与最后一场会议的结束时间，用空格分隔。
• 如果无法全部参加，输出 Impossible。

样例解释 1

例如，要同时参加会议 $1, 2, 3$ 时，最优策略如下：

• 将会议 $2$ 安排在时刻 $3$ 开始，$4$ 结束。
• 将会议 $3$ 安排在时刻 $4$ 开始，$5$ 结束。
• 将会议 $1$ 安排在时刻 $5$ 开始，$6$ 结束。

约束条件

• $1 \leq N \leq 180\,000$
• $0 \leq L_i < R_i \leq 180\,000$
• 所有输入均为整数。

由 ChatGPT 5 翻译