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