Ivan Tsarevich, in search of the death of Koschei the Deathless, has come to a magical grove. According to Baba Yaga, there are $n$ wise oaks in it, among which exactly $k$ oaks always tell the truth, while the others always lie.

To find out where to go next, the Tsarevich needs to learn the further route from the oaks. However, he must be extremely cautious, as if he follows the advice of one of the lying oaks, he will wander into a swamp where the one-eyed Likho would ambush him.

To figure out which oaks he can trust, Ivan has asked each oak a question in the form: "Oak number $i$, tell me, does the oak number $a_i$ always tell the truth?" However, he cannot figure out what to do with the answers he has received.

Help Ivan Tsarevich draw conclusions from the questions. For each oak, determine whether it always tells the truth, always lies, or if the information is insufficient. If Baba Yaga has deceived Ivan Tsarevich and there is no possible configuration of oaks that satisfies the input data, output a single number $-2$.

Input

The first line contains two integers $n$ and $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$), denoting the number of oaks and how many of them always tell the truth, respectively.

The $i$-th of the next $n$ lines contains two integers $a_i$ and $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$), denoting that the oak number $i$ has been asked whether the oak number $a_i$ always tells the truth, and the answer has been "yes" if $b_i = 1$, or "no" otherwise.

Output

If the input data are contradictory, print a single integer $-2$.

Otherwise, print $n$ integers $t_1, t_2, \dots, t_n$: conclusions about whether the oaks tell the truth. They can take the following values:

• $t_i = 1$ if the oak number $i$ always tells the truth;
• $t_i = -1$ if the oak number $i$ always lies;
• $t_i = 0$ if it is impossible to determine whether the oak number $i$ always lies or tells the truth from the available data.

Examples

Input 1

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

Output 1

0 0 -1 1 1 1

Input 2

3 1
2 0
3 0
1 0

Output 2

-2