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 \leq i \leq j \leq 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 \leq t \leq 1000)\) là số lượng test.

• Tại \(t\) test, dòng một gồm 2 số \(n, m\). \((1 \leq n \leq 10^5, 1 \leq m \leq 10^5)\). 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 \leq i \leq j \leq n, 1 \leq k \leq 10^5)\).

• Tổng các \(n\) trong t test không vượt quá \(10_5\).

Đầ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ụ

Input 1

1
3 1
1 3 5

Output 1

5 5 5

Input 2

2
4 3
1 2 5
3 4 2
1 3 1
4 2
1 3 3
2 3 5

Output 2

6 6 3 2
3 8 8 0