איוואן צארביץ', בחיפושיו אחר מותו של קושצ'יי בן האלמוות, הגיע לחורשה קסומה. לפי באבה יאגה, יש בה $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