Codeforces celebrates 10 years! We are pleased to announce the crowdfunding-campaign. Congratulate us by the link https://codeforces.com/10years.
×

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

No tag edit access

B1. The Doctor Meets Vader (Easy)

time limit per test

4 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputHeidi and Doctor Who hopped out of the TARDIS and found themselves at EPFL in 2018. They were surrounded by stormtroopers and Darth Vader was approaching. Miraculously, they managed to escape to a nearby rebel base but the Doctor was very confused. Heidi reminded him that last year's HC2 theme was Star Wars. Now he understood, and he's ready to face the evils of the Empire!

The rebels have $$$s$$$ spaceships, each with a certain attacking power $$$a$$$.

They want to send their spaceships to destroy the empire bases and steal enough gold and supplies in order to keep the rebellion alive.

The empire has $$$b$$$ bases, each with a certain defensive power $$$d$$$, and a certain amount of gold $$$g$$$.

A spaceship can attack all the bases which have a defensive power less than or equal to its attacking power.

If a spaceship attacks a base, it steals all the gold in that base.

The rebels are still undecided which spaceship to send out first, so they asked for the Doctor's help. They would like to know, for each spaceship, the maximum amount of gold it can steal.

Input

The first line contains integers $$$s$$$ and $$$b$$$ ($$$1 \leq s, b \leq 10^5$$$), the number of spaceships and the number of bases, respectively.

The second line contains $$$s$$$ integers $$$a$$$ ($$$0 \leq a \leq 10^9$$$), the attacking power of each spaceship.

The next $$$b$$$ lines contain integers $$$d, g$$$ ($$$0 \leq d \leq 10^9$$$, $$$0 \leq g \leq 10^4$$$), the defensive power and the gold of each base, respectively.

Output

Print $$$s$$$ integers, the maximum amount of gold each spaceship can steal, in the same order as the spaceships are given in the input.

Example

Input

5 4 1 3 5 2 4 0 1 4 2 2 8 9 4

Output

1 9 11 9 11

Note

The first spaceship can only attack the first base.

The second spaceship can attack the first and third bases.

The third spaceship can attack the first, second and third bases.

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Feb/24/2020 12:30:08 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|