Background

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

Problem Description

This problem is translated from BalticOI 2018 Day 2 “Alternating Current”.

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.

Input Format

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 Format

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.

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

00101

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

impossible

5 2
1 5
3 3

impossible

5 3
3 3
2 1
4 2

101

Hint

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

Thanks to Hatsune_Miku for providing the translation.

Input Format

Output Format

Hint

Translated by ChatGPT 5