Một mùa thi bận rộn và tràn đầy hy vọng lại đến. Năm nay, thầy Tina sẽ dẫn đội tuyển Olympic Tin học của IUH thi Olympic Tin học Sinh viên Việt Nam lần thứ 32 kết hợp cùng với Kỳ thi lập trình sinh viên Quốc tế ICPC Asia Huế sẽ được tổ chức tại Đại học Khoa học Huế. Một vấn đề giống với mọi năm về trước chính là làm sao chụp được một bức hình cả đội tuyển thật đẹp, để làm được như vậy thì một điều quan trọng chính là cách xếp hàng sao cho có tổ chức và đồng đều giữa các thành viên. Biết n vị trí có thể sắp hàng, thầy Tina sẽ đưa ra k yêu cầu cho các sinh viên của mình, yêu cầu thứ i (~ 1 \le i \le k ~) sắp ~c_i~ sinh viên từ vị trí ~p_i, p_i + v_i, p_i + 2 * v_i, ..., p_i + (c_i - 1) * v_i~.

Tuy nhiên vì số lượng sinh viên năm này quá đông và thầy không thể nào nhớ hết những yêu cầu trước đó. Hãy giúp thầy Tina tính xem sau yêu cầu cuối cùng thì có bao nhiêu sinh viên mỗi hàng.

Input

Dòng đầu tiên gồm 2 số n và k (~ 1 \le n, k \le 2*10^5 ~) - số vị trí có thể sắp hàng và số yêu cầu.

Tiếp theo k dòng gồm 3 số ~ c_i, p_i, v_i ~ (~ 1 \le p_i + (c_i - 1) * v_i \le n ~) -

Subtask 1: (30% số điểm) ~ 1 \le n, k \le 2*10^3 ~

Subtask 2: (35% số điểm) ~ 1 \le n, k \le 2*10^5 ~, tất cả các giá trị ~v_i~ giống nhau

Subtask 3: (35% số điểm) Không có hạn chế gì thêm.

Output

In ra kết quả gồm một dòng có n số - số sinh viên trong hàng thứ i

Examples

Input

10 3 
4 2 2 
3 2 3 
5 4 1 

Output

0 2 0 2 2 2 1 3 0 0 

*Giải thích: *

Hàng thứ 1 gồm các sinh viên theo yêu cầu: []

Hàng thứ 2 gồm các sinh viên theo yêu cầu: [1, 2]

Hàng thứ 3 gồm các sinh viên theo yêu cầu: []

Hàng thứ 4 gồm các sinh viên theo yêu cầu: [1, 3]

Hàng thứ 5 gồm các sinh viên theo yêu cầu: [2, 3]

Hàng thứ 6 gồm các sinh viên theo yêu cầu: [1, 3]

Hàng thứ 7 gồm các sinh viên theo yêu cầu: [3]

Hàng thứ 8 gồm các sinh viên theo yêu cầu: [1, 2, 3]

Hàng thứ 9 gồm các sinh viên theo yêu cầu: []

Hàng thứ 10 gồm các sinh viên theo yêu cầu: []