Iivana Tsarevitš on Kuolemattoman Koštšein kuolemaa etsiessään saapunut taikalehtoon. Baba Jagan mukaan lehdossa on $n$ viisasta tammea, joista täsmälleen $k$ tammea puhuu aina totta, kun taas muut valehtelevat aina.
Saadakseen selville, minne mennä seuraavaksi, Tsarevitšin täytyy kysyä jatkoreittiä tammilta. Hänen on kuitenkin oltava äärimmäisen varovainen, sillä jos hän noudattaa valehtelevan tammen neuvoa, hän harhautuu suolle, jossa yksisilmäinen Liho väijyy häntä.
Selvittääkseen, mihin tammiin hän voi luottaa, Iivana on esittänyt jokaiselle tammelle kysymyksen muodossa: ”Tammi numero $i$, kerro minulle, puhuuko tammi numero $a_i$ aina totta?” Hän ei kuitenkaan keksi, mitä tehdä saamillaan vastauksilla.
Auta Iivana Tsarevitšia tekemään johtopäätökset kysymyksistä. Määritä jokaisesta tammesta, puhuuko se aina totta, valehteleeko se aina, vai ovatko tiedot riittämättömät. Jos Baba Jaga on pettänyt Iivana Tsarevitšia eikä syötettä vastaavaa tammien asetelmaa ole olemassa, tulosta yksi luku $-2$.
Syöte
Ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$), jotka ilmaisevat tammien lukumäärän ja sen, kuinka moni niistä puhuu aina totta.
Seuraavista $n$ rivistä $i$-s sisältää kaksi kokonaislukua $a_i$ ja $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$), mikä tarkoittaa, että tammelta numero $i$ on kysytty, puhuuko tammi numero $a_i$ aina totta, ja vastaus on ollut ”kyllä”, jos $b_i = 1$, ja muuten ”ei”.
Tuloste
Jos syötteen tiedot ovat ristiriitaisia, tulosta yksi kokonaisluku $-2$.
Muussa tapauksessa tulosta $n$ kokonaislukua $t_1, t_2, \dots, t_n$: johtopäätökset siitä, puhuvatko tammet totta. Ne voivat saada seuraavat arvot:
- $t_i = 1$, jos tammi numero $i$ puhuu aina totta;
- $t_i = -1$, jos tammi numero $i$ valehtelee aina;
- $t_i = 0$, jos käytettävissä olevista tiedoista on mahdotonta päätellä, valehteleeko tammi numero $i$ aina vai puhuuko se aina totta.
Esimerkit
Syöte 1
6 4 2 0 1 0 3 1 3 0 3 0 6 1
Tuloste 1
0 0 -1 1 1 1
Syöte 2
3 1 2 0 3 0 1 0
Tuloste 2
-2