Iwan Zarewitsch ist auf der Suche nach dem Tod von Koschtschei dem Unsterblichen in einen magischen Hain gekommen. Laut Baba Jaga gibt es dort $n$ weise Eichen, unter denen genau $k$ Eichen immer die Wahrheit sagen, während die anderen immer lügen.

Um herauszufinden, wohin er als Nächstes gehen soll, muss der Zarewitsch den weiteren Weg von den Eichen erfahren. Er muss jedoch äußerst vorsichtig sein, denn wenn er dem Rat einer der lügenden Eichen folgt, gerät er in einen Sumpf, in dem ihm das einäugige Licho auflauern würde.

Um herauszufinden, welchen Eichen er vertrauen kann, hat Iwan jeder Eiche eine Frage in der folgenden Form gestellt: „Eiche Nummer $i$, sag mir, sagt die Eiche Nummer $a_i$ immer die Wahrheit?“ Allerdings weiß er nicht, was er mit den erhaltenen Antworten anfangen soll.

Hilf Iwan Zarewitsch, Schlüsse aus den Fragen zu ziehen. Bestimme für jede Eiche, ob sie immer die Wahrheit sagt, immer lügt oder ob die Informationen unzureichend sind. Falls Baba Jaga Iwan Zarewitsch getäuscht hat und es keine mögliche Konfiguration von Eichen gibt, die mit den Eingabedaten übereinstimmt, gib eine einzige Zahl $-2$ aus.

Eingabe

Die erste Zeile enthält zwei ganze Zahlen $n$ und $k$ ($1 \le n \le 5 \cdot 10^5$, $0 \le k \le n$), welche die Anzahl der Eichen bzw. die Anzahl der Eichen, die immer die Wahrheit sagen, bezeichnen.

Die $i$-te der nächsten $n$ Zeilen enthält zwei ganze Zahlen $a_i$ und $b_i$ ($1 \le a_i \le n$, $0 \le b_i \le 1$), was bedeutet, dass die Eiche Nummer $i$ gefragt wurde, ob die Eiche Nummer $a_i$ immer die Wahrheit sagt, und die Antwort „Ja“ lautete, falls $b_i = 1$ ist, oder andernfalls „Nein“.

Ausgabe

Falls die Eingabedaten widersprüchlich sind, gib eine einzige ganze Zahl $-2$ aus.

Andernfalls gib $n$ ganze Zahlen $t_1, t_2, \dots, t_n$ aus: die Schlussfolgerungen darüber, ob die Eichen die Wahrheit sagen. Sie können die folgenden Werte annehmen:

• $t_i = 1$, falls die Eiche Nummer $i$ immer die Wahrheit sagt;
• $t_i = -1$, falls die Eiche Nummer $i$ immer lügt;
• $t_i = 0$, falls es anhand der verfügbaren Daten unmöglich ist zu bestimmen, ob die Eiche Nummer $i$ immer lügt oder immer die Wahrheit sagt.

Beispiele

Eingabe 1

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

Ausgabe 1

0 0 -1 1 1 1

Eingabe 2

3 1
2 0
3 0
1 0

Ausgabe 2

-2