伊凡·沙皇子为了寻找不死之身科斯切伊的死穴，来到了一个魔法橡树林。根据芭芭·雅加的说法，林子里有 $n$ 棵智慧橡树，其中恰好有 $k$ 棵橡树总是说真话，而其余的橡树总是说谎。

为了知道接下来该往哪里走，沙皇子需要从橡树那里了解后续的路线。然而，他必须极其谨慎，因为如果他听信了某棵说谎的橡树的建议，他就会误入沼泽，遭到独眼利霍的伏击。

为了弄清楚哪些橡树是可以信任的，伊凡向每棵橡树提了一个问题，形式为：“第 $i$ 棵橡树，请告诉我，第 $a_i$ 棵橡树是不是总是说真话？”然而，他无法根据得到的回答推导出结论。

请帮助伊凡·沙皇子从这些问题中得出结论。对于每棵橡树，确定它是否总是说真话、总是说谎，或者信息不足。如果芭芭·雅加欺骗了伊凡·沙皇子，且不存在任何满足输入数据的橡树配置，则输出一个数字 $-2$。

输入格式

第一行包含两个整数 $n$ 和 $k$（$1 \le n \le 5 \cdot 10^5$，$0 \le k \le n$），分别表示橡树的数量以及其中总是说真话的橡树数量。

接下来的 $n$ 行中，第 $i$ 行包含两个整数 $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