Ivan Tsarevitj har i sitt sökande efter Kosjtjej den odödliges död kommit till en magisk lund. Enligt Baba Jaga finns det $n$ visa ekar i den, bland vilka exakt $k$ ekar alltid talar sanning, medan de övriga alltid ljuger.

För att ta reda på vart han ska gå härnäst måste Tsarevitj få veta den fortsatta vägen av ekarna. Han måste dock vara ytterst försiktig, för om han följer rådet från en av de ljugande ekarna kommer han att vandra in i ett träsk där det enögda Licho ligger i bakhåll.

För att lista ut vilka ekar han kan lita på har Ivan ställt en fråga till varje ek på formen: "Ek nummer $i$, säg mig, talar ek nummer $a_i$ alltid sanning?" Han kan dock inte lista ut vad han ska göra med svaren han har fått.

Hjälp Ivan Tsarevitj att dra slutsatser från frågorna. För varje ek, avgör om den alltid talar sanning, alltid ljuger eller om informationen är otillräcklig. Om Baba Jaga har lurat Ivan Tsarevitj och det inte finns någon möjlig konfiguration av ekar som uppfyller indatan, skriv ut ett enda tal $-2$.

Indata

Den första raden innehåller två heltal $n$ och $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$), som anger antalet ekar respektive hur många av dem som alltid talar sanning.

Den $i$-te av de följande $n$ raderna innehåller två heltal $a_i$ och $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$), som anger att ek nummer $i$ har tillfrågats om ek nummer $a_i$ alltid talar sanning, och att svaret har varit "ja" om $b_i = 1$, eller "nej" annars.

Utdata

Om indatan är motsägelsefull, skriv ut ett enda heltal $-2$.

Annars, skriv ut $n$ heltal $t_1, t_2, \dots, t_n$: slutsatser om huruvida ekarna talar sanning. De kan anta följande värden:

• $t_i = 1$ om ek nummer $i$ alltid talar sanning;
• $t_i = -1$ om ek nummer $i$ alltid ljuger;
• $t_i = 0$ om det är omöjligt att avgöra om ek nummer $i$ alltid ljuger eller talar sanning utifrån tillgänglig data.

Exempel

Indata 1

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

Utdata 1

0 0 -1 1 1 1

Indata 2

3 1
2 0
3 0
1 0

Utdata 2

-2