Informacije

Ο Mirko βαρέθηκε, γι' αυτό πήρε ένα κομμάτι χαρτί και έγραψε μια ακολουθία ~A~ μήκους ~N~, η οποία περιέχει κάθε θετικό ακέραιο μεταξύ του 1 και του ~N~, κλειστό διάστημα, ακριβώς μία φορά. Μετά από αυτό, πήρε ένα άλλο κομμάτι χαρτί και έγραψε ~M~ περιγραφές της ακολουθίας ~A~.
Κάθε περιγραφή έχει μία από τις ακόλουθες μορφές:

1 x y v – ο μεγαλύτερος αριθμός στις θέσεις μεταξύ ~x~ και ~y~ (κλειστό διάστημα) ισούται με ~v~
2 x y v – ο μικρότερος αριθμός στις θέσεις μεταξύ ~x~ και ~y~ (κλειστό διάστημα) ισούται με ~v~

Μετά ήρθε ο Slavko, είδε και έκλεψε το πρώτο χαρτί. Ο Mirko είναι απελπισμένος και σας ζήτησε να βρείτε κάποια σειρά που να ταιριάζει με τις περιγραφές, όχι απαραίτητα ίση με την αρχική σειρά.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει δύο θετικούς ακέραιους, ~N\;(1 \le N \le 200)~, το μήκος της ακολουθίας και ~M\;(0 \le M \le 40\,000)~, τον αριθμό των περιγραφών.
Κάθε μία από τις ακόλουθες ~M~ γραμμές περιέχει μια περιγραφή, όπως αναφέρεται παραπάνω.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει μια ακολουθία ~N~ θετικών ακεραίων, διαχωρισμένων στο διάστημα (που ταιριάζουν με τις περιγραφές και περιέχουν όλους τους θετικούς ακέραιους από το 1 έως το ~N~) ή -1 εάν δεν υπάρχει τέτοια ακολουθία.

Παραδείγματα

input

3 2
1 1 1 1
2 2 2 2

output

1 2 3

input

4 2
1 1 1 1
2 3 4 1

output

-1

input

5 2
1 2 3 3
2 4 5 4

output

1 2 3 4 5