Cho một dãy A gồm N phần tử. Ban đầu, giá trị của các phần tử đều bằng 0. Có Q truy vấn, truy vấn thứ i được mô tả bởi hai số nguyên ri và pi, yêu cầu thực hiện pi lần các thao tác sau:

• Chọn phần tử có giá trị nhỏ nhất trong các phần tử có vị trí từ 1 đến ri. Nếu có nhiều phần tử có cùng giá trị nhỏ nhất, chọn phần tử có vị trí nhỏ nhất trong số chúng.

• Tăng giá trị của phần tử được chọn thêm 1.

Hãy cho biết giá trị các phần tử trong dãy A sau khi thực hiện Q truy vấn trên.

Input:

• Dòng đầu tiên gồm hai số nguyên N, Q (1 ≤ N, Q ≤ 100000) - số phần tử của dãy A và số truy vấn cần thực hiện.

• Q dòng tiếp theo, mỗi dòng gồm hai số nguyên ri và pi (1 ≤ ri ≤ N, 1 ≤ pi ≤ 9 ∗100000000) - mô tả truy vấn thứ i.

Output:

• In ra N số nguyên lần lượt là giá trị các phần tử trong dãy A sau khi thực hiện Q truy vấn.

Sample Input

8 3

3 11 

8 7

6 3

Sample Output

4 4 3 3 3 2 1 1

Sample Input

5 5 

5 1 

4 1 

3 1 

2 1 

2 1

Sample Output

2 2 1 0 0

Ràng buộc

• Subtask 1 (10% số điểm): N, Q ≤ 2000, pi = 1 

• Subtask 2 (25% số điểm): N, Q ≤ 2000

• Subtask 3 (25% số điểm): pi = 1

• Subtask 4 (40% số điểm): Không có ràng buộc gì thêm