P4794 [BalticOI 2018] Alternating Current

### Abusing the judge for this problem will result in your account being banned.

**This problem is translated from [BalticOI 2018](https://boi2018.progolymp.se/tasks/) Day 2 “[Alternating Current](https://boi18-day2-open.kattis.com/problems/boi18.alternating)”.** You are given a circular track, which can be divided into $N$ equal-length segments, numbered $1 \ldots N$. At the same time, you have $M$ control points that can color certain segments of the track either red or blue. These $M$ control points are numbered $1 \ldots M$. Your task is to choose the colors of the segments controlled by these $M$ points so that every point on the track is covered by at least one red segment and at least one blue segment. It is guaranteed that there is no part of the circle that cannot be colored.

The first line contains two integers $N$ and $M$, representing the number of track segments and the number of control points. The next $M$ lines each contain two integers $a$ and $b$, representing the left and right endpoints of the range that the control point can color. In particular, if $a=b$, then this control point only controls the single segment $a$ with length $1$; if $b < a$, then this control point can control all segments with indices in the interval $[a,\, N]\cup[1,\,b]$.

Output one line containing $M$ characters. Each character is either ``0`` or ``1``, indicating whether the segment controlled by the $i$-th control point is colored red or blue. If there are multiple solutions, output any one of them. If there is no solution, output ``impossible``.

#### Explanation for Sample 1  The figure above shows one solution for Sample 1. Note that you can reverse all arrows to obtain another valid solution ``11010``. ## Constraints | Subtask | Score | Constraints | Additional Constraints | |:------:|:-----:|:-----------:|:----------------------:| | $1$ | $13$ | $2\leqslant N,\,M\leqslant15$ | . | | $2$ | $20$ | $2\leqslant N,\,M\leqslant100$ | . | | $3$ | $22$ | $2\leqslant N,\,M\leqslant1000$ | . | | $4$ | $19$ | $2\leqslant N,\,M\leqslant100\,000$ | It is guaranteed that $b\geqslant a$. | | $5$ | $26$ | $2\leqslant N,\,M\leqslant100\,000$ | 　| Thanks to Hatsune_Miku for providing the translation. # Input Format # Output Format # Hint Translated by ChatGPT 5