Perhaps today and/or tomorrow due to a power outage there may be disruptions in the work of Codeforces and Polygon. Please do not plan any important events during this time. If there are details or the exact time, we will definitely publish them. Estimated time of maintenance: from 2 Aug, 16:00 (UTC) to 2 Aug, 20:00 (UTC). ×

C. Anime
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

Little Lesha studies in the sixth grade. Lesha is not the best performing student, and that's why his interests are rather peculiar. In particular, he finds it exciting to watch Chinese cartoons that are commonly known as anime.

Once, Lesha decided to skip school and devote the whole day to his favorite activity — watching anime. However, suddenly, he realized that there is a lot of trash on the shelf where he stores his anime discs.

The shelf contains $n$ items. The items are arranged in a row, i.e. can be enumerated from $1$ to $n$. The $i$-th item might be either trash or and anime disc. Lesha remembers that he has exactly $k$ discs, and that the $i$-th disc is located somewhere between the positions $l_i$ and $r_i$, inclusive.

Help Lesha clean the shelf and regain hope for a better future.

Input

The first line contains two integers separated by space: $n$, $k$. Each of the following $k$ lines also contains two integers: $l_i$, $r_i$.

$1 \le n \le 100228$

$0 \le k \le n$

$1 \le l_i \le r_i \le n$

Output

Print $n$ integer numbers, each equal to $0$ or $1$. The $i$-th number should be equal to $1$ if and only if the $i$-th item on the shelf is trash. It is guaranteed that one can always find an unambiguous solution.

Example
Input
5 0

Output
1 1 1 1 1