Іван-царевич у пошуках смерті Кощія Безсмертного прийшов до чарівного гаю. За словами Баби-Яги, у ньому ростуть $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