你是 Psycho Cookmaster，一个被恶魔附身的灵魂，却对食物有着出奇谦逊的热爱。今晚是你全新餐厅——“Food to Die For”（为之死而无憾的美食）的开业之夜，这里已经预订满了 $n$ 只精灵！第 $i$ 只精灵当前的虚弱值（sickness）为 $s_i$。

这 $n$ 只精灵今晚将依次前来享用他们难忘的晚餐。为了避免出现意外，你提前准备了 $m$ 道菜品，每道菜品都有一个健康指数 $h_i$ 和一个美味度指数 $t_i$。如果精灵 $x$ 吃下了菜品 $y$ 且满足 $h_y < s_x$，那么精灵 $x$ 就会死亡。

今晚是展现你邪恶一面的绝佳机会；毕竟，你是一个变态之神！因此，你希望分配这 $m$ 道菜品，使得吃下它们的精灵都会死亡，但你同时也想向他们表达一些歉意以及你对美味盛宴的热爱。因此，你决定给那些即将死去的精灵提供美味的食物，让他们死而无憾。而那些不会死去的精灵将被取消预订，并获得一张精美的优惠券，以便改日再来你的餐厅消费。

换句话说，你的目标是将部分菜品分配给部分精灵（可能不分配，且每只精灵最多吃一盘菜，每盘菜最多分配给一只精灵），使得因吃下菜品而死亡的精灵所吃菜品的美味度之和尽可能大。

唯一的问题是，你不知道所谓的“善良之神”何时会干预你的计划。因此，已知这 $n$ 只精灵将按顺序来到餐厅，你必须对于所有的 $1 \le i \le n$，独立地为前 $i$ 只精灵解决这个问题。

输入格式

输入的第一行包含两个正整数 $n$ 和 $m$（$1 \le n, m \le 200\,000$），分别表示精灵的数量和菜品的数量。

输入的第二行包含 $n$ 个正整数 $s_1, s_2, \dots, s_n$（$1 \le s_i \le 10^9$），表示每只精灵的虚弱值。

接下来的 $m$ 行中，第 $i$ 行包含两个整数 $h_i$ 和 $t_i$（$1 \le h_i, t_i \le 10^9$），分别表示第 $i$ 道菜品的健康指数和美味度指数。

输出格式

输出 $n$ 个整数，其中第 $i$ 个整数应当是针对前 $i$ 只精灵的答案。

样例

输入样例 1

5 3
8 10 5 1 6
6 10
5 12
9 4

输出样例 1

12 22 22 22 26