Contest Duration: - (local time) (180 minutes)
F - Sushi /

Time Limit: 3 sec / Memory Limit: 256 MB

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}$.

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:

 1st Operation 2nd Operation 3rd Operation Customer 1 Customer 2 Customer 3 Customer 4 Customer 5 Customer 6 Customer 7 Customer 8 Customer 9 3 2 2 2 2 0 0 0 0 3 2 2 2 2 2 1 1 0 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

### 問題文

$N$人の客が寿司屋にいます。それぞれの客には番号が付けられており, $1,2,3,…,N$ となっています。

$i$ 回目の操作では, 次のことをします。
1. 板前は, 客 $1, 2, 3, \dots, a_i$ の中で食べた寿司の皿数が最も少ない人を選びます。そのような人が複数いる場合は, その中で番号が最も少ない人を選びます。
2. 板前が選んだ人に寿司を渡します。
3. 2. で選ばれた人は, 寿司を食べます。
4. 1. ～ 3. のを $b_i$ 回繰り返します。

$Q$ 回すべての操作が終わったあと, それぞれの人が食べた寿司の皿数を計算してください。

### 入力

$N \ Q$ $a_1 \ b_1$ $a_2 \ b_2$ $： \ ：$ $a_Q \ b_Q$
• 1行目に, 客の数 $N$ と, 操作の回数 $Q$ が空白区切りで与えられる。
• 2行目から $N$ 行にわたって, 整数 $a_i$, $b_i$ が空白区切りで与えられる。

### 出力

• $N$ 行にわたって出力する。
• $i$ 行目には, 客 $i$ が食べた寿司の皿数を出力しなさい。

### 制約

• $3 \le N, Q \le 100,000$
• $1 \le a_i \le N$
• $1 \le b_i \le 10^{12}$
• 最終的な値は, どれも $2 \times 10^{13}$ を超えない。

### 小課題

• $N, Q \le 100$
• $b_i = 1$

• $N, Q \le 100$
• $b_i \le 10^{12}$

• $N, Q \le 100,000$
• $b_i = 1$

• 追加の制約はない。

### 入力例1

9 3
5 11
8 4
4 7


### 出力例1

4
4
4
4
2
2
1
1
0


 1回目の操作 2回目の操作 3回目の操作 客1 客2 客3 客4 客5 客6 客7 客8 客9 3 2 2 2 2 0 0 0 0 3 2 2 2 2 2 1 1 0 4 4 4 4 2 2 1 1 0

### 入力例2

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


### 出力例2

10
10
5
5
4
2


### 入力例3

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


### 出力例3

2
2
1
1
0


### 入力例4

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


### 出力例4

223
123
77
50
33
21
12
7
3
1