Hôm nay, các học sinh tại trường mầm non SuperKids được học về phép cộng. Nhằm mục đích vừa giải trí, vừa luyện tập, thầy giáo bày ra một trò chơi như sau:

"Thầy có một dãy \(a\) gồm \(n\) số. Ban đầu, các số này đều bằng \(0\). Sau đó, thầy sẽ lần lượt chọn ra những đoạn con liên tiếp. Yêu cầu các em phải cộng vào số đầu tiên của đoạn con đó lên \(1\) đơn vị, số thứ hai lên \(2\) đơn vị, số thứ ba lên \(3\) đơn vị, \(\dots\), cứ như thế cho tới khi hết đoạn con. Sau khi cộng xong, mỗi bạn phải đưa cho thầy dãy \(a\) mà bạn ấy đã tính được. Nếu giống với đáp án của thầy thì các bạn ấy sẽ được thưởng 5 phiếu bé ngoan mỗi tháng cho cả học kì."

Quả không hổ danh là những thần đồng với IQ 400 và tốc độ tính toán lên tới 5GHz, bài tập trên chỉ là chuyện nhỏ với các bạn mầm non. Hóa ra người bị đánh đố lại là bạn, những người đang đọc đề bài này.

Bạn hãy in ra dãy \(a\) mà mình đã tính được nhé.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(m\), lần lượt là độ dài dãy và số lần cộng vào các đoạn con.
• \(m\) dòng tiếp theo, mỗi dòng chứa hai số \(l,r\) là vị trí đầu & cuối của đoạn con cần được cộng vào.

Output

• Một dòng duy nhất chứa dãy \(a\) gồm \(n\) số

Constraints

• \(1 \le n,m \le 2 \times 10^5\)
• \(1 \le l \le r \le n\)

Example

Sample input

5 3
1 3
2 4
1 5

Sample output

2 5 8 7 5

Note

Dãy số \(a\) sau mỗi thao tác cộng:

• \(1,2,3,0,0\)
• \(1,3, 5, 3, 0\)
• \(2, 5, 8, 7, 5\)