Ívan Tsarevítsj, í leit sinni að dauða Kosjtsjejs hins ódauðlega, er kominn í töfralund. Samkvæmt Baba Jaga eru $n$ vitrar eikur í honum, og þar af segja nákvæmlega $k$ eikur alltaf satt, en hinar ljúga alltaf.

Til að komast að því hvert hann á að fara næst þarf Tsarevítsj að fá upplýsingar um framhaldsleiðina frá eikunum. Hins vegar verður hann að vera afar varkár, því ef hann fer að ráðum einhverrar af lygaeikunum mun hann villast út í mýri þar sem hið eineygða Líkó situr fyrir honum.

Til að komast að því hvaða eikum hann getur treyst hefur Ívan spurt hverja eik spurningar á forminu: „Eik númer $i$, segðu mér, segir eik númer $a_i$ alltaf satt?“ Hins vegar áttar hann sig ekki á því hvað hann á að gera við svörin sem hann hefur fengið.

Hjálpaðu Ívani Tsarevítsj að draga ályktanir af spurningunum. Fyrir hverja eik skaltu ákvarða hvort hún segir alltaf satt, lýgur alltaf eða hvort upplýsingarnar séu ófullnægjandi. Ef Baba Jaga hefur blekkt Ívan Tsarevítsj og engin möguleg samsetning eika uppfyllir inntaksgögnin, skaltu prenta eina tölu $-2$.

Inntak

Fyrsta línan inniheldur tvær heiltölur $n$ og $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$), sem tákna fjölda eika og hversu margar þeirra segja alltaf satt, í sömu röð.

Lína $i$ af næstu $n$ línum inniheldur tvær heiltölur $a_i$ og $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$), sem táknar að eik númer $i$ hafi verið spurð hvort eik númer $a_i$ segi alltaf satt, og svarið hafi verið „já“ ef $b_i = 1$, en „nei“ annars.

Úttak

Ef inntaksgögnin eru mótsagnakennd, prentaðu eina heiltölu $-2$.

Annars skaltu prenta $n$ heiltölur $t_1, t_2, \dots, t_n$: ályktanir um hvort eikurnar segi satt. Þær geta tekið eftirfarandi gildi:

• $t_i = 1$ ef eik númer $i$ segir alltaf satt;
• $t_i = -1$ ef eik númer $i$ lýgur alltaf;
• $t_i = 0$ ef ómögulegt er að ákvarða út frá tiltækum gögnum hvort eik númer $i$ lýgur alltaf eða segir alltaf satt.

Dæmi

Inntak 1

6 4
2 0
1 0
3 1
3 0
3 0
6 1

Úttak 1

0 0 -1 1 1 1

Inntak 2

3 1
2 0
3 0
1 0

Úttak 2

-2