题目描述

贡卡软件（贡软）是一家互联网公司，经营许多服务，在全球有 $n$ 个数据中心。每个数据中心都有一些可用的机器。出于安全和冗余的原因，每个服务都有一个或多个副本同时运行。每个副本在一个不同的数据中心运行，并需要一些机器来运行。一个服务的所有副本需要相同数量的机器。

当贡软计划推出一项需要 $c_i$ 个副本，每个副本在 $m$ 台机器上运行的新的服务 $i$ 时，它按照当前可用机器对数据中心降序排序，然后在前 $c_i$ 个数据中心各使用 $m$ 台机器。

请求出在推出 $s$ 个服务后，每个数据中心剩余的机器数量。

输入格式

第一行两个整数 $n,s$，表示数据中心数和服务数。

第二行 $n$ 个整数 $a_i$，表示每个数据中心初始可用机器数。

接下来 $s$ 行，每行两个整数 $m_i,c_i$，表示需要的机器数、副本数。

输出格式

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

5 4
20 12 10 15 18
3 4
4 1
1 3
4 2

11 10 10 9 8

提示

样例解释

数据范围

对于全部数据，$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$，保证任意时刻任意数据中心可用机器数非负。

• 子任务一（$12$ 分）：$n\le 100$，$s=0$。
• 子任务二（$12$ 分）：$n\le 100$，$s\le 10$。
• 子任务三（$9$ 分）：$n\le 5\times 10^4$，$s\le 100$。
• 子任务四（$26$ 分）：$a_i\le 10^3$。
• 子任务五（$18$ 分）：$c_i=1$。
• 子任务六（$23$ 分）：无特殊限制。