ICPC 2023 · Problem H · Jet Lag

Time limit: 2 seconds

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\le n\le 200 000$), the number of activities planned for the Finals.

The $i$th of the remaining $n$ lines contains two positive integers $b_{i}$ and $e_{i}$ ($bi < ei$, $ei \le bi+1$, $0 \le b_{1}$, $en \le 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$th of these lines contains two integers $s_{i}$ and $t_{i}$ – the beginning and end time of the $i$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 = s1 < t1 < s2 < t2 < . . . < tp \le bn$ 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 $si =ej$) and you may wake up just before an activity (so it may be that $ti =bj$).

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.

Sample Input 1

3
30 45
60 90
120 180

Sample Output 1

2
0 30
90 120

Sample Input 2

1
0 60

Sample Output 2

impossible

Sample Input 3

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

Sample Output 3

5
0 5
10 28
56 68
92 900
2025 2900