Max Score: $1200$ Points

Problem statement

There are $N$ customers in a restaurant. Each customer is numbered $1$ through $N$.
A sushi chef carried out $Q$ operations for customers.

The $i$-th operation is follows:
  1. The sushi chef chooses a customer whose number of dishes of sushi eaten is minimum, in customer $1, 2, 3, \dots, a_i$. If there are multiple customers who are minimum numbers of dishes, he selects the minimum-numbered customers.
  2. He puts a dish of sushi on the selected seats.
  3. A customer who have selected for professional eats this sushi.
  4. Repeat 1-3, $b_i$ times.

Please calculate the number of dishes of sushi that have been eaten by each customer.

Input

The input is given from Standard Input in the following format:
$N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $ ： \ ： $ $a_Q \ b_Q$

Output

  • You have to print $N$ lines.
  • The $i$-th line should contain the number of dishes of sushi had eaten for customer $i (1 \le i \le N)$.

Constraints

  • $3 \le N, Q \le 100,000$
  • $1 \le a_i \le N$
  • $1 \le b_i \le 10^{12}$
  • Any final results do not exceed $2 \times 10^{13}$.

Subtasks

Subtask 1 [ $60$ points ]
  • $N, Q \le 100$
  • $b_i = 1$
Subtask 2 [ $400$ points ]
  • $N, Q \le 100$
  • $b_i \le 10^{12}$
Subtask 3 [ $240$ points ]
  • $N, Q \le 100,000$
  • $b_i = 1$
Subtask 4 [ $500$ points ]
  • There are no additional constraints.

Sample Input 1

9 3
5 11
8 4
4 7

Sample Output 1

4
4
4
4
2
2
1
1
0
The change of the number of dishes of sushi have eaten is following:

Customer 1 Customer 2 Customer 3 Customer 4 Customer 5 Customer 6 Customer 7 Customer 8 Customer 9
1st Operation 3 2 2 2 2 0 0 0 0
2nd Operation 3 2 2 2 2 2 1 1 0
3rd Operation 4 4 4 4 2 2 1 1 0

Sample Input 2

6 6
3 5
6 11
1 6
4 7
5 2
2 5

Sample Output 2

10
10
5
5
4
2

Sample Input 3

5 6
1 1
2 1
3 1
1 1
5 1
3 1

Sample Output 3

2
2
1
1
0

Sample Input 4

10 10
10 10
9 20
8 30
7 40
6 50
5 60
4 70
3 80
2 90
1 100

Sample Output 4

223
123
77
50
33
21
12
7
3
1
Writer: E869120