Iwan Carewicz, poszukując śmierci Kościeja Nieśmiertelnego, dotarł do magicznego gaju. Według Baby Jagi rośnie w nim $n$ mądrych dębów, spośród których dokładnie $k$ dębów zawsze mówi prawdę, a pozostałe zawsze kłamią.

Aby dowiedzieć się, dokąd iść dalej, Carewicz musi poznać dalszą drogę od dębów. Musi jednak zachować najwyższą ostrożność, gdyż jeśli posłucha rady jednego z kłamiących dębów, zabłądzi na bagna, gdzie zaczai się na niego jednookie Licho.

Aby ustalić, którym dębom może zaufać, Iwan zadał każdemu dębowi pytanie w postaci: „Dębie numer $i$, powiedz mi, czy dąb numer $a_i$ zawsze mówi prawdę?”. Nie potrafi jednak wyciągnąć wniosków z otrzymanych odpowiedzi.

Pomóż Iwanowi Carewiczowi wyciągnąć wnioski z zadanych pytań. Dla każdego dębu określ, czy zawsze mówi prawdę, czy zawsze kłamie, czy też informacje są niewystarczające. Jeśli Baba Jaga oszukała Iwana Carewicza i nie istnieje żadna możliwa konfiguracja dębów zgodna z danymi wejściowymi, wypisz jedną liczbę $-2$.

Wejście

Pierwszy wiersz zawiera dwie liczby całkowite $n$ oraz $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$), oznaczające odpowiednio liczbę dębów oraz liczbę tych spośród nich, które zawsze mówią prawdę.

W $i$-tym z kolejnych $n$ wierszy znajdują się dwie liczby całkowite $a_i$ oraz $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$), oznaczające, że dębowi numer $i$ zadano pytanie, czy dąb numer $a_i$ zawsze mówi prawdę, a odpowiedź brzmiała „tak”, jeśli $b_i = 1$, lub „nie” w przeciwnym przypadku.

Wyjście

Jeśli dane wejściowe są sprzeczne, wypisz jedną liczbę całkowitą $-2$.

W przeciwnym razie wypisz $n$ liczb całkowitych $t_1, t_2, \dots, t_n$: wnioski dotyczące prawdomówności kolejnych dębów. Mogą one przyjmować następujące wartości:

• $t_i = 1$, jeśli dąb numer $i$ zawsze mówi prawdę;
• $t_i = -1$, jeśli dąb numer $i$ zawsze kłamie;
• $t_i = 0$, jeśli na podstawie dostępnych danych nie da się ustalić, czy dąb numer $i$ zawsze kłamie, czy zawsze mówi prawdę.

Przykłady

Wejście 1

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

Wyjście 1

0 0 -1 1 1 1

Wejście 2

3 1
2 0
3 0
1 0

Wyjście 2

-2