Có một dãy số nguyên không âm ~a_1, a_2,..., a_N~.

Cho ~K~ dữ kiện, mỗi dữ kiện gồm 4 số nguyên ~l, r, X, Y~ cho biết rằng ~X \le \sum_{i=l}^{r} a_i \le Y~.

Đặt ~f(a) = \sum_{i=1}^{N} a_i \times i~.

Tìm dãy số ~a~ thỏa mãn tất cả ~K~ dữ kiện sao cho ~f(a)~ đạt giá trị nhỏ nhất.

Input:

• Dòng đầu tiên chứa 2 số nguyên ~N~, ~K~.
• ~K~ dòng tiếp theo, mỗi dòng chứa 1 dữ kiện gồm 4 số nguyên ~l, r, X, Y~ (~1 \le l \le r \le N~, ~0 \le X \le Y \le 2 \times 10^{10}~).

Output:

• Nếu không tồn tại dãy a thỏa mãn tất cả các dữ kiện, in ra duy nhất ~-1~. Ngược lại in ra ~N~ số nguyên không âm là dãy ~a~ tìm được. Nếu có nhiều đáp án chỉ cần in ra một đáp án bất kỳ.

Sample input 1

7 5
4 5 3 4
2 6 25 25
3 5 7 8
3 5 6 8
2 4 12 13

Sample output 1

0 10 3 0 4 8 0 

Sample input 2

2 2
1 2 1 2
1 1 3 3

Sample output 2

-1

Scoring:

• Subtask 1 (20%): ~1 \le N, K \le 100~.
• Subtask 2 (80%): ~1 \le N, K \le 10000~.