ICPC 世界总决赛如期而至，这里有你想要参加的各种活动——演讲、展示、趣味活动，更不用说比赛本身了。这里只有一个问题：你什么时候睡觉？

当你入睡时，你总是会设置一个定时器，否则你可能会永远睡下去。使用定时器，你可以选择睡任意正整数分钟。睡了 $k$ 分钟后，你将获得 $k$ 分钟的休息时间（在此期间你无法再次入睡）；之后你将有 $k$ 分钟的活动时间（在此期间你可以保持清醒，也可以根据需要再次入睡）。

你知道决赛中所有活动的具体时间；你应该规划好你的睡眠时间表，以确保不错过任何活动的任何部分。在决赛开始前（第 0 分钟），你将在长途跋涉后抵达酒店房间，并需要立即睡觉。

输入格式

输入的第一行包含一个正整数 $n$ ($1 \le n \le 200\,000$)，表示为决赛计划的活动数量。

接下来的 $n$ 行中，第 $i$ 行包含两个正整数 $b_i$ 和 $e_i$ ($b_i < e_i, e_i \le b_{i+1}, 0 \le b_1, e_n \le 10^{10}$)，分别表示活动的开始时间和结束时间，单位为从决赛开始算起的分钟数。

输出格式

如果能找到一个睡眠时间表，让你能够完整参加所有计划的活动，则按以下格式输出该时间表。否则，输出 impossible。

睡眠时间表由一行包含睡眠周期数 $p$ ($1 \le p \le 10^6$) 的行指定，随后是 $p$ 行。这 $p$ 行中的第 $i$ 行包含两个整数 $s_i$ 和 $t_i$，分别表示第 $i$ 个睡眠周期的开始时间和结束时间，单位为从决赛开始算起的分钟数。注意，你不应输出最后一个活动之后的任何睡眠周期。

睡眠周期必须满足 $0 = s_1 < t_1 < s_2 < t_2 < \dots < t_p \le b_n$，并且满足题目中关于睡眠周期后一段时间内无法入睡的限制条件。你可以在活动结束后立即入睡（因此可能存在 $s_i = e_j$），也可以在活动开始前刚好醒来（因此可能存在 $t_i = b_j$）。

如果有多个有效的睡眠时间表，输出其中任意一个即可。可以证明，如果存在有效的睡眠时间表，则一定存在一个睡眠周期数不超过 $10^6$ 的时间表。

样例

输入格式 1

3
30 45
60 90
120 180

输出格式 1

2
0 30
90 120

输入格式 2

1
0 60

输出格式 2

impossible

输入格式 3

7
31 32
35 41
48 55
69 91
1000 2022
2022 2023
2994 4096

输出格式 3

5
0 5
10 28
56 68
92 900
2025 2900