GoncaSoft 是一家在全球拥有 $n$ 个数据中心的互联网公司。每个数据中心都有一定数量的可用机器。出于安全和冗余的考虑，每项服务都需要同时运行一个或多个副本。每个副本在独立的数据中心运行，并需要一定数量的机器来支撑。对于给定的某项服务，其所有副本所需的机器数量相同。

当 GoncaSoft 计划启动一项需要 $c$ 个副本、每个副本需要 $m$ 台机器的新服务 $i$ 时，它会根据当前可用机器数量将数据中心按降序排列，然后使用前 $c$ 个数据中心，并在每个数据中心中各使用 $m$ 台机器。

请计算在按给定顺序启动 $s$ 项服务后，各数据中心剩余的可用机器数量。

输入格式

第一行包含两个空格分隔的整数 $n$ 和 $s$，分别表示 GoncaSoft 拥有的数据中心数量和想要启动的新服务数量。

第二行包含 $n$ 个空格分隔的整数，表示在启动任何服务之前，每个数据中心拥有的可用机器数量。

接下来的 $s$ 行描述了将要启动的服务：第 $i$ 行包含两个空格分隔的整数 $m_i$ 和 $c_i$，分别表示第 $i$ 项服务所需的机器数量和副本数量。

输出格式

输出一行，包含 $n$ 个按降序排列的空格分隔的整数，表示所有服务启动后各数据中心剩余的可用机器数量。

数据范围

• $1 \le n \le 100\,000$ 且 $0 \le s \le 5\,000$。
• 每个数据中心初始时最多有 $10^9$ 台机器。
• 对于每项服务 $i$（$1 \le i \le s$），满足 $1 \le m_i \le 10^9$。
• 对于每项服务 $i$（$1 \le i \le s$），满足 $1 \le c_i \le n$。
• 数据中心始终有足够的机器供新服务使用。

子任务

• 子任务 1（12 分）：$n \le 100$，$s = 0$。
• 子任务 2（12 分）：$n \le 100$，$s \le 10$。
• 子任务 3（9 分）：$n \le 50\,000$，$s \le 100$。
• 子任务 4（26 分）：每个数据中心初始时最多有 $1\,000$ 台机器。
• 子任务 5（18 分）：对于所有 $1$ 到 $s$ 的服务，$c_i = 1$。
• 子任务 6（23 分）：无其他限制。

样例

输入 1

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

输出 1

11 10 10 9 8

说明