叛军有s艘宇宙飞船，每艘都有一定的攻击力a.

他们想派遣他们的宇宙飞船去摧毁帝国的基地，偷走足够的黄金和物资。

帝国有b个基地，每个基地都有一定的防御能力d，和一定量的黄金g.

飞船可以攻击所有防御力小于或等于其攻击力的基地。

如果一艘飞船攻击了一个基地，它会偷走基地里所有的黄金。

叛军还没决定先派出哪艘飞船，于是向博士求助。他们想知道，对于每艘宇宙飞船，它能窃取的黄金的最大数量。

第一行包含整数s和b (1≤s,b≤10⁵），分别表示宇宙飞船的数量和基地的数量。

第二行包含s个整数a (0≤a≤10⁹），表示每个宇宙飞船的攻击力。

接下来的b行，每行包含两个整数d,g (0≤d≤10⁹, 0≤g≤10⁴），分别表示每个基地的防御力和黄金。

打印s个整数，每艘宇宙飞船能偷到的黄金的最大数量，与输入中给出的宇宙飞船的顺序相同。

第一艘飞船只能攻击第一基地。 

第二艘飞船可以攻击第一和第三基地。 

第三艘飞船可以攻击第一、二、三基地。

赵晨晨2021