Mirko cảm thấy buồn chán nên lấy một tờ giấy viết ra một dãy ~A~ có độ dài ~N~, chứa mỗi số nguyên dương từ ~1~ đến ~N~, bao gồm đúng một lần. Sau đó, anh ta lấy một mảnh giấy khác và viết ra ~M~ mô tả về dãy ~A~.

Mỗi mô tả có một trong các định dạng sau:

~1~ ~x~ ~y~ ~v~ – số lớn nhất ở các vị trí giữa x và y (bao gồm ~x~ và ~y~) bằng ~v~

~2~ ~x~ ~y~ ~v~ – số nhỏ nhất ở vị trí giữa ~x~ và ~y~ (bao gồm ~x~ và ~y~) bằng ~v~

Sau đó Slavko đến, nhìn thấy và lấy trộm tờ giấy đầu tiên. Mirko tuyệt vọng và đã yêu cầu bạn tìm một số trình tự phù hợp với mô tả, không nhất thiết phải giống với trình tự ban đầu.

Input

• Dòng đầu tiên của đầu vào chứa hai số nguyên dương ~N~ ~(1 \le N \le 200)~, độ dài của chuỗi và ~M~ ~(0 \le M \le 40 000)~, số lượng mô tả.
• Mỗi dòng trong số ~M~ dòng tiếp theo chứa một mô tả như mô tả ở trên.

Output

• Dòng đầu tiên và duy nhất của đầu ra phải chứa một chuỗi gồm ~N~ số nguyên dương được phân tách bằng dấu cách (khớp với mô tả và chứa tất cả các số nguyên dương từ ~1~ đến ~N~) hoặc ~-1~ nếu không tồn tại chuỗi đó.

Sample Input 1

3 2
1 1 1 1
2 2 2 2

Sample Output 1

1 2 3

Sample Input 2

4 2
1 1 1 1
2 3 4 1

Sample Output 2

-1

Sample Input 3

5 2
1 2 3 3
2 4 5 4

Sample Output 3

1 2 3 4 5