AT_s8pc_3_f 寿司

[problemUrl]: https://atcoder.jp/contests/s8pc-3/tasks/s8pc_3_f $ 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 $ 点 \] - 追加の制約はない。 ### 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