4. Slizká pochúťka

Ak nevieš programovať, nezúfaj! Môžeš sa to naučiť a ešte za to získať body, ktoré sa ti budú počítať namiesto tejto úlohy. Stačí, že pôjdeš na stránku Programátorskej Liahne (liahen.ksp.sk). Keď budeš riešiť sadu variables_cpp, bodmi, ktoré získaš si môžeš nahradiť riešenie tejto úlohy. Stačí ak na spodku tejto stránky odovzdáš pdf-ko s prezývkou, ktorú používaš na Liahni.

Ak máte akékoľvek otázky ohľadom tejto úlohy, napíšte Danovi na [email protected]

Krtko má rád dážďovky, najlepšie natreté omáčkou. Nemyslite si ale, že to je len tak. Na niektoré časti dážovky sa omáčka proste nehodí. To môže byť spôsobené napríklad nadmerným množstvom povrchového slizu, ktorý je sám o sebe lahodný, s omáčkou je však k ničomu. Krtko je veľmi skúsený dážďovkár, vďaka čomu vie hneď na prvý pohľad povedať, ktoré úseky dážďovky sa oplatí natrieť.

Krtko dážďovky natiera tak, že sa postaví do dostatočnej vzdialenosti, aby dážďovku videl celú. Následne si zapíše pod seba úseky, ktoré treba natrieť. Ako všetci vieme, každá dážďovka sa skladá z \(n\) políčok očíslovaných v poradí od 1 po \(n\). Krtko si teda bude zapisovať úseky \([a, b]\), kde \(a\) je prvé políčko úseku, ktorý chce natrieť a \(b\) je posledné políčko tohoto úseku. Často sa mu však stáva, že počas zapisovania zabudne, že niektoré políčko si už zapísal a tak ho zapíše aj do ďalšieho úseku. Jeho papier teda môže vyzerať tak, že sú na ňom napríklad úseky \([1, 4]\) a \([3, 7]\). Môžeme si všimnúť, že políčka \(3\) a \(4\) sú tu zahrnuté v oboch úsekoch napísaných na papieri a budú teda natreté dvakrát. Toľké plytvanie omáčkou! Uvedomil si to aj sám Krtko a tak vás požiadal, či by ste mu nenapísali program, ktorému ukáže svoj papier a on mu podľa toho nakreslí dážďovku tak, ako má byť natretá.

Úloha

Vašou úlohou je napísať program, ktorý na vstupe dostane Krtkov papier a na výstup nakreslí natretú dážďovku. To znamená, že pre každé políčko dážďovky určí, či má alebo nemá byť natreté. Nezaujíma nás, či niektoré políčko má byť podľa papiera natreté viackrát. Ak má byť natreté aspoň raz, prehlásime ho za natreté, v opačnom prípade za nenatreté.

Formát vstupu

Na prvom riadku vstupu sú dve celé čísla \(n\) (\(1 \leq n \leq 10^{6}\)) a \(q\) (\(0 \leq q \leq 10^{5}\)). Číslo \(n\) je počet políčok dážovky, číslo \(q\) je počet úsekov napísaných na Krtkovom papieri.

Nasleduje \(q\) riadkov popisujúcich Krtkov papier. Na každom sú dve celé čísla \(a\), \(b\) (\(1 \leq a \leq b \leq n\)). Tie hovoria, že má byť natretý úsek dážďovky od \(a\)-teho políčka po \(b\)-te vrátane. Úseky na papieri sa môžu ľubovoľne prekrývať. Je teda možné aj to, že niektoré políčka dážďovky budú zahrnuté vo všetkých úsekoch na papieri.

Formát výstupu

Na výstup vypíšte \(n\) medzerou oddelených čísiel. Ako \(i\)-te číslo vypíšte \(0\), ak je \(i\)-te políčko dážďovky nenatreté, v opačnom prípade vypíšte ako \(i\)-te číslo \(1\).

Hodnotenie

Príklady

Input:

8 4
4 7
1 1
3 5
6 7

Output:

1 0 1 1 1 1 1 0