Ivan Zarevic, alla ricerca della morte di Koschei l'Immortale, è giunto in un boschetto magico. Secondo Baba Jaga, in esso ci sono $n$ querce sagge, tra le quali esattamente $k$ querce dicono sempre la verità, mentre le altre mentono sempre.

Per scoprire dove andare dopo, lo Zarevic deve apprendere il percorso successivo dalle querce. Tuttavia, deve essere estremamente cauto, poiché se seguisse il consiglio di una delle querce bugiarde, finirebbe in una palude dove il Licho con un occhio solo gli tenderebbe un'imboscata.

Per capire di quali querce può fidarsi, Ivan ha posto a ciascuna quercia una domanda nella forma: "Quercia numero $i$, dimmi, la quercia numero $a_i$ dice sempre la verità?" Tuttavia, non riesce a capire cosa fare con le risposte che ha ricevuto.

Aiuta Ivan Zarevic a trarre conclusioni dalle domande. Per ciascuna quercia, determina se dice sempre la verità, se mente sempre, oppure se le informazioni sono insufficienti. Se Baba Jaga ha ingannato Ivan Zarevic e non esiste alcuna configurazione possibile di querce che soddisfi i dati di input, stampa un singolo numero $-2$.

Input

La prima riga contiene due interi $n$ e $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$), che indicano rispettivamente il numero di querce e quante di esse dicono sempre la verità.

La $i$-esima delle successive $n$ righe contiene due interi $a_i$ e $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$), che indicano che alla quercia numero $i$ è stato chiesto se la quercia numero $a_i$ dice sempre la verità, e la risposta è stata "sì" se $b_i = 1$, oppure "no" altrimenti.

Output

Se i dati di input sono contraddittori, stampa un singolo intero $-2$.

Altrimenti, stampa $n$ interi $t_1, t_2, \dots, t_n$: le conclusioni sul fatto che le querce dicano o meno la verità. Possono assumere i seguenti valori:

• $t_i = 1$ se la quercia numero $i$ dice sempre la verità;
• $t_i = -1$ se la quercia numero $i$ mente sempre;
• $t_i = 0$ se è impossibile determinare dai dati disponibili se la quercia numero $i$ menta sempre o dica sempre la verità.

Esempi

Input 1

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

Output 1

0 0 -1 1 1 1

Input 2

3 1
2 0
3 0
1 0

Output 2

-2