该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

魔法学院的地下室里排列着一排用于储存魔力的水晶。由于年代久远，这些水晶的传导线路出现了异常：当某个水晶的能量充满时，它无法再接收新的能量，多余的能量会自动“溢出”并流向右侧的下一个未充满的水晶。

题目描述

实验台上有 $N$ 个水晶排成一排，编号从 $1$ 到 $N$。 每个水晶都有一个固定的能量上限 $L_i$。初始时，所有水晶的当前能量均为 $0$。

为了测试水晶的性能，大法师会进行 $M$ 次充能操作。 每次操作由两个参数 $(idx, val)$ 描述，表示法师尝试向第 $idx$ 号水晶注入 $val$ 点能量。

能量流动的规则如下：

1. 首先检查第 $idx$ 号水晶。
2. 如果该水晶未充满（当前能量 $< L_{idx}$），能量会被该水晶吸收。
   • 如果吸收 $val$ 后，总能量仍然 $\leq L_{idx}$，则操作结束。
   • 如果吸收 $val$ 后，总能量超过了 $L_{idx}$，该水晶会变满（能量变为 $L_{idx}$），剩余的能量（$val - \text{吸收量}$）会变为“溢出能量”，继续流向第 $idx + 1$ 号水晶。
3. 如果该水晶已充满（当前能量 $= L_{idx}$），它将完全不吸收能量，所有的 $val$ 能量直接流向第 $idx + 1$ 号水晶。
4. 能量会一直向右流动，直到被某个未充满的水晶完全吸收，或者流过了第 $N$ 号水晶（此时多余能量消散在空气中）。

你的任务： 在所有 $M$ 次操作完成后，输出每个水晶最终的能量值。

输入格式

第一行包含两个整数 $N$ 和 $M$，表示水晶数量和操作次数。 第二行包含 $N$ 个整数 $L_1, L_2, \dots, L_N$，表示每个水晶的能量上限。 接下来 $M$ 行，每行包含两个整数 $idx, val$，表示一次从第 $idx$ 号水晶开始的充能操作，注入能量为 $val$。

输出格式

输出一行 $N$ 个整数，表示操作结束后，第 $1$ 到第 $N$ 号水晶的当前能量值。

输入输出样例 #1

输入 #1

5 4
10 5 10 10 10
1 8
1 5
2 6
4 12

输出 #1

10 5 4 10 2

说明/提示

样例解释 初始上限：[10, 5, 10, 10, 10]，当前：[0, 0, 0, 0, 0]

1. 1 8：向 1 号注入 8。1 号容量 10，未满。

   • 1 号变为 8。剩余 0。
   • 当前：[8, 0, 0, 0, 0]

2. 1 5：向 1 号注入 5。1 号当前 8，容量 10。

   • 1 号吸收 2 变为 10（满）。剩余 3 流向 2 号。
   • 2 号当前 0，容量 5。吸收 3 变为 3。剩余 0。
   • 当前：[10, 3, 0, 0, 0]

3. 2 6：向 2 号注入 6。2 号当前 3，容量 5。

   • 2 号吸收 2 变为 5（满）。剩余 4 流向 3 号。
   • 3 号当前 0，容量 10。吸收 4 变为 4。
   • 当前：[10, 5, 4, 0, 0]

4. 4 12：向 4 号注入 12。4 号当前 0，容量 10。

   • 4 号吸收 10 变为 10（满）。剩余 2 流向 5 号。
   • 5 号当前 0，容量 10。吸收 2 变为 2。
   • 当前：[10, 5, 4, 10, 2]

数据范围

• $1 \leq N, M \leq 2 \times 10^5$
• $1 \leq L_i \leq 10^9$
• $1 \leq val \leq 10^9$