이반 차레비치(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$)가 주어집니다.

다음 $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