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