Humanity's Last Code Exam / 2023_H / 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≤n≤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) (b_(i)<e_(i),e_(i)≤b_(i+1),0≤b₁,e_(n)≤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⁶) 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=s₁<t₁<s₂<t₂<…<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⁶ sleep periods.

### Sample Input 1

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\)-th of the remaining \(n\) lines contains two positive integers \(b_i\) and \(e_i\) \((b_i < e_i, e_i \leq b_{i+1}, 0 \leq 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 \leq p \leq 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 = 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.

### Sample Input 1