Problem G
Maiņstrāva

Frederiks tagad ir mājās un spēlējas ar paštaisītu rotaļu dzelzceļu, par kuru viņš ir ļoti lepns. Dzelzceļš sastāv no $N$ segmentiem, kas ir savienoti riņķī un sanumurēti kā $1, 2, \dots , N$ pulksteņa rādītāja virzienā. Elektrisko strāvu dzelzceļam nodrošina $M$ izliekti vadi, kas iet līdzi dzelzceļam. Katram segmentam līdzi iet vismaz viens vads.

Tiesa gan, Frederikam kļūst garlaicīgi skatīties uz riņķojošo vilcienu, tāpēc viņš nolemj pievienot dzelzceļa pārmiju katram segmentam, ko viņš varētu izmantot, lai izraisītu vilciena noskriešanu no sliedēm, kā arī citām aizraujošām lietām. Pārmijas arī prasa elektrisko strāvu. Un ne jebkādu strāvu — tās prasa tieši maiņstrāvu.¹

Lai iegūtu maiņstrāvu, Frederiks spriež, ir jābūt strāvai, kas plūst abos virzienos. Katrs vads dod strāvu tikai vienā virzienā (vai nu pulksteņa rādītāja virzienā, vai nu otrādi), bet Frederiks var brīvi izlemt, kurā. Secīgi, viņam ir jāizvēlas, kāds strāvas virziens būs katram vadam, tā, lai katru dzelzceļa segmentu noklāj gan vads ar pulksteņa rādītāja virziena strāvu, gan vads ar pretēju strāvu.

Vai jūs varat palīdzēt Frederikam ar šo uzdevumu?

Atrisinājums pirmajam piemēram. Izliektas bultiņas ārpus dzelzceļa apzīmē vadus, kas pievada elektrību. Katras bultiņas virziens ir Frederika izvēlētais strāvas virziens (zila un sarkana krāsa apzīmē dažādus virzienus). Ievērojiet, ka visas bultiņas var apvērst pretējā virzienā un iegūt citu pareizu atrisinājumu: 11010.

Ievaddati

Pirmā rinda satur divus veselus skaitļus $N$ un $M$, attiecīgi dzelzceļa segmentu skaitu un vadu skaitu.

Nākamās $M$ rindas katra satur divus skaitļus $1 \le a, b \le N$, kas nozīmē, ka ir vads, kas noklāj segmentus $a, a+1, \dots , b$. Ja $b$ ir mazāks par $a$, tas nozīmē, ka numuri iet pa riņķi, t. i., vads noklāj segmentus $a, \dots , N, 1, \dots , b$. Ievērojiet, ka, ja $a=b$, tad vads noklāj tikai vienu segmentu.

Izvaddati

Izvadiet vienu rindu ar $M$ simboliem, katru vai nu 0, vai nu 1. $i$-jam simbolam rindā ir jābūt 0, ja strāva $i$-jā vadā ir jāvirza pulksteņa rādītāja virzienā, vai 1, ja tā ir jāvirza pretējā virzienā. Ja pastāv vairāki atrisinājumi, izvadiet jebkuru no tiem.

Ja pareiza atrisinājuma nav, izvadiet “impossible”.

Ierobežojumi

Jūsu risinājums tiks testēts uz vairākām testu grupām, par katru no tām var iegūt punktus. Katra testu grupa satur vienu vai vairākus testus. Lai iegūtu punktus par testu grupu, jums ir pareizi jāatrisina visi testi šajā grupā. Jūsu beigu vērtējums par uzdevumu būs starp visiem iesūtījumiem lielākais.

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