Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(300000)
from heapq import heappush, heappop

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, K = MI()
A = LMI()

if all(a < 0 for a in A) and K % 2 == 1:
    A.sort(reverse=True)
    ans = 1
    for a in A[:K]:
        ans = ans * a % MOD
    print(ans)
    exit(0)

p = []
n = []
for a in A:
    if a < 0:
        heappush(n, a)
    else:
        heappush(p, -a)

ans = 1
cnt = 0
while cnt < K:
    if cnt == K - 1:
        if len(p) > 0:
            ans = ans * -heappop(p) % MOD
        else:
            ans = ans * max(n) % MOD
        cnt += 1
        break
    if len(p) < 1:
        ans = ans * heappop(n) * heappop(n) % MOD
        cnt += 2
    elif len(n) < 2:
        ans = ans * -heappop(p) % MOD
        cnt += 1
    else:
        if len(p) < 2 and -p[0] > n[0] * n[1]:
            ans = ans * -heappop(p) % MOD
            cnt += 1
        elif -p[0] * -p[1] > n[0] * n[1]:
            ans = ans * -heappop(p) % MOD
            cnt += 1
        else:
            ans = ans * heappop(n) * heappop(n) % MOD
            cnt += 2
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(300000)
from heapq import heappush, heappop

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def MI0(): return map(lambda s: int(s) - 1, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
def LMI0(): return list(map(lambda s: int(s) - 1, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


N, K = MI()
A = LMI()

if all(a < 0 for a in A) and K % 2 == 1:
    A.sort(reverse=True)
    ans = 1
    for a in A[:K]:
        ans = ans * a % MOD
    print(ans)
    exit(0)

p = []
n = []
for a in A:
    if a < 0:
        heappush(n, a)
    else:
        heappush(p, -a)

ans = 1
cnt = 0
while cnt < K:
    if cnt == K - 1:
        if len(p) > 0:
            ans = ans * -heappop(p) % MOD
        else:
            ans = ans * max(n) % MOD
        cnt += 1
        break
    if len(p) < 1:
        ans = ans * heappop(n) * heappop(n) % MOD
        cnt += 2
    elif len(n) < 2:
        ans = ans * -heappop(p) % MOD
        cnt += 1
    else:
        p0, p1 = -p[0], -p[1] if len(p) > 1 else 1
        if p0 * p1 > n[0] * n[1]:
            ans = ans * -heappop(p) % MOD
            cnt += 1
        else:
            ans = ans * heappop(n) * heappop(n) % MOD
            cnt += 2
print(ans)
n=int(input())
list=list(map(int,input().split()))
list2=sorted(list)
if n%2==0:
  print(list[n/2]-list[n/2-1])
else:
  print(0)


### FIXED CODE ###

n=int(input())
list=list(map(int,input().split()))
list2=list.sort()

print(list[int(n/2)]-list[int(n/2)-1])
a=int(input())
if a[0]==0 and a[1]==0:
  print('NA')
elif a[2]==0 and a[3]==0:
  print('NA')
elif a[0]>=2:
  print ('YYMM')
elif a[0]>=1 and a[1]>=3:
  print('YYMM')
elif a[2]>=2:
  print ('MMYY')
elif a[2]>=1 and a[3]>=3:
  print('MMYY')


### FIXED CODE ###

S=input()
ab=int(S[0]+S[1])
cd=int(S[2]+S[3])
if ab==0:
  if cd==0:#0000
    print('NA')
  elif cd>=1 and cd<=12:
    #0001~0012
    print('YYMM')
  else: #0013~0099
    print('NA')
elif ab>=1 and ab<=12:
  if cd ==0:
    print('MMYY')
  elif cd>=1 and cd<=12:
    print('AMBIGUOUS')
  else:
    print('MMYY')
else:
  if cd>=1 and cd<=12:
    print('YYMM')
  else:
    print("NA")
from scipy.special import comb

N, M = map(int, input().split())

print(comb(N,2, exact=True) + comb(M,2,exact=True))

### FIXED CODE ###

from scipy.misc import comb

N, M = map(int, input().split())

print(comb(N,2, exact=True) + comb(M,2,exact=True))
x,y,a,b,c=map(int,input().split())
AC=[None]*(a+b+c)
for i in range(a):
  AC[i]=(int(input()),1)
for i in range(a,a+b):
  AC[i]=(int(input()),2)
for i in range(a+b,a+b+c):
  AC[i]=(int(input()),0)
AC.sort(reverse=1)

red=0
green=0
cnt=0
res=0
for a,c in AC:
  if c==0:
    res+=a
    cnt+=1
  elif c==1:
    if red<x:
      res+=a
      red+=1
      cnt+=1
  else:
    if green<y:
      res+=a
      green+=1
      cnt+=1
  if cnt==x+y:
    print(res)
    exit(0)

### FIXED CODE ###

x,y,a,b,c=map(int,input().split())
AC=[]
for a in map(int,input().split()):
  AC.append((a,1))
for a in map(int,input().split()):
  AC.append((a,2))
for a in map(int,input().split()):
  AC.append((a,0))
AC.sort(reverse=1)

red=0
green=0
cnt=0
res=0
for a,c in AC:
  if c==0:
    res+=a
    cnt+=1
  elif c==1:
    if red<x:
      res+=a
      red+=1
      cnt+=1
  else:
    if green<y:
      res+=a
      green+=1
      cnt+=1
  if cnt==x+y:
    print(res)
    exit(0)
N = int(input())
A_list = list(map(int, input().split()))
A_set = sorted(set(A_list), reverse=True)
A_output = []
for i in range(len(A_set)):
    A_output[i] =len(A_list) - len(A_list.remove(A_set[i]))
    
print(A_output.reverse)

### FIXED CODE ###

import collections

N = int(input())
A_list = list(map(int, input().split()))
A_collection = collections.Counter(A_list)

for i in range(N):
    print(A_collection[i+1])
A = imput()
B = imput()

if B % A == 0:
  print(A+B)
else:
  print(A-B)

### FIXED CODE ###

A, B = map(int, input().split())

if B % A == 0:
  print(A+B)
else:
  print(B-A)
#encoding utf-8
from collections import Counter
def main(n,v):
    odd = Counter(v[0::2]).most_common(2) + [(0,0)]
    even = Counter(v[1::2]).most_common(2) + [(0,0)]

    if odd[0][0] == even[0][0]:
        ans = min(n-odd[0][1]-even[1][1],
        n-odd[1][1]-even[0][1])
    else:
        ans = n-odd[0][1]-even[0][1]
    print(ans)


if __name__ == "__main__":
    n = int(input())
    v = list(int(i) for i in input().split())
    main(n,v)

### FIXED CODE ###

#encoding utf-8

n = list(str(input()))

for i in range(len(n)):
    if n[i] == "1":
        n[i] = "to9"
    if n[i] == "9":
        n[i] = "to1"

for i in range(len(n)):
    if n[i] == "to9":
        n[i] = "9"
    elif n[i] == "to1":
        n[i] = "1"

print("".join(n))
N,K,Q = list(map(int, input().split()))

a=[]
nScore=[]
for x in range(Q):
    a.append(input())

for x in range(N):
    nScore.append(K)

for x in range(Q):
    ＃print("----Scores-----")
    
    for y in range(N)#
        if(y+1 !=int(a[x])):
            nScore[y]-=1
            #print("{}: {}".format(y,str(nScore[y])))
        else:
            #print("{}: {} Scored".format(y,str(nScore[y])))

for x in range(N):
    if(nScore[x]<=0):
        print("No")
    else:
        print("Yes")




### FIXED CODE ###

N,K,Q = list(map(int, input().split()))



a=[]
nScore=[]

for x in range(N):
    nScore.append(0)

for x in range(Q):
    nScore[int(input())-1]+=1

# if(K>Q):
#     for x in range(N):
#         print("Yes")

for x in range(N):
    if K-Q+nScore[x]>0:
        print("Yes")
    else:
        print("No")
n,r = int(input()),int(input()) #コンテストの参加回数と表示レーティング

if n >= 10:
  print(r)
else:
  in_rate = r + 100 * (10 - n)
  print(in_rate)


### FIXED CODE ###

n,r=map(int,input().split())

if n >= 10:
  print(r)
else:
	in_rate = r + 100 * (10-n)
	print(in_rate)
def resolve():
    from collections import deque
    d=deque()
    s=list(input())
    d.extend(s)
    #print(d)
    q=int(input())
    Q=[list(map(str,input().split())) for i in range(q)]

    #print(Q)
    rev=0
    for i in range(q):
        if int(Q[i][0])==1:
            if i!=q-1 and int(Q[i+1][0])==2 and int(Q[i+1][1])==1:
                d.append(int(Q[i+1][2]))
                d.reverse()
                i=i+1
            else:
                d.reverse()
            #print(s)
        elif int(Q[i][0])==2:
            if int(Q[i][1])==1:
                d.appendleft(Q[i][2])
                #print(s)
            else:
                d.append(Q[i][2])
                #print(s)
    print(''.join(list(d)))






resolve()

### FIXED CODE ###

def resolve():
    from collections import deque
    d=deque()
    s=list(input())
    d.extend(s)
    #print(d)
    q=int(input())
    Q=[list(map(str,input().split())) for i in range(q)]

    reverse= False
    for i in range(q):
        if int(Q[i][0])==1:
            reverse=not reverse
        elif int(Q[i][0])==2:
            if int(Q[i][1])==1:
                if reverse:
                    d.append(Q[i][2])
                else:
                    d.appendleft(Q[i][2])
                #print(s)
            else:
                if reverse:
                    d.appendleft(Q[i][2])
                else:
                    d.append(Q[i][2])
                #print(s)

    if reverse:
        print(''.join(list(reversed(d))))
    else:
        print(''.join(list(d)))






resolve()
n=int(input())
a=[int(i) for i in input().split()]
x=0
for i in a:
    x^=i

b=[x^i for i in a]
for i in b:
    print(i,end=" ")

### FIXED CODE ###

a = str(input())

if a.isupper():
    print('A')
else:
    print('a')
N,D= map(int, input().split())
X,Y=[map(int, input().split() for i in range(N))]

def f(a,b,c):
  s=0
  for i in range(N)
  　　if (a[i]**2 + b[i]**2)**(1/2)<= c:
     　　s=s+1
  return s
a = X
b = Y
c = D
print(f(a,b,c))

### FIXED CODE ###

N,D = map(int, input().split())
XY = [map(int, input().split()) for _ in range(N)]
X,Y = [list(i) for i in zip(*XY)]

s=0
for i in range (N):
  if X[i]*X[i]+Y[i]*Y[i]<=D*D:
    s=s+1
print(s)
import sys<
N, Y = map(int, raw_input().split())<
for i in range(N + 1):<
    for j in range(N + 1 - i):<
        k = N - i - j<
        if i * 10000 + j * 5000 + k * 1000 == Y:
            print i, j, k<
            sys.exit()<
print "-1 -1 -1"<


### FIXED CODE ###

import sys
N, Y = map(int, raw_input().split())
for i in range(N + 1):
    for j in range(N + 1 - i):
        k = N - i - j
        if i * 10000 + j * 5000 + k * 1000 == Y:
            print i, j, k
            sys.exit()
print "-1 -1 -1"
import fileinput


def frog(stones, jump_range):
    stone_cost = [0]
    for i in range(1, len(stones)):
        stone_cost.append(min(
            stone_cost[i - curr_jmp] + abs(stones[i] - stones[i - curr_jmp])
            for curr_jmp in range(1, min(i, jump_range) + 1)
        ))
    return stone_cost[-1]


inp = fileinput.input()
jump_range = [int(v) for v in inp.readline().split(" ")][1]
stones = [int(v) for v in inp.readline().split(" ")]
print(frog(stones, jump_range))

### FIXED CODE ###

import fileinput
    
def frog(stones):
    stone_cost = [0]
    for i in range(1, len(stones)):
        single_step_cost = abs(stones[i] - stones[i - 1])
        if i == 1:
            stone_cost.append(single_step_cost)
        else:
            double_step_cost = abs(stones[i] - stones[i - 2])
            stone_cost.append(min(single_step_cost + stone_cost[-1], double_step_cost + stone_cost[-2]))
    
    return stone_cost[-1]
    
    
inp = fileinput.input()
inp.readline()
stones = [int(v) for v in inp.readline().split(" ")]
print(frog(stones))
a, b = input().split()
if a * b // 2 == 1:
  print(Odd)
else if:
  print(Even)

### FIXED CODE ###

a,b = map(int,input().split())
 
print("Even" if (a * b) % 2 == 0 else "Odd" )
print("Yes" if input().find("7") >= 0 else "No")
n = int(input()) + 1
a = set(range(0, n))
fs = set(range(0, n, 3))
bs = set(range(0, n, 5))
print(sum(a - fs - bs))

### FIXED CODE ###

n = int(input()) + 1
a = set(range(0, n))
fs = set(range(0, n, 3))
bs = set(range(0, n, 5))
print(sum(a - fs - bs))
x=input()
if x>=1200:
    print("ARC")
else:
    print("ABC")

### FIXED CODE ###

x=int(input())
if x>=1200:
    print("ARC")
else:
    print("ABC")
from collections import Counter
n = int(input())
v = list(map(int, input().split()))
v1, v2 = v[::2], [1::2]
vv1 = Counter(v1).most_common()
vv2 = Counter(v2).most_common()

if len(set(v)) == 1:
    print(n//2)
if vv1[0] != vv2[0]:
    print(n - vv1[0][1] - vv2[0][1])
else:
    print(n - max(vv1[1][1] + vv2[0][1], vv1[0][1] + vv2[1][1]))

### FIXED CODE ###

from collections import Counter
n = int(input())
v = list(map(int, input().split()))
v1, v2 = [], []
for i in range(n):
    if i%2:
        v1.append(v[i])
    else:
        v2.append(v[i])
vv1 = Counter(v1).most_common()
vv2 = Counter(v2).most_common()
if vv1[0] != vv2[0]:
    print(n - vv1[0][1] - vv2[0][1])
else:
    if len(vv1) == len(vv2) == 1:
        print(n - max(vv1[0][1], vv2[0][1]))
    elif len(vv1) == 1 and len(vv2) == 2:
        print(n - vv1[0][1] - vv2[1][1])
    elif len(vv1) == 2 and len(vv2) == 1:
        print(n - vv1[1][1] - vv2[0][1])
    else:
        print(n - max(vv1[1][1] + vv2[0][1], vv1[0][1] + vv2[1][1]))
a=sum(input().split());print(a%2*'IMPOSSIBLE'or a//2)

### FIXED CODE ###

a=sum(map(int,input().split()));print(a%2*'IMPOSSIBLE'or a//2)
N = int(input())
r_N = int(N ** (1 / 2))

li = []
for n in range(1,r_N + 1):
  if N % n == 0:
    a = N // n
    l = max(len(str(a)),len(str(n))))
  	li.append(l)
    
print(min(li))

### FIXED CODE ###

N = int(input())
r_N = int(N ** (1 / 2))
 
li = []
for n in range(1,r_N + 1):
  if N % n == 0:
    a = N // n
    l = max(len(str(a)),len(str(n)))
    li.append(l)
    
print(min(li))
MAX = 10**7
p = [0]*(MAX+1)
t = 1
while 1:
    m, n = map(int, raw_input().split())
    if m == 0:
        break
    i = m
    cnt = 0
    while 1:
        if p[i] != t:
            if cnt == n:
                break
            for j in xrange(i, MAX, i):
                p[j] = t
            cnt += 1
        i += 1
    print i
    t += 1

### FIXED CODE ###

import math
MAX = 7400000
prime = [1]*MAX
prime[0] = prime[1] = 0
res = []
sq = int(math.sqrt(MAX))
for i in xrange(2, sq+1):
    q = len(res)
    if prime[i]:
        res.append(i)
        for j in xrange(i*i, MAX, i):
            prime[j] = 0
    prime[i] = q
for i in xrange(sq+1, MAX):
    q = len(res)
    if prime[i]:
        res.append(i)
    prime[i] = q

def solve(m, n):
    # [m,m*m)
    sat = [0]*(m*m)
    for i in xrange(m, m*m):
        if not sat[i]:
            if n == 0:
                return i
            n -= 1
            for j in xrange(i, m*m, i):
                sat[j] = 1
    # [m*m,\inf)
    idx = prime[m*m]
    return res[idx+n]
while 1:
    m, n = map(int, raw_input().split())
    if m==0:
        break
    print solve(m, n)
N,K=map(int,input().split())
X=list(map(int,input().split()))

cost=10**10

Plus=[i for i in X if i>=0]
Minus=[-i for i in X if i<=0]

if len(Plus)>=K:
    cost=Plus[K-1]
if len(Minus)>=K:
    cost=min(cost,Minus[-K])

i=0
while X[i]<0 and i<=K:
    if i+K-1<N:
        cost=min(cost,X[i+K-1]-X[i]+abs(X[i]))
    i+=1

print(cost)

### FIXED CODE ###

N,K=map(int,input().split())
X=list(map(int,input().split()))
X.sort()
ans=10**10

for i in range(N-K+1):
    R=X[i+K-1]
    L=X[i]
    A=[ans, abs(L)+abs(R-L), abs(R)+abs(R-L)]
    ans=min(A)

print(ans)
import math
MOD = 1000000000+7
X, Y = map(int, input().split())




if ((2*Y-X)%3 != 0) or ((2*X-Y)%3 != 0) or (2*Y-X) < 0 or (2*X-Y) < 0:
    print(0)
else:
    x = (2*Y-X) // 3
    y = (2*X-Y) // 3
    fac_list = [None for _ in range(x+y+2)]
    inv_fac_list = [None for _ in range(x+y+2)]

    fac_list[0] = 1
    for i in range(1, x+y+2):
        print(i)
        fac_list[i] = i * fac_list[i-1] % MOD

    inv_fac_list[x+y+1] = pow(fac_list[x+y+1],(MOD - 2), MOD)
    for i in range(x+y, 0, -1):
        inv_fac_list[i] = inv_fac_list[i+1] * (i+1) % MOD

    print((fac_list[x+y] * inv_fac_list[x] * inv_fac_list[y]) % MOD)

### FIXED CODE ###

import math
MOD = 1000000000+7
X, Y = map(int, input().split())

if ((2*Y-X)%3 != 0) or ((2*X-Y)%3 != 0) or (2*Y-X) < 0 or (2*X-Y) < 0:
    print(0)
elif 2 *Y == X or 2 * X == Y:
    print(1)
else:
    x = (2*Y-X) // 3
    y = (2*X-Y) // 3
    fac_list = [None for _ in range(x+y+2)]
    inv_fac_list = [None for _ in range(x+y+2)]

    fac_list[0] = 1
    for i in range(1, x+y+2):
        fac_list[i] = i * fac_list[i-1] % MOD

    inv_fac_list[x+y+1] = pow(fac_list[x+y+1],(MOD - 2), MOD)
    for i in range(x+y, 0, -1):
        inv_fac_list[i] = inv_fac_list[i+1] * (i+1) % MOD

    print((fac_list[x+y] * inv_fac_list[x] * inv_fac_list[y]) % MOD)
import numpy as np
in1=list(map(int,input().split(" ")))
#print(in1)
#arr=np.zeros((in1[0],in1[1]))
d={}
for i in range(in1[0]):
    #arr[i]=input().split(" ")
    for n,k in enumerate(input().split(" ")):
        d[int(k)]=[i,n]
#print(arr)
Q=int(input())
test=[]
out=[]
route=[]
for k in range(Q):
    ans=0
    start,end=list(map(int,input().split(" ")))
    #place=np.where(arr==start)
    place=d[start]
    #print(start,end)
    while start != end:
        #print("ans",ans)
        #nextplace=np.where(arr==start+in1[2])#[1][0]
        if start in route:
            nextplace=d[start+in1[2]]
        else:
            nextplace=d[start+in1[2]]
            ans1=abs(int(nextplace[0])-int(place[0]))
            ans2=abs(int(nextplace[1])-int(place[1]))
            route[start]=ans1+ans2
        ans+=route[start]
        start+=in1[2]
        place=nextplace

    print(ans)
    #out.append(ans)
#for i in out:
    #print(i)


### FIXED CODE ###

import numpy as np
H, W, D=list(map(int,input().split(" ")))
#print(in1)
#arr=np.zeros((in1[0],in1[1]))
d={}
for i in range(H):
    #arr[i]=input().split(" ")
    for n,k in enumerate(input().split(" ")):
        d[int(k)]=[i,n]
#print(arr)
Q=int(input())
out=[]

cost={}

for i in range(1,D+1):
    now = i + D
    cost[i]=0
    #cost[i]=abs(d[now][0] - d[now - D][0]) + abs(d[now][1] - d[now - D][1])
    while now <= H * W:
        cost[now] = cost[now - D] + abs(d[now][0] - d[now - D][0]) + abs(d[now][1] - d[now - D][1])
        now += D


out=[]
for k in range(Q):
    start,end=list(map(int,input().split(" ")))
    out.append(cost[end]-cost[start])

for i in out:
    print(int(i))
N = input()
a=map(int,raw_input().split())
print(a)
for i in range(1,N):
    v = a[i]
    j = i-1
    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j-=1
    a[j+1]=v
    print(a)

### FIXED CODE ###

N = int(input())
a = [int(x) for x in input().split()]
for i in range(N):
    v = a[i]
    j = i-1
    while j >= 0 and a[j] > v:
        a[j+1] = a[j]
        j-=1
    a[j+1]=v
    print(*a)
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
if m == 0:
    if n == 1:
        print(0)
    else:
        print('1' + '0' * (n - 1))
sc = [list(map(int, readline().split())) for i in range(m)]
sc.sort()
memo = sc[0]
if sc[0] == [1, 0] and n != 1:
    print(-1)
    exit()
for i in range(1, m):
    if memo[0] == sc[i][0]:
        if memo[1] != sc[i][1]:
            print(-1)
            exit()
    else:
        memo = sc[i]
ans = ''
for i in range(n):
    for j in range(m):
        if i + 1 == sc[j][0]:
            ans += str(sc[j][1])
            break
    if len(ans) != i + 1:
        if len(ans) == 0:
            ans += '1'
        else:
            ans += '0'
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, m = map(int, readline().split())
if m == 0:
    if n == 1:
        print(0)
    else:
        print('1' + '0' * (n - 1))
    exit()
sc = [list(map(int, readline().split())) for i in range(m)]
sc.sort()
memo = sc[0]
if sc[0] == [1, 0] and n != 1:
    print(-1)
    exit()
for i in range(1, m):
    if memo[0] == sc[i][0]:
        if memo[1] != sc[i][1]:
            print(-1)
            exit()
    else:
        memo = sc[i]
ans = ''
for i in range(n):
    for j in range(m):
        if i + 1 == sc[j][0]:
            ans += str(sc[j][1])
            break
    if len(ans) != i + 1:
        if len(ans) == 0:
            ans += '1'
        else:
            ans += '0'
print(ans)
def sum_dict(d, sum, b, c):
    val = 0
    if b in d:
        val = d[b]
        sum -= (b * val)
        del d[b]
        d[c] = d.get(c, 0) + val
        sum += (c * val)
    return sum, d
    
n = int(input())
a = [int(x) for x in input().split()]
d = {}
for i in a:
    d[i] = d.get(i, 0) + 1
s = sum(a)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    s, d = sum_dict(d, b, c)
    print(s)

### FIXED CODE ###

def sum_dict(d, sum, b, c):
    val = 0
    if b in d:
        val = d[b]
        sum -= (b * val)
        del d[b]
        d[c] = d.get(c, 0) + val
        sum += (c * val)
    return sum, d
    
n = int(input())
a = [int(x) for x in input().split()]
d = {}
for i in a:
    d[i] = d.get(i, 0) + 1
s = sum(a)
q = int(input())
for i in range(q):
    b, c = map(int, input().split())
    s, d = sum_dict(d, s, b, c)
    print(s)
from math import floor, ceil, sqrt, factorial, log, gcd
from itertools import accumulate, permutations, combinations, product, combinations_with_replacement
from bisect import bisect_left, bisect_right
from collections import Counter, defaultdict
from heapq import heappop, heappush, heappushpop
import copy
import numpy as np
import sys
INF = float('inf')
mod = 10**9+7


def lcm(a, b): return a * b / gcd(a, b)

# 1 2 3
# a, b, c = LI()


def LI(): return list(map(int, sys.stdin.buffer.readline().split()))

# a = I()


def I(): return int(sys.stdin.buffer.readline())

# abc def
# a, b = LS()


def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()

# a = S()


def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')

# 2
# 1
# 2
# [1, 2]


def IR(n): return [I() for i in range(n)]

# 2
# 1 2 3
# 4 5 6
# [[1,2,3], [4,5,6]]


def LIR(n): return [LI() for i in range(n)]

# 2
# abc
# def
# [abc, def]


def SR(n): return [S() for i in range(n)]

# 2
# abc def
# ghi jkl
# [[abc,def], [ghi,jkl]]


def LSR(n): return [LS() for i in range(n)]

# 2
# abcd
# efgh
# [[a,b,c,d], [e,f,g,h]]


def SRL(n): return [list(S()) for i in range(n)]


def dfs(n):
    visited[n-1] = True
    for child in graph[n-1]:
        if visited[child-1]:
            continue
        point[child-1] += point[n-1]
        dfs(child)


n, q = LI()
point = [0]*n
graph = [[] for i in range(n)]

for i in range(n - 1):
    a, b = LI()
    graph[a - 1].append(b)
    graph[b - 1].append(a)


for i in range(q):
    p, x = LI()
    point[p - 1] += x

visited = [False]*n


dfs(1)


print(*point)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
 
N, Q = map(int, input().split())
root = [[] for _ in range(N)]
ans = [0]*N
 
for _ in range(N-1):
  a,b=map(int, input().split())
  a,b=a-1,b-1
  root[a].append(b)
  root[b].append(a)

for _ in range(Q):
  p,x=map(int, input().split())
  ans[p-1]+=x
  
visited=[False]*N
def dfs(v):
  visited[v] = True
  for go in root[v]:
    if visited[go]:
      continue
    ans[go] += ans[v]
    dfs(go)

dfs(0)
print(*ans)
import sys
from collections import deque
readline = sys.stdin.readline

def main():
  x,y,a,b,c=map(int,readline().split())

  red=[int(i) for i in readline().split()]
  green=[int(i) for i in readline().split()]
  nc=sorted([int(i) for i in readline().split()], reverse=1)
  if a<x:
    red+=nc[:(x-a)]
    nc=nc[(x-a):]
  if b<y:
    green+=nc[:(y-b)]
    nc=nc[(y-b):]
  red=deque(sorted(red)[-x:])
  green=deque(sorted(green)[-y:])
  res=0
  for i in nc:
    tr=red[0]
    tg=green[0]
    if tr<tg:
      if i>tr:
        red.popleft()
        res+=i
    else:
      if i>tg:
        green.popleft()
        res+=i
  print(res+sum(red)+sum(green))

main()

### FIXED CODE ###

import sys
from collections import deque
readline = sys.stdin.readline

def main():
  x,y,a,b,c=map(int,readline().split())

  red=[int(i) for i in readline().split()]
  green=[int(i) for i in readline().split()]
  nc=sorted([int(i) for i in readline().split()], reverse=1)
  if a<x:
    red+=nc[:(x-a)]
    nc=nc[(x-a):]
  if b<y:
    green+=nc[:(y-b)]
    nc=nc[(y-b):]
  red=deque(sorted(red)[-x:])
  green=deque(sorted(green)[-y:])
  res=0
  
  def ppl(lst,i,t):
    if i>t:
      lst.popleft()
      return i
    else:
      return 0
    
  for i in nc:
    if (not red) and (not green):
      break
    if not red:
      tg=green[0]
      res+=ppl(green,i,tg)
    elif not green:
      tr=red[0]
      res+=ppl(red,i,tr)
    else:
      tr=red[0]
      tg=green[0]
      if tr<tg:
        res+=ppl(red,i,tr)
      else:
        res+=ppl(green,i,tg)
    
  print(res+sum(red)+sum(green))

main()