Problem Description

Translated from BalticOI 2018 Day2「Alternating Current」

Given a ring that can be divided into equal-length segments numbered from $1$ to $N$. You can use $M$ control points to color a segment of the ring either red or blue. These $M$ control points are numbered from $1$ to $M$.

Determine how to arrange the colors controlled by these $M$ points such 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 are no segments that cannot be colored.

Input Format

The first line contains two integers $N$ and $M$, representing the number of track segments and the number of control points, respectively.

The next $M$ lines each contain two integers $a$ and $b$, indicating the left and right endpoints of the segments that each control point can color. Specifically, if $a = b$, the control point only controls the segment $a$ of length 1; if $b < a$, it means the control point can control all segments in the range $[a, N] \cup [1, b]$.

Output Format

Output a line with $M$ characters, each being either 0 or 1, indicating whether the segment controlled by the $i$-th control point should be colored red or blue.

If there are multiple solutions, output any one of them. If there is no solution, output impossible.

Sample Input and Output

Input Sample #1

10 5
1 5
6 7
5 1
7 2
2 4

Output Sample #1

00101

Input Sample #2

10 5
1 4
2 5
4 7
6 10
8 1

Output Sample #2

impossible

Input Sample #3

5 2
1 5
3 3

Output Sample #3

impossible

Input Sample #4

5 3
3 3
2 1
4 2

Output Sample #4

101

Notes

Sample 1 Explanation

The above image shows a solution for Sample 1. Note that reversing all arrows yields another valid solution 11010.

Constraints and Hints

见题面 Input 部分

见题面 Output 部分