Bơm Dầu

Điểm số: 1

Giới hạn thời gian: 1s

Giới hạn bộ nhớ: 512 MB

Người đăng: ICTU

Nhà máy dầu A đã mời một kỹ sư E đến lắp một dàn máy bơm dầu tự động hiện đại bậc nhất Đông Nam Á. Với n thùng dầu rỗng trên băng chuyền, mỗi 1 giây, một đầu bơm sẽ bơm được từ thùng dầu thứ i đến thùng dầu thứ j (1 <= i <= j <= n), mỗi thùng k lít dầu. Hỏi sau m giây, các thùng dầu chứa bao nhiêu lít dầu.

Đầu vào

            Dòng một là một số t (1 <= t <= 1000) là số lượng test.

            Tại t test, dòng một gồm 2 số n, m. (1 <= n <= 105, 1 <= m <= 105). Trong m dòng tiếp theo sẽ gồm 3 số i, j, k thể hiện cho đầu bơm đã bơm k lít dầu cho các thùng dầu từ i đến j. (1 <= i <= j <= n, 1 <= k <= 105).

            Tổng các n trong t test không vượt quá 105.

Đầu ra

Gồm t dòng, mỗi dòng sẽ bao gồm n số là số lượng dầu của các thùng sau khi bơm xong.

Ví dụ

Đầu vào

Đầu ra

1

3 1

1 3 5

5 5 5

 

2

4 3

1 2 5

3 4 2

1 3 1

4 2

1 3 3

2 3 5

6 6 3 2

3 8 8 0