T386422 【第 13 周】B

西西艾弗公司有 $n$ 个数据中心，第 $i$ 个数据中心有 $a_i$ 台设备。 现在有 $s$ 条需求，第 $i$ 条需求是： - 选择当前空闲设备数最多的 $c_i$ 个数据中心，对这些每个数据中心占用 $m_i$ 台设备用于计算。 数据保证这 $s$ 条需求总能被分配到机器。 请求出在满足这 $s$ 个需求后，每个数据中心剩余的机器数量。

第一行：$n,s$。 第二行：$a_1, a_2, \dots, a_n$。 接下来 $s$ 行：$m_i, c_i$。

输出一行**降序排列**的 $n$ 个整数，表示每个数据中心剩余的机器数。

对于全部数据，$1\le n\le 10^5$，$0\le s\le 5\times 10^3$，$0\le a_i\le 10^9$，$1\le m_i\le 10^9$，$1\le c_i\le n$，保证任意时刻任意数据中心可用机器数非负。