Tăng kiểu bậc thang

Cho dãy số \(a\) gồm \(n\) số nguyên đánh số từ \(1\) đến \(n\). Ban đầu dãy \(a\) gồm toàn số \(0\). Cho \(q\) truy vấn, mỗi truy vấn được cho dưới dạng hai số nguyên \(i\) và \(k\) : tăng \(a_{i}\) lên \(k\) đơn vị, \(a_{i+1}\) lên \(k - 1\) đơn vị,... \(a_{i+k−1}\) lên \(1\) đơn vị.

Hãy in ra dãy \(a\) sau khi thực hiện \(q\) truy vấn này.

Input

Dòng đầu chứa hai số nguyên dương \(n\) và \(q\) \((n, q \leq 5 \times 10^5)\).

\(q\) dòng tiếp theo, mỗi dòng tương ứng với một truy vấn là hai số nguyên \(i\) và \(k\) \((1 \leq i \leq n; 1 \leq k \leq n-i+1)\).

Output

Một dòng duy nhất là dãy \(a_{1},a_{2},...,a_{n}\) sau khi thực hiện xong \(q\) truy vấn.

Example

7 5
5 2
1 6
1 6
7 1
7 1

12 10 8 6 6 3 2 

Scoring

\(30\%\) số test tương ứng với \(30\%\) số điểm có \(n, q \leq 1000\).

\(30\%\) số test tương ứng với \(30\%\) số điểm mọi \(k\) trong \(q\) truy vấn bằng nhau.

\(40\%\) số test tương ứng với \(30\%\) số điểm còn lại không có ràng buộc gì thêm.