Cho mảng ~A~ gồm ~n~ số ~0~ và ~q~ truy vấn dạng (~l,r~), tăng các phần tử ~A_l,A_l+1,…,A_r~ lên ~1~ đơn vị.

Input

• Dòng đầu tiên gồm 2 số nguyên ~n~,~q~.
• ~q~ dòng tiếp theo mỗi dòng gồm 2 số nguyên ~l~,~r~.

Output

• In ra mảng ~A~ sau ~q~ truy vấn.

Điều kiện

~1 ≤ n,q ≤ 10^5~.~1≤l,r≤n~.

Ví dụ

Input:

4 3
1 3
2 4
1 2

Output:

2 3 2 1

Cho dãy số nguyên ~A~ gồm ~n~ phần tử ~a_1,a_2,…,a_n~. Ban đầu tất cả các phần tử đều mang giá trị 0. Bạn cần thực hiện ~Q~ thao tác cập nhật trên dãy số này, với mỗi thao tác, cần tăng đoạn gồm các phần tử từ vị trí ~l~ tới vị trí ~r~ của dãy số thêm ~k~ đơn vị.

Yêu cầu: Tìm giá trị lớn nhất của dãy số sau khi thực hiện xong cả ~Q~ thao tác cập nhật?

Input:

Dòng đầu tiên chứa hai số nguyên dương

• ~n~ và ~Q~ - độ dài dãy số và số lượng thao tác cập nhật.
• ~Q~ dòng tiếp theo, mỗi dòng chứa ba số nguyên dương ~l~,~r~,~k~ thể hiện một thao tác cập nhật.

Ràng buộc:

• ~1 ≤ n,Q ≤ 10^5~.~1 ≤ k ≤ 10^9~.

• In ra giá trị lớn nhất của dãy số sau Q thao tác cập nhật.

Input:

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

Output:

17

Cho dãy số ~A~ gồm ~n~ phần tử, các phần tử được đánh số từ 1 tới ~n~. Ban đầu tất cả các phần tử trong mảng đều mang giá trị ~0~. Người ta tiến hành điều chỉnh dãy số bằng ~Q~ thao tác có dạng [~l,r~]; với mỗi thao tác, phần tử ~a_l~ sẽ tăng thêm 1 đơn vị, phần tử ~a_{l+1}~ tăng thêm 2 đơn vị,..., ~a_r~ tăng thêm ~r-l+1~ đơn vị.

Yêu cầu: Hãy đưa ra dãy số sau khi tất cả các thao tác được thực hiện?

Input:

• Dòng đầu chứa hai số nguyên n và Q - số nguyên l,r – biểu thị một thao tác điều chỉnh.

Ràng buộc:

• ~1≤n≤10^6~. ~1≤Q≤2×10^5~. ~1≤l≤r≤n~.

Output:

• Đưa ra ~n~ số nguyên là các phần tử của dãy số sau khi thực hiện ~Q~ thao tác cập nhật, các số phân tách nhau bởi dấu cách.

Input:

5 3
1 2 
2 5 
3 4

Output:

1 3 3 5 4