イワン皇子（Ivan Tsarevich）は、不死身のコシチェイ（Koschei the Deathless）の死の秘密を探し求めて、魔法の木立へとやって来ました。バーバ・ヤガー（Baba Yaga）によると、そこには $n$ 本の賢いオークの木があり、そのうちちょうど $k$ 本のオークは常に真実を語り、残りのオークは常に嘘をつくといいます。

次にどこへ行くべきかを知るため、皇子はオークたちから今後の道順を聞き出す必要があります。しかし、嘘つきのオークの助言に従ってしまうと、一つ目のリホ（Likho）が待ち伏せする沼地へと迷い込んでしまうため、細心の注意を払わなければなりません。

どのオークを信頼できるか見極めるため、イワンは各オークに「$i$ 番目のオークよ、教えてくれ。$a_i$ 番目のオークは常に真実を語るか？」という形式の質問をしました。しかし、彼は得られた回答からどう結論を出せばよいか分からなくなってしまいました。

イワン皇子が質問から結論を導き出すのを手伝ってください。各オークについて、常に真実を語るか、常に嘘をつくか、あるいは情報が不十分であるかを判定してください。もしバーバ・ヤガーがイワン皇子を騙しており、入力データに合致するオークの構成が存在しない場合は、単一の整数 $-2$ を出力してください。

入力

$1$ 行目には、オークの本数と、そのうち常に真実を語るオークの本数をそれぞれ表す $2$ つの整数 $n$, $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$) が含まれます。

続く $n$ 行のうち $i$ 行目には、$2$ つの整数 $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