题目描述

$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$ が食べた寿司の皿数を出力しなさい。

题目大意

寿司店里来了$N$个客人。每个客人都有一个号码：$1,\ 2,\ 3,\ \dots,\ a_i$ 。在桌前，将以下操作设为 Q：

桌前，客人们（客人$1,\ 2,\ 3,\ \dots,\ a_i$ ）选择他们中寿司盘数最少的人（客人）吃下一盘寿司，注意，如果有多个这样的人，我们选择其中编号最低的那个人吃下那盘寿司。

重复$b_i$ 次，完成所有操作后，计算每个人吃的寿司盘数。

（因为翻译者不知道‘板’是什么意思，故译为‘桌子’。）

9 3
5 11
8 4
4 7

4
4
4
4
2
2
1
1
0

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

10
10
5
5
4
2

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

2
2
1
1
0

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

223
123
77
50
33
21
12
7
3
1

提示

制約

• $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$ 点 ]

• 追加の制約はない。

Sample Explanation 1

客が食べた寿司の皿数の変化は以下の通りです。 客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