Иван-царевич в поисках смерти Кощея Бессмертного пришел в волшебную рощу. По словам Бабы-Яги, в ней растут $n$ мудрых дубов, среди которых ровно $k$ дубов всегда говорят правду, а остальные — всегда лгут.

Чтобы узнать, куда идти дальше, царевичу нужно узнать у дубов дальнейший маршрут. Однако он должен быть предельно осторожен, ведь если он последует совету одного из лгущих дубов, то забредет в болото, где его подстережет одноглазое Лихо.

Чтобы понять, каким дубам можно доверять, Иван задал каждому дубу вопрос вида: «Дуб номер $i$, скажи мне, правда ли, что дуб номер $a_i$ всегда говорит правду?» Однако он никак не может понять, что делать с полученными ответами.

Помогите Ивану-царевичу сделать выводы из вопросов. Для каждого дуба определите, всегда ли он говорит правду, всегда лжет, или информации недостаточно. Если же Баба-Яга обманула Ивана-царевича и не существует возможной конфигурации дубов, удовлетворяющей входным данным, выведите одно число $-2$.

Входные данные

Первая строка содержит два целых числа $n$ и $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$), обозначающих количество дубов и то, сколько из них всегда говорят правду, соответственно.

В $i$-й из следующих $n$ строк содержатся два целых числа $a_i$ и $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$), означающие, что дубу номер $i$ был задан вопрос, всегда ли дуб номер $a_i$ говорит правду, и ответ был «да», если $b_i = 1$, или «нет» в противном случае.

Выходные данные

Если входные данные противоречивы, выведите одно целое число $-2$.

В противном случае выведите $n$ целых чисел $t_1, t_2, \dots, t_n$ — выводы о том, говорят ли дубы правду. Они могут принимать следующие значения:

• $t_i = 1$, если дуб номер $i$ всегда говорит правду;
• $t_i = -1$, если дуб номер $i$ всегда лжет;
• $t_i = 0$, если по имеющимся данным невозможно определить, всегда ли лжет или говорит правду дуб номер $i$.

Примеры

Входные данные 1

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

Выходные данные 1

0 0 -1 1 1 1

Входные данные 2

3 1
2 0
3 0
1 0

Выходные данные 2

-2