Trong một lớp học lập trình có N học sinh xếp thành một hàng ngang, được đánh số từ 1 đến N.

Ban đầu, điểm tích lũy của tất cả học sinh đều bằng 0.

Trong buổi học, Thầy giáo thực hiện Q lần tặng điểm thưởng.

Mỗi lần, Thầy chọn một nhóm các bạn ngồi liên tiếp từ vị trí L đến vị trí R và cộng thêm 1 điểm cho mỗi bạn trong nhóm đó.

Hãy tính số điểm cuối cùng của tất cả học sinh sau khi thực hiện xong các lần tặng điểm.

Dữ liệu vào — TANGDIEM.INP

Dòng đầu tiên chứa hai số nguyên N và Q

(1 ≤ N, Q ≤ 10⁵)

Q dòng tiếp theo, mỗi dòng chứa hai số nguyên L và R

(1 ≤ L ≤ R ≤ N)

Dữ liệu ra — TANGDIEM.OUT

In ra một dòng gồm N số nguyên, là điểm của các học sinh từ vị trí 1 đến N.

Các số cách nhau đúng một dấu cách.

Ví dụ

Input
5 3
1 3
2 5
3 3

Output
1 2 3 1 1

Giải thích

Sau lần 1: 1 1 1 0 0

Sau lần 2: 1 2 2 1 1

Sau lần 3: 1 2 3 1 1