F - Sushi Editorial /

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

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
配点： $1200$ 点

問題文

$N$人の客が寿司屋にいます。それぞれの客には番号が付けられており, $1,2,3,…,N$ となっています。
板前は, 次の操作を $Q$ 回します。

$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}$ を超えない。

小課題

小課題1 [ $60$ 点 ]
  • $N, Q \le 100$
  • $b_i = 1$
小課題2 [ $400$ 点 ]
  • $N, Q \le 100$
  • $b_i \le 10^{12}$
小課題3 [ $240$ 点 ]
  • $N, Q \le 100,000$
  • $b_i = 1$
小課題4 [ $500$ 点 ]
  • 追加の制約はない。

入力例1

9 3
5 11
8 4
4 7

出力例1

4
4
4
4
2
2
1
1
0
客が食べた寿司の皿数の変化は以下の通りです。

客1 客2 客3 客4 客5 客6 客7 客8 客9
1回目の操作 3 2 2 2 2 0 0 0 0
2回目の操作 3 2 2 2 2 2 1 1 0
3回目の操作 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
問題作成者 : E869120