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 \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.

Difficulty: interview

Starter code:

Solutions:
# -*- coding: utf-8 -*-
import sys
from operator import itemgetter
from fractions import gcd
from math import ceil, floor
from copy import deepcopy
from itertools import accumulate
from collections import Counter
import math
from functools import reduce
from bisect import bisect_right
sys.setrecursionlimit(200000)
input = sys.stdin.readline
def ii(): return int(input())
def mi(): return map(int, input().rstrip().split())
def lmi(): return list(map(int, input().rstrip().split()))
def li(): return list(input().rstrip())
def debug(x): print("debug: ", x, file=sys.stderr)
# template


class BIT:
    def __init__(self, x, d=0):
        if isinstance(x, int):
            self.size = x
            self.tree = [d for _ in range(self.size + 1)]
        elif isinstance(x, list):
            self.size = len(x)
            self.tree = [d for _ in range(self.size + 1)]
            self.build(x)
        else:
            raise TypeError

    def build(self, arr):
        if isinstance(arr, list):
            raise TypeError
        for num, x in enumerate(arr):
            self.add0(num, x)

    def sum(self, i):
        s = self.tree[0]
        while i > 0:
            s += self.tree[i]
            i -= (i & -i)
        return s

    def add(self, i, a):
        if(i == 0):
            return
        while (i <= self.size):
            self.tree[i] += a
            i += (i & -i)

    def bisect_left(self, w):
        if w <= 0:
            return 0
        x = 0
        r = 1
        while (r < self.size):
            r <<= 1
        k = r
        while (k > 0):
            if x + k <= self.size and self.tree[x + k] < w:
                w -= self.tree[x + k]
                x += k
            k >>= 1
        return x + 1

    def query(self, l, r):
        return self.sum(r - 1) - self.sum(l - 1)

    def sum0(self, i):
        return self.sum(i + 1)

    def add0(self, i, a):
        self.add(i + 1, a)

    def query0(self, l, r):
        return self.sum(r) - self.sum(l)

    def __getitem__(self, item):
        _tmp = item.indices(self.size + 1)
        return [self.sum(i) - self.sum(i - 1) for i in range(_tmp[0], _tmp[1], _tmp[2])]

    def __str__(self):
        return str(self[1:self.size + 1])

# END CUT HERE


def main():
    s, b = mi()
    a = lmi()
    d = []
    g = []
    for i in range(b):
        _d, _g = mi()
        d.append(_d)
        g.append(_g)
    tmp = [(d[i], g[i]) for i in range(b)]
    tmp.sort(key=lambda x: x[0])
    d.sort()
    # print(tmp)
    # print(d)
    bit = BIT(b)
    for i in range(b):
        bit.add0(i, tmp[i][1])
    for i in range(s):
        tmp = bisect_right(d, a[i])
        # print(tmp)
        print(bit.sum(tmp), end=" ")
    print()


def __starting_point():
    main()

__starting_point()

s, b = map(int, input().split())
a = list(map(int, input().split()))
for i in range(s):
    a[i] = [a[i], i, None]
bases = []
for i in range(b):
    d, g = map(int, input().split())
    bases.append((d, g))
bases.sort()
a.sort()
j = 0
count = 0
for i in range(b):
    while j < s and a[j][0] < bases[i][0]:
        a[j][2] = count
        j += 1
    if j == s:
        break
    count += bases[i][1]
    if i == b-1:
        if j < s and a[j][0] >= bases[i][0]:
            r = j
            for j in range(r, s):
                a[j][2] = count
a.sort(key=lambda x: x[1])
a = [x[2] for x in a]
print(*a)

s, b = map(int, input().split())
a = list(map(int,input().split()))
d = [ list(map(int,input().split())) for _ in range(b) ]
d.sort(key=lambda f: f[0])
for i in range(1,b):
    d[ i ][ 1 ] += d[ i - 1 ][ 1 ]
d = { k: v for k, v in d }
k = list(d.keys())
from bisect import bisect_right as br
for ship in a:
    key = br(k, ship)
    ans = d[ k[ key - 1 ] ] if key else 0
    print( ans, end = " " )


from sys import stdin
from bisect import bisect_right as br
input=stdin.readline
s,b=map(int,input().split())
sp=list(map(int,input().split()))
bp=[]
for i in range(b):
    bp.append(list(map(int,input().split())))
c=[0]*b
bp.sort()
for i in range(1,b):
    bp[i][1]+=bp[i-1][1]
an=[0]*s
for i in range(s):
    m=br(bp,[sp[i]])
    if m<b and bp[m][0]>sp[i]:
        m-=1
    elif m==b:
        m-=1
    if m>=0:
        an[i]=bp[m][1]
    else:
        an[i]=0
print(*an)

from bisect import bisect_right
from operator import itemgetter
s, b = list(map(int, input().split()))
A = list(map(int, input().split()))
DG = [list(map(int, input().split())) for _ in range(b)]
DG.sort(key=itemgetter(0))
cumG = [0]
for d, g in DG:
  cumG.append(cumG[-1]+g)
D = list(map(itemgetter(0), DG))
Ans = []
for a in A:
  idx = bisect_right(D, a)
  Ans.append(cumG[idx])
print(*Ans)



arr = input()

N,B = [int(x) for x in arr.split(' ')]

arr = input()
A = [int(x) for x in arr.split(' ')]


base = []

for i in range(B):
    arr = input()
    H,G = [int(x) for x in arr.split(' ')]
    
    base.append([H,G])
    
base.sort()

idx = sorted(range(len(A)), key=lambda k: A[k])
A.sort()
#print(base)
s = 0
k = -1
ans = [0]*(N)
for i in range(N):
    attack = A[i]
    while k<B-1:
        if base[k+1][0]<=attack:
            s += base[k+1][1]
            k += 1
        else:
            break
    
    #print(attack,s)
    ans[idx[i]] = s
    
for num in ans:
    print(num,end=' ')
        

s_cnt, b_cnt = list(map(int, input().split()))
a = list(map(int, input().split()))
b = []
for i in range(b_cnt):
	d, g = list(map(int, input().split()))
	b.append((d, g))
b.sort()
idx = [i for i in range(s_cnt)]
idx.sort(key = lambda i : a[i])
ans = [0]*s_cnt
s, j = 0, 0
for i in range(s_cnt):
	while j < b_cnt and b[j][0] <= a[idx[i]]:
		s += b[j][1]
		j += 1
	ans[idx[i]] = s
print(*ans)


s, b = list(map(int, input().split(' ')))

ships = list(map(int, input().split(' ')))
bases = [tuple(map(int, input().split(' '))) for _ in range(b)]

bases.sort()

gold = [0] * (b + 1)
for i in range(b):
    gold[i + 1] = gold[i] + bases[i][1]

# ships.sort()

def find(x, inf, sup):
    while inf < sup:
        mid = (inf + sup) // 2
        if bases[mid][0] <= x:
            inf = mid + 1
        else:
            sup = mid

    return sup - 1

attacks = [0] * s
for (i, ship) in enumerate(ships):
    # print("{} can attack {} bases".format(i, find(ship, 0, b) + 1))
    attacks[i] = gold[find(ship, 0, b) + 1]

print(' '.join(map(str, attacks)))


n,m = list(map(int,input().split()))
d = list(map(int,input().split()))
l = []
for i in range(n):
    l.append([d[i],i])
l.sort()
l2 = []
for i in range(m):
    a,b = list(map(int, input().split()))
    l2.append([a,b])
l2.sort()
s = 0
j = 0
r = [0]*n
for i in range(n):
    while(j<m and l2[j][0]<=l[i][0]):
        s+=l2[j][1]
        j+=1
    r[l[i][1]]=s
print(" ".join(map(str,r)))


string_ = input()
s, b = string_.split()
s = int(s)
b = int(b)
string_ = input()
arr = string_.split()
arr = [int(x) for x in arr]

base = []
for i in range(b):
    string_ = input()
    d, g = string_.split()
    d = int(d)
    g = int(g)
    base.append((d, g))

base.sort()
pref = []
for i in range(b):
    if i == 0:
        pref.append(base[i][1])
    else:
        pref.append(pref[i-1]+base[i][1])


for i in range(s):
    ans = 0
    lef, r = 0, b
    while r-lef > 1:
        mid = int((r+lef)/2)
        if base[mid][0] > arr[i]:
            r = mid
        else:
            lef = mid
    if lef == 0:
        if base[lef][0] <= arr[i]:
            ans += pref[lef]
    else:
        ans += pref[lef]
    print(ans, end=" ")




def bins(a,k,n1):
 l,h=0,n1-1
 while(l<=h):
  m=(l+h)//2
  if(l==h):
   return m
  elif(a[m][0]<=k):
   l=m+1
  else:
   h=m-1
 return l
n,n1=map(int,input().split())
sp=list(map(int,input().split()))
de=[]
s=0
gosum=[]
for i in range(n1):
 d,g=map(int,input().split())
 de+=[[d,g]]
de.sort()
for i in range(n1):
 s+=de[i][1]
 gosum+=[s]
for i in range(n):
 ind=bins(de,sp[i],n1)
 if(de[ind][0]>sp[i] and ind!=0):
  print(gosum[ind-1],end=" ")
 elif(ind==0 and de[ind][0]>sp[i]):
  print(0,end=" ")
 else:
  print(gosum[ind],end=" ")
 


import bisect
from collections import OrderedDict
a,b=list(map(int,input().split()))
aray=list(map(int,input().split()))
dic={}
ans=OrderedDict()
max=0
min=55555555555
summ=0
arr=[]
answer=[]
for x in range(b):
    c,d=list(map(int,input().split()))
    if c not in dic:
       dic[c]=[d]
       arr.append(c)
    else:
        dic[c].append(d)
    if c>max:
        max=c
    if c<min:
        min=c
arr.sort()
for it in arr:
    summ+=sum(dic[it])
    ans[it]=summ
for it in aray:
    if it in ans:
        answer.append(ans[it])
    else:
        if it<min:
            answer.append(0)
        elif it>=max:
            answer.append(ans[max])
        else:
            ind = bisect.bisect_left(arr,it)
            answer.append(ans[arr[ind-1]])
print(*answer)

#!/usr/bin/env python

import bisect

def cummulative_sum(arr):
    #array of tuples
    acc = 0
    newarr = [[0,0]]
    for defence, gold in arr:
        acc += gold
        if newarr[-1][0] == defence:
            newarr[-1][1] += gold
        else:
            newarr.append([defence, acc])
    return newarr

spaceship_count, base_count = list(map(int, input().strip().split()))
spaceships = list(map(int, input().strip().split()))
bases = []
answer = []

for _ in range(base_count):
    d, g = list(map(int, input().strip().split()))
    bases.append((d, g))

bases.sort()
bases_prefixes = cummulative_sum(bases)
#print(bases)
#print(bases_prefixes)

for spaceship in spaceships:
    i = bisect.bisect_right(bases_prefixes, [spaceship, 10**15])
    #print(f'The spaceship does {spaceship} damage, so it can attack base {i} and collect {bases_prefixes[i-1][1]} gold.')
    answer.append(bases_prefixes[i-1][1])

print(*answer)


n, m = list(map(int, input().split()))
a = sorted([(int(x), y) for x, y in zip(input().split(), list(range(n)))])
b = []
for _ in range(m):
    b.append(list(map(int, input().split())))
b = sorted(b)
p1 = 0
p2 = 0
s = 0
ans = [0 for _ in range(len(a))]
while p1 < len(a) and p2 < len(b):
    # print(p1, p2)
    if a[p1][0] >= b[p2][0]:
        s += b[p2][1]
        p2 += 1
    else:
        ans[a[p1][1]] = s
        p1 += 1
while p1 < len(a):
    ans[a[p1][1]] = s
    p1 += 1
print(" ".join(list(map(str, ans))))


from sys import stdin

def binary(A,x):
	N = len(A)
	low,hi=0,N
	while low+1 != hi:
		mid = low+((hi-low)>>1)
		if x<A[mid]: hi = mid
		else: low = mid
	return low



def main():
	s,b = stdin.readline().split()
	line = list(map(int,stdin.readline().split()))
	gold = {}
	l = list()
	for _ in range(int(b)):
		d,g = map(int,stdin.readline().split())
		if gold.get(d) == None:
			gold[d] = g
			l.append(d)
		else:
			gold[d]+= g
	l.sort()
	i = 1
	while i < len(l):
		gold[l[i]]+=gold[l[i-1]]
		i+=1
	s = int(s)
	for i in range(s):
		it = binary(l,line[i])
		if(i == s-1):
			if(it == 0 and line[i] < l[it]):
				print(0)
			else:
				print(gold[l[it]])
		else:

			if(it == 0 and line[i] < l[it]):
				print(0,end = " ")
			else:
				print(gold[l[it]],end=" ")
		
main()

import bisect
s,b = map(int,input().split())
a = list(map(int,input().split()))
d = []
for i in range(b):
    d.append(list(map(int,input().split())))
d = sorted(d)
c = []
p = []
for i in range(len(d)):
    c.append(d[i][0])
    p.append(d[i][1])
k = [p[0]]
for i in range(1,len(p)):
    k.append(k[-1]+p[i])
for i in range(len(a)):
    l = bisect.bisect_right(c,a[i])
    if(l==0):
        print(0,end = ' ')
    else:
        print(k[l-1],end = ' ')


s, b = map(int, input().split())
a = list(map(int, input().split()))
d = []
for i in range(b):
    x, y = map(int, input().split())
    d.append((x, y, i + 1))

d.sort()
f = [d[0][1]]
for i in range(1, b):
    f.append(f[-1] + d[i][1])


for i in range(s):
    if d[0][0] > a[i]:
        print(0, end=' ')
    elif d[-1][0] <= a[i]:
        print(f[-1])
    else:
        L = 0
        R = b - 1
        while R - L > 1:
            m = (L + R) // 2
            if d[m][0] <= a[i]:
                L = m
            else:
                R = m
        print(f[L], end=' ')


sb = input().split()
s = int(sb[0])
b = int(sb[1])
a = list(map(int, input().split()))
bases = []

#
# class Base:
#     def __init__(self,str):
#         lst = str.split()
#         d = int(lst[0])
#         g = int(lst[1])
#
#
# for _ in range(b):
#     new_base = Base(input())
#     bases.append(new_base)
#

for _ in range(b):
    dg = list(map(int, input().split()))
    bases.append(dg)

bases.sort(key=lambda a: a[0])

sum_total = 0
for i in bases:
    sum_total += i[1]
    i[1] = sum_total

dg = [*zip(*bases)]

a_sorted = []
a_sorted += a
a_sorted.sort()
g = []
j = 0
for i in a_sorted:
    while j < b:
        if dg[0][j] > i:
            if j > 0:
                g.append(dg[1][j - 1])
            else:
                g.append(0)
            break
        elif j == b - 1:
            g.append(dg[1][j])
            break
        j += 1


for i in a:
    index = a_sorted.index(i)
    print(g[index], end=' ')


"""
NTC here
"""
from sys import setcheckinterval, stdin
setcheckinterval(1000)

# print("Case #{}: {} {}".format(i, n + m, n * m))

iin = lambda: int(stdin.readline())
lin = lambda: list(map(int, stdin.readline().split()))


s,b=lin()
sa=lin()
ba=[lin() for i in range(b)]
ba.sort()
ans=[]
sol=[]
for i,j in ba:
    sol.append(i)
    ans.append(j)
for i in range(1,b):
    ans[i]+=ans[i-1]

from bisect import bisect_right
a=[]
for i in sa:
    x=bisect_right(sol,i)-1
    #print(x,ans)
    if x<0:
        a.append(0)
    else:
        a.append(ans[x])
print(*a)

from sys import stdin, stdout
def rsingle_int():
    return int(stdin.readline().rstrip())
 
def rmult_int():
    return [ int(x) for x in stdin.readline().rstrip().split() ]
 
def r_str():
    return stdin.readline().rstrip()
    
def rsingle_char():
    return stdin.read(1)
 
def main():
    s, b = rmult_int()
    a = rmult_int()

    a_order = a.copy()
    a.sort()

    a_g = {}
    for el in a:
        a_g[el] = 0

    ds = []
    d_g = {}
    for i in range(b):
        d, g = rmult_int()
        if d in d_g:
            d_g[d] += g
        else:
            d_g[d] = g
            ds.append(d)

    ds.sort()
    ds_len = len(ds)
    
    acc = 0
    d_i = 0
    for el in a:
        while d_i < ds_len and ds[d_i] <= el:
            acc += d_g[ds[d_i]]
            d_i += 1
        a_g[el] = acc
    
    out = []
    for el in a_order:
        out.append(int(a_g[el]))
    print(*out)

 
main()

import sys
input = lambda: sys.stdin.readline().strip()
from bisect import bisect_right

s, b = map(int, input().split())
ls = list(map(int, input().split()))
d = {}
for i in range(b):
    a, b  = map(int, input().split())
    try: d[a] += b
    except: d[a] = b
keys = list(d.keys())
keys.sort()
Sum = 0
for i in keys:
    Sum+=d[i]
    d[i] = Sum
for i in ls:
    if bisect_right(keys, i)!=0:
        print(d[keys[bisect_right(keys, i)-1]], end=' ')
    else:
        print(0, end=' ')
print()


# cook your dish here
# cook your dish here
# cook your dish here
s,b=list(map(int,input().split(" ")))
y=list(map(int,input().split()))
c=[]
for i in range(b):
    d,g=list(map(int,input().split(' ')))
    c.append([d,g])

c=sorted(c)

c2=[]
j=s1=0
while j<b:
    s1=s1+c[j][1]
    c2.append(s1)
    j+=1
    
c2.append(0)
count=[]

for i in range(s):
    
    start=0
    end=b-1
    mid=(start+end)//2
    while start<=end:
        if c[mid][0]<=y[i]:
            start=mid+1
            end=end
            mid=(start+end)//2
        else:
            start=start
            end=mid-1
            mid=(start+end)//2
    count.append(c2[end])
    
    
print(*count)

    


from bisect import bisect_right

def find_le(a, x):
    'Find rightmost value less than or equal to x'
    i = bisect_right(a, x)
    if i:
        return i-1
    return -1

s, b = list(map(int,input().split()))
v = []
a = list(map(int,input().split()))
for i in range(b):
    v.append(tuple(map(int,input().split())))
v.sort()
summa = 0
c = []
for i in v:
    summa += i[1]
    c.append(summa)

mas = [i[0] for i in v]

for i in a:
    ind = find_le(mas, i)
    if ind == -1:
        print(0)
    else:
        print(c[ind],end = ' ')

s, b = list(map(int, input().split()))
spaceships = list(map(int, input().split()))

bases = [tuple(map(int, input().split())) for i in range(b)]
bases.sort()

sumbases = [bases[i][1] for i in range(b)]

for i in range(1, b):
    sumbases[i] += sumbases[i - 1]

def search_bases(strength):
    l, r = 0, b
    while l < r:
        m = (l + r)//2
        if bases[m][0] <= strength:
            l = m + 1
        else:
            r = m
    return l - 1

def res(x):
    i = search_bases(x)
    if i < 0:
        return 0
    else: return sumbases[i]

print(*tuple(map(res, spaceships)))