伊凡王子（Ivan Tsarevich）為了尋找不死科斯切伊（Koschei the Deathless）的死穴，來到了一片魔法樹林。根據芭芭雅嘎（Baba Yaga）的說法，樹林裡有 $n$ 棵智慧橡樹，其中恰好有 $k$ 棵橡樹總是說真話，而其餘的橡樹總是說謊。

為了知道接下來該往哪裡走，王子需要從橡樹那裡得知後續的路線。然而，他必須極其謹慎，因為一旦他聽信了某棵說謊橡樹的建議，他就會誤入沼澤，遭到獨眼怪利霍（Likho）的伏擊。

為了弄清楚哪些橡樹可以信任，伊凡向每棵橡樹詢問了一個問題，形式為：「第 $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