Iván Tsarévich, en busca de la muerte de Koschéi el Inmortal, ha llegado a una arboleda mágica. Según Baba Yagá, en ella hay $n$ robles sabios, entre los cuales exactamente $k$ robles dicen siempre la verdad, mientras que los demás siempre mienten.

Para saber adónde ir a continuación, el Tsarévich necesita conocer la ruta a seguir a través de los robles. Sin embargo, debe ser extremadamente precavido, ya que si sigue el consejo de uno de los robles mentirosos, se adentrará en un pantano donde el Lijo tuerto le tenderá una emboscada.

Para averiguar en qué robles puede confiar, Iván le ha hecho a cada roble una pregunta de la forma: «Roble número $i$, dime, ¿el roble número $a_i$ siempre dice la verdad?». Sin embargo, no logra deducir qué hacer con las respuestas que ha recibido.

Ayuda a Iván Tsarévich a sacar conclusiones de las preguntas. Para cada roble, determina si siempre dice la verdad, si siempre miente o si la información es insuficiente. Si Baba Yagá ha engañado a Iván Tsarévich y no existe ninguna configuración posible de robles que satisfaga los datos de entrada, imprime un único número $-2$.

Entrada

La primera línea contiene dos enteros $n$ y $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$), que denotan el número de robles y cuántos de ellos dicen siempre la verdad, respectivamente.

La $i$-ésima de las siguientes $n$ líneas contiene dos enteros $a_i$ y $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$), que indican que al roble número $i$ se le ha preguntado si el roble número $a_i$ siempre dice la verdad, y la respuesta ha sido «sí» si $b_i = 1$, o «no» en caso contrario.

Salida

Si los datos de entrada son contradictorios, imprime un solo entero $-2$.

En caso contrario, imprime $n$ enteros $t_1, t_2, \dots, t_n$: las conclusiones sobre si los robles dicen la verdad. Pueden tomar los siguientes valores:

• $t_i = 1$ si el roble número $i$ siempre dice la verdad;
• $t_i = -1$ si el roble número $i$ siempre miente;
• $t_i = 0$ si es imposible determinar a partir de los datos disponibles si el roble número $i$ siempre miente o siempre dice la verdad.

Ejemplos

Entrada 1

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

Salida 1

0 0 -1 1 1 1

Entrada 2

3 1
2 0
3 0
1 0

Salida 2

-2