最高分数:$1200$ 积分
一名寿司厨师为顾客进行了 $Q$ 的操作。
第 $i$ 个操作如下:
请计算每位顾客吃过的寿司的份数。
问题陈述
餐厅里有 $N$ 顾客。每个客户的编号为 $1$ 到 $N$。一名寿司厨师为顾客进行了 $Q$ 的操作。
第 $i$ 个操作如下:
- 寿司厨师选择吃寿司菜数最少的顾客,即顾客$1,2,3,\dots,a_i$。如果有多个顾客的菜品数量最少,他就选择数量最少的顾客。
- 他把一盘寿司放在选定的座位上。
- 选择专业的顾客吃这个寿司。
- 重复 1-3 $b_i$ 次。
请计算每位顾客吃过的寿司的份数。
输入
输入由标准输入按以下格式给出:$N \ Q$ $a_1\b_1$ $a_2\b_2$ $ : \ : $ $a_Q \ b_Q$
输出
- 您必须打印 $N$ 行。
- 第 $i$ 行应包含顾客 $i (1 \le i \le N)$ 吃过的寿司菜肴数量。
约束
- $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$
- $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 | 客户 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