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.util.*;
import java.lang.*;
import java.io.*;
public class Codechef
{       static PrintWriter out=new PrintWriter(System.out);static FastScanner in = new FastScanner(System.in);static class FastScanner {BufferedReader br;StringTokenizer stok;FastScanner(InputStream is) {br = new BufferedReader(new InputStreamReader(is));}
        String next() throws IOException {while (stok == null || !stok.hasMoreTokens()) {String s = br.readLine();if (s == null) {return null;}
                stok = new StringTokenizer(s);}return stok.nextToken();}
        int ni() throws IOException {return Integer.parseInt(next());}long nl() throws IOException {return Long.parseLong(next());}double nd() throws IOException {return Double.parseDouble(next());}char nc() throws IOException {return (char) (br.read());}String ns() throws IOException {return br.readLine();}
        int[] nia(int n) throws IOException{int a[] = new int[n];for (int i = 0; i < n; i++)a[i] = ni();return a;}long[] nla(int n) throws IOException {long a[] = new long[n];for (int i = 0; i < n; i++)a[i] = nl();return a;}
        double[] nda(int n)throws IOException {double a[] = new double[n];for (int i = 0; i < n; i++)a[i] = nd();return a;}int [][] imat(int n,int m) throws IOException{int mat[][]=new int[n][m];for(int i=0;i<n;i++){for(int j=0;j<m;j++)mat[i][j]=ni();}return mat;}
    }
	static long mod=Long.MAX_VALUE;
	public static void main (String[] args) throws java.lang.Exception
	{   int i,j;
	    HashMap<Integer,Integer> hm=new HashMap<Integer,Integer>();
		/*  if(hm.containsKey(z))
		        hm.put(z,hm.get(z)+1);
		    else
		        hm.put(z,1);
		 */       
        ArrayList<Integer> arr=new ArrayList<Integer>();
        HashSet<Integer> set=new HashSet<Integer>();
        PriorityQueue<Integer> pq=new PriorityQueue<Integer>();
        
        int n=in.ni();
        int m=in.ni();
        long a[]=in.nla(n);
        pair p[]=new pair[m];
        for(i=0;i<m;i++)
            p[i]=new pair(in.ni(),in.ni());
        Arrays.sort(p);    
        //for(i=0;i<m;i++)
        //    out.println(p[i].x+" "+p[i].y);
        long temp[]=new long[m];
        long ans[]=new long[m];
        for(i=0;i<m;i++)
            temp[i]=p[i].x;
        ans[0]=p[0].y;
        for(i=1;i<m;i++)
            ans[i]=ans[i-1]+p[i].y;        
        for(i=0;i<n;i++)
        {   
            int z=binarySearch(temp,m,a[i]);
            if(z==-1)
                out.print("0 ");
            else
                out.print(ans[z]+" ");    
        }
        
        
        
        out.close();
	}
	static class pair implements Comparable<pair>{
		long x, y;
		public pair(long x, long y){this.x = x; this.y = y;}
		@Override
		public int compareTo(pair arg0) 
		{   if(x<arg0.x)    return -1;
		    else if(x==arg0.x)
		    {   if(y<arg0.y)    return -1;
		        else if(y>arg0.y)   return 1;
		        else    return 0;
		    }
		    else    return 1;
		}
	}
	static long gcd(long a,long b)
	{   if(b==0)
	        return a;
	    return gcd(b,a%b);    
	}
	static long exponent(long a,long n)
	{   long ans=1;
	    while(n!=0)
	    {   if(n%2==1)
	            ans=(ans*a)%mod;
	       a=(a*a)%mod;
	       n=n>>1;
	    }
	    return ans;
	}
	static int binarySearch(long arr[], int n, long key) 
    {   int left = 0, right = n; 
        int mid = 0; 
        while (left < right) { 
            mid = (right + left) >> 1; 
            // Check if key is present in array 
            if (arr[mid] == key) { 
                // If duplicates are present it returns 
                // the position of last element 
                while (mid + 1 < n && arr[mid + 1] == key) 
                    mid++; 
                break; 
            } 
            // If key is smaller, ignore right half 
            else if (arr[mid] > key) 
                right = mid; 
            // If key is greater, ignore left half 
            else
                left = mid + 1; 
        } 
        // If key is not found in array then it will be 
        // before mid 
        while (mid > -1 && arr[mid] > key) 
            mid--; 
  
        // Return mid + 1 because of 0-based indexing 
        // of array 
        return mid ; 
    } 
	 
    static void merge(int arr[], int l, int m, int r) {   
        int n1 = m - l + 1; int n2 = r - m; int L[] = new int [n1]; int R[] = new int [n2]; 
        
        for (int i=0; i<n1; ++i) L[i] = arr[l + i]; for (int j=0; j<n2; ++j) R[j] = arr[m + 1+ j]; int i = 0, j = 0; int k = l; while (i < n1 && j < n2) {   if (L[i] <= R[j]) {   arr[k] = L[i]; i++; } else{   arr[k] = R[j]; j++; } k++; } while (i < n1){   arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j];   j++;     k++; } 
    } 
    static void Sort(int arr[], int l, int r) {if (l < r) {   int m = (l+r)/2; Sort(arr, l, m); Sort(arr , m+1, r); merge(arr, l, m, r); } } 
    
    static void sort(int a[])
    {Sort(a,0,a.length-1);}
}