Hãy xây dựng một dãy ~a~ gồm ~n~ phần tử nguyên dương không vượt quá ~10^9~ thoả mãn ~m~ điều kiện, trong đó điều kiện thứ ~i \ (1 \le i \le m)~ là ~\gcd(a_{l_i}, ..., a_{r_i}) = x_i~.

(Biết rằng ~\gcd(a_l, ..., a_r)~ là số lớn nhất là ước của tất cả các phần tử trong dãy ~a~ có vị trí từ ~l~ đến ~r~).

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, m;~
• Dòng thứ ~i~ trong ~m~ dòng tiếp theo chứa ba số nguyên dương ~l_i, r_i, x_i \ (1 \le l_i \le r_i \le n)~.

Output

Nếu có ít nhất một dãy ~a~ thoả mãn tất cả ~m~ điều kiện thì in ra kết quả là ~n~ số nguyên dương (cách nhau bởi một khoảng trắng) là ~n~ phần tử của dãy ~a~ bất kỳ thoả mãn đề bài. Ngược lại, in ra ~-1~.

Scoring

• Subtask 1 [20%]: ~1 \le n, m \le 2000, \ 1 \le x_i \le 2 \ (1 \le i \le m);~
• Subtask 2 [40%]: ~1 \le n, m \le 2000, \ 1 \le x_i \le 16 \ (1 \le i \le m);~
• Subtask 3 [40%]: ~1 \le n, m \le 2 \times 10^5, \ 1 \le x_i \le 16 \ (1 \le i \le m);~

Examples

Input

2 2
1 2 2
2 2 6

Output

4 6

Chú ý: Trong test này, dãy 2 6 cũng là một dãy đúng.

Input

2 2
1 2 2
2 2 5

Output

-1