Hoàng tử Ivan (Ivan Tsarevich), trong hành trình tìm kiếm cái chết của Koschei Bất Tử, đã đến một khu rừng phép thuật. Theo lời Baba Yaga, trong rừng có $n$ cây sồi thông thái, trong đó có đúng $k$ cây sồi luôn nói thật, còn những cây khác luôn nói dối.

Để biết phải đi đâu tiếp theo, Hoàng tử cần hỏi đường đi tiếp theo từ những cây sồi. Tuy nhiên, chàng phải hết sức thận trọng, vì nếu nghe theo lời khuyên của một trong những cây sồi nói dối, chàng sẽ lạc vào đầm lầy nơi quái vật một mắt Likho đang phục kích.

Để tìm ra những cây sồi nào có thể tin tưởng được, Ivan đã hỏi mỗi cây sồi một câu hỏi có dạng: "Cây sồi số $i$, hãy nói cho ta biết, cây sồi số $a_i$ có phải luôn nói thật không?" Tuy nhiên, chàng không biết phải suy luận thế nào từ những câu trả lời nhận được.

Hãy giúp Hoàng tử Ivan rút ra kết luận từ các câu hỏi. Với mỗi cây sồi, hãy xác định xem nó luôn nói thật, luôn nói dối, hay thông tin chưa đủ để kết luận. Nếu Baba Yaga đã lừa Hoàng tử Ivan và không tồn tại cấu hình cây sồi nào thỏa mãn dữ liệu đầu vào, hãy in ra một số duy nhất là $-2$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$), lần lượt biểu thị số lượng cây sồi và số lượng cây sồi trong đó luôn nói thật.

Dòng thứ $i$ trong $n$ dòng tiếp theo chứa hai số nguyên $a_i$ và $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$), biểu thị rằng cây sồi số $i$ đã được hỏi liệu cây sồi số $a_i$ có luôn nói thật hay không, và câu trả lời là "có" nếu $b_i = 1$, hoặc "không" trong trường hợp ngược lại.

Kết quả

Nếu dữ liệu đầu vào mâu thuẫn, hãy in ra một số nguyên duy nhất là $-2$.

Ngược lại, hãy in ra $n$ số nguyên $t_1, t_2, \dots, t_n$: kết luận về việc các cây sồi có nói thật hay không. Chúng có thể nhận các giá trị sau:

• $t_i = 1$ nếu cây sồi số $i$ luôn nói thật;
• $t_i = -1$ nếu cây sồi số $i$ luôn nói dối;
• $t_i = 0$ nếu không thể xác định được cây sồi số $i$ luôn nói dối hay luôn nói thật từ dữ liệu hiện có.

Ví dụ

Dữ liệu vào 1

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

Kết quả 1

0 0 -1 1 1 1

Dữ liệu vào 2

3 1
2 0
3 0
1 0

Kết quả 2

-2