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 r_i và p_i, yêu cầu thực hiện p_i 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 r_i. 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.

• Dòng đầu tiên gồm hai số nguyên N, Q (1 \leq N, Q \leq 105) - 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 r_i và p_i (1 \leq r_i \leq N, 1 \leq p_i \leq 9 \times 10^8) - mô tả truy vấn thứ i.

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.

Subtask:

• Subtask 1 (10% số điểm): N, Q \leq 2000, p_i = 1
• Subtask 2 (25% số điểm): N, Q \leq 2000
• Subtask 3 (25% số điểm): p_i = 1
• Subtask 4 (40% số điểm): Không có ràng buộc gì thêm

• Trong ví dụ thứ nhất:
  • Sau khi thực hiện truy vấn 1, dãy A trở thành: [4, 4, 3, 0, 0, 0, 0, 0]
  • Sau khi thực hiện truy vấn 2, dãy A trở thành: [4, 4, 3, 2, 2, 1, 1, 1]
  • Sau khi thực hiện truy vấn 3, dãy A trở thành: [4, 4, 3, 3, 3, 2, 1, 1]
• Trong ví dụ thứ hai:
  • Sau khi thực hiện truy vấn 1, dãy A trở thành: [1, 0, 0, 0, 0]
  • Sau khi thực hiện truy vấn 2, dãy A trở thành: [1, 1, 0, 0, 0]
  • Sau khi thực hiện truy vấn 3, dãy A trở thành: [1, 1, 1, 0, 0]
  • Sau khi thực hiện truy vấn 4, dãy A trở thành: [2, 1, 1, 0, 0]
  • Sau khi thực hiện truy vấn 5, dãy A trở thành: [2, 2, 1, 0, 0]