Nhà máy dầu ~A~ vừa mời một kỹ sư ~E~ đến lắp đặt một dàn máy bơm dầu tự động hiện đại bậc nhất Đông Nam Á. Trên băng chuyền có ~n~ thùng dầu rỗng, được đánh số từ ~1~ đến ~n~. Mỗi giây, một đầu bơm sẽ thực hiện bơm dầu vào một đoạn liên tiếp các thùng, từ thùng dầu thứ i đến thùng dầu thứ j ~(1 ≤ i ≤ j ≤ n)~, mỗi thùng trong đoạn này sẽ được bơm thêm ~k~ lít dầu.

Sau ~m~ giây bơm, hãy xác định lượng dầu có trong từng thùng.

Dữ liệu vào:

Dòng đầu tiên chứa một số nguyên t — số lượng test case.

Với mỗi test case:

Dòng đầu tiên chứa hai số nguyên n và m — số thùng dầu và số giây bơm.

Tiếp theo là m dòng, mỗi dòng chứa ba số nguyên i, j, k, nghĩa là trong giây này, máy bơm sẽ bơm thêm k lít dầu vào tất cả các thùng từ i đến j.

Dữ liệu ra:

Với mỗi test case, in ra một dòng gồm ~n~ số nguyên, trong đó số thứ ~x~ là lượng dầu có trong thùng dầu thứ ~x~ sau khi thực hiện xong tất cả các lần bơm.

Ví dụ :

Input:

1
3 1
1 3 5

Output:

5 5 5