Jet Lag

The ICPC World Finals are here and they are packed full of activities you want to attend — speeches, presentations, fun events, not to mention the contest itself. There is only one problem: when are you going to sleep?

When you fall asleep, you always set a timer because otherwise you would be able to sleep forever. Using the timer, you can choose to sleep for any positive integer amount of minutes. After sleeping for $k$ minutes, you will be rested for another $k$ minutes (and so you will not be able to fall asleep again); and then you will be able to function for a third $k$ minutes (so you can stay awake, but you can also go to sleep if you want to).

You know the times of all the activities at the Finals; you should plan your sleep schedule to not miss any part of any event. Just before the Finals start (at minute $0$), you will arrive in your hotel room after a long journey and you will need to sleep immediately.

Input

The first line of input contains a positive integer $n$ ($1\leq n \leq 200\, 000$), the number of activities planned for the Finals.

The $i^{\text {th}}$ of the remaining $n$ lines contains two positive integers $b_ i$ and $e_ i$ ($b_ i < e_ i$, $e_ i \le b_{i+1}$, $0 \le b_1$, $e_ n \leq 10^{10}$), the beginning and end time of the activity, counted in minutes from the beginning of the Finals.

Output

If it is possible to find a sleep schedule that allows you to participate in all planned activities in their entirety, then output such a schedule in the format described below. Otherwise, output impossible.

A sleep schedule is specified by a line containing the number $p$ ($1 \le p \le 10^6$) of sleep periods, followed by $p$ lines. The $i^{\text {th}}$ of these lines contains two integers $s_ i$ and $t_ i$ — the beginning and end time of the $i^{\text {th}}$ sleep period, counted in minutes from the beginning of the Finals. Note that you should not output any sleep period after the last activity.

The sleep periods must satisfy $0 = s_1 < t_1 < s_2 < t_2 < \ldots < t_ p \leq b_ n$ as well as the condition described in the statement that does not allow you to fall asleep for some time after a sleep period. You may fall asleep immediately after an activity (so it may be that $s_ i=e_ j$) and you may wake up just before an activity (so it may be that $t_ i=b_ j$).

If there are multiple valid sleep schedules, any one will be accepted. It can be shown that if there is a valid sleep schedule, then there is also one with at most $10^6$ sleep periods.

3
30 45
60 90
120 180

2
0 30
90 120

1
0 60

impossible

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

5
0 5
10 28
56 68
92 900
2025 2900