Problem Description

There are $ N $ customers in a sushi restaurant. Each customer is assigned a number, $1, 2, 3, \ldots, N$.
The chef performs the following operation $ Q $ times:

In the $ i $-th operation, the chef does the following:

1. The chef selects the customer among $1, 2, 3, \ldots, a_i$ who has eaten the fewest plates of sushi. If there are multiple such customers, the chef selects the one with the smallest number.
2. The chef gives a plate of sushi to the selected customer.
3. The selected customer eats the sushi.
4. Steps 1 to 3 are repeated $ b_i $ times.

After all $ Q $ operations are completed, calculate the number of plates of sushi each customer has eaten.

Input Format

The input is given from the standard input in the following format:

$N\ Q$ $a_1\ b_1$ $a_2\ b_2$ $\ldots$ $a_Q\ b_Q$

• The first line contains the number of customers $ N $ and the number of operations $ Q $, separated by spaces.
• The next $ Q $ lines contain integers $ a_i $ and $ b_i $, separated by spaces.

Output Format

Output should follow the standard output in the following format:

• Output $ N $ lines.
• The $ i $-th line should contain the number of plates of sushi eaten by customer $ i $.

Sample Input and Output

Sample Input #1

9 3
5 11
8 4
4 7

Sample Output #1

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

Notes/Hints

Constraints

• $3 \le N, Q \le 100,000$
• $1 \le a_i \le N$
• $1 \le b_i \le 10^{12}$
• The final values will 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 \]
- No additional constraints.

见题面 Input 部分

见题面 Output 部分