Heidi 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 ≤ s, b ≤ 10^5), the number of spaceships and the number of bases, respectively.

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

The next b lines contain integers d, g (0 ≤ d ≤ 10^9, 0 ≤ g ≤ 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.
import java.io.*;
import java.util.*;
import java.math.*;
import java.lang.*;
 
import static java.lang.Math.*;

public class Vader implements Runnable 
{
    static class InputReader 
    {
        private InputStream stream;
        private byte[] buf = new byte[1024];
        private int curChar;
        private int numChars;
        private SpaceCharFilter filter;
        private BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        public InputReader(InputStream stream) 
        {
            this.stream = stream;
        }
        
        public int read()
        {
            if (numChars==-1) 
                throw new InputMismatchException();
            
            if (curChar >= numChars) 
            {
                curChar = 0;
                try
                {
                    numChars = stream.read(buf);
                }
                catch (IOException e)
                {
                    throw new InputMismatchException();
                }
                
                if(numChars <= 0)               
                    return -1;
            }
            return buf[curChar++];
        }
     
        public String nextLine()
        {
            String str = "";
            try
            {
                str = br.readLine();
            }
            catch (IOException e)
            {
                e.printStackTrace();
            }
            return str;
        }
        public int nextInt() 
        {
            int c = read();
            
            while(isSpaceChar(c)) 
                c = read();
            
            int sgn = 1;
        
            if (c == '-') 
            {
                sgn = -1;
                c = read();
            }
            
            int res = 0;
            do
            {
                if(c<'0'||c>'9') 
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c)); 
        
            return res * sgn;
        }
        
        public long nextLong() 
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            long res = 0;
            
            do 
            {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            while (!isSpaceChar(c));
                return res * sgn;
        }
        
        public double nextDouble() 
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            int sgn = 1;
            if (c == '-')
            {
                sgn = -1;
                c = read();
            }
            double res = 0;
            while (!isSpaceChar(c) && c != '.') {
                if (c == 'e' || c == 'E')
                    return res * Math.pow(10, nextInt());
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = read();
            }
            if (c == '.') 
            {
                c = read();
                double m = 1;
                while (!isSpaceChar(c))
                {
                    if (c == 'e' || c == 'E')
                        return res * Math.pow(10, nextInt());
                    if (c < '0' || c > '9')
                        throw new InputMismatchException();
                    m /= 10;
                    res += (c - '0') * m;
                    c = read();
                }
            }
            return res * sgn;
        }
    
        public String readString() 
        {
            int c = read();
            while (isSpaceChar(c))
                c = read();
            StringBuilder res = new StringBuilder();
            do 
            {
                res.appendCodePoint(c);
                c = read();
            } 
            while (!isSpaceChar(c));
            
            return res.toString();
        }
     
        public boolean isSpaceChar(int c) 
        {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }
     
        public String next()
        {
            return readString();
        }
        
        public interface SpaceCharFilter
        {
            public boolean isSpaceChar(int ch);
        }
    }
	
	
	// if modulo is required set value accordingly
	public static long[][] matrixMultiply2dL(long t[][],long m[][])
	{
		long res[][]= new long[t.length][m[0].length];
		
		for(int i=0;i<t.length;i++)
		{
			for(int j=0;j<m[0].length;j++)
			{
				res[i][j]=0;
				for(int k=0;k<t[0].length;k++)
				{
					res[i][j]+=t[i][k]+m[k][j];
				}
			}
		}
		
		return res;
	}
	
	static long combination(long n,long r)
	{
		long ans=1;
		for(long i=0;i<r;i++)
		{
			ans=(ans*(n-i))/(i+1);
		}
		return ans;
	}
	
	static long binarySearch(Base base[], int l, int r, int a)
	{
		if(a<base[l].dsum) return (long)0;
		
		if(l==r) return base[l].gold;
		
		int m=(l+r+1)/2;
		
		if(base[m].dsum>a) return binarySearch(base,l,m-1,a);
		
		return binarySearch(base,m,r,a);
	}
	
	
    public static void main(String args[]) throws Exception 
    {
        new Thread(null, new Vader(),"Vader",1<<27).start();
    }
	// **just change the name of class from Main to reuquired**
    public void run()
    {
        InputReader sc = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);
		
		int s=sc.nextInt();
		int b=sc.nextInt();
		
		ship a[]= new ship[s];
		for(int i=0;i<s;++i)
		{
			int attack=sc.nextInt();
			a[i]= new ship(attack,i);
		}
		
		
		Base base[]= new Base[b];
		for(int i=0;i<b;++i)
		{
			int d=sc.nextInt();
			long g=sc.nextInt();
			base[i]= new Base(d,g);
		}
		
		Arrays.sort(base, new sortByDefence());
		
		base[0].dsum=base[0].defence;
		
		
		
		Arrays.sort(a, new sortByAttack());
		
		int j=0;
		long ans=0;
		for(int i=0;i<s;++i)
		{
			while(j<b && base[j].defence<=a[i].attack)
			{
				ans+=base[j].gold;
				j++;
			}
			a[i].answer=ans;
			
			/*int l=0,r=s-1;
			int mid=(l+r)>>1;
			int index=-1;
			
			while(l<r)
			{
				
				mid = (int)Math.ceil((double)(l+r)/2);
				System.out.println("l:"+l+" r:"+r+" mid:"+mid);
				if(a[i]>base[mid].dsum)
				{
					r=mid-1;
				}
				else
				{
					l=mid;
				}
			}
			
			if(base[mid].dsum>=a[i]) index=l;
			
			if(index!=1) ans[i]=base[l].gold;*/
		}
		
		Arrays.sort(a, new sortByIndex());
		
		for(int i=0;i<s;++i) w.print(a[i].answer+" ");
		
		
        System.out.flush();
        w.close();
    }
}

class Base
{
	int defence;
	long gold;
	long dsum;
	
	Base(int a, long b)
	{
		defence=a;
		gold=b;
	}
}

class sortByDefence implements Comparator<Base>
{
	public int compare(Base b1, Base b2)
	{
		return b1.defence-b2.defence;
	}
}

class ship{
	int attack;
	int index;
	long answer;
	
	ship(int a, int in)
	{
		attack=a;
		index=in;
	}
}

class sortByAttack implements Comparator<ship>
{
	public int compare(ship s1, ship s2)
	{
		return s1.attack-s2.attack;
	}
}

class sortByIndex implements Comparator<ship>
{
	public int compare(ship s1, ship s2)
	{
		return s1.index-s2.index;
	}
}