Page not loading? Try clicking here.
Placeholder

#8291

Jet Lag 2s 1024MB

Problems

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

The ith of the remaining n lines contains two positive integers b_i and e_i (b_i<e_i, e_i≤b_i+1, 0≤b_1, e_n≤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≤p≤10^6) of sleep periods, followed by p lines. The ith of these lines contains two integers s_i and t_i — the beginning and end time of the ith 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<\dots <t_p≤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.


Example #1

3
30 45
60 90
120 180
2
0 30
90 120

Example #2

1
0 60
impossible

Example #3

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

Source

ICPC World Finals 2023 H번

You must sign in to write code.