Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
A.sort(reverse=True)
B.sort(reverse=True)
C.sort(reverse=True)
D = []
for i in range(X):
    for j in range(Y):
        for k in range(Z):
            if i + j + k > K:
                break
            D.append(A[i] + B[j] + C[k])
D.sort(reverse=True)
for ans in D[:K]:
    print(ans)

### FIXED CODE ###

x,y,z,K=map(int,input().split())
a=list(map(int,input().split()))
b=list(map(int,input().split()))
c=list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)
ans=[]
for i in range(x):
  for j in range(y):
    for k in range(z):
      if (i+1)*(j+1)*(k+1)<=K:
        ans.append(a[i]+b[j]+c[k])
      else:
        break
ans.sort(reverse=True)
for i in range(K):
  print(ans[i])
### BUGGY CODE ###

N = int(input())
n = [int(input()) for i in range(N)]

def Is_prime(n):
    if n == 2:
        return True
    if n == 1:
        return False
    if n % 2 == 0:
        return False
    i = 3
    while i < int(n ** (0.5))+ 1:
        if n % i == 0:
            return False
    return True

count = 0
for j in n:
    if Is_prime(j):
        count += 1

print (count)

### FIXED CODE ###

N = int(input())
n = [int(input()) for i in range(N)]

def Is_prime(n):
    if n == 2:
        return True
    if n == 1:
        return False
    if n % 2 == 0:
        return False
    i = 3
    while i < int(n ** (0.5))+ 1:
        if n % i == 0:
            return False
        i += 2
    return True

count = 0
for j in n:
    if Is_prime(j):
        count += 1

print (count)
### BUGGY CODE ###

X=int(input())
for j in range(2,int(X**0.5)+1):
    if X%j==0:
        for a in range(X):
            b=a-j
            S=j*(a**4+b**4+(a**3)*b+(a**2)*(b**2)+a*(b**3))
            if S==X:
                print(a,b)
                exit(0)
if X==1:
    print(0,-1)



### FIXED CODE ###

X=int(input())
for j in range(int(X**0.5)+2,0,-1):
    if X%j==0:
        for a in range(2*(10**4)):
            b=a-j
            S=j*(a**4+b**4+(a**3)*b+(a**2)*(b**2)+a*(b**3))
            if S==X:
                print(a,b)
                exit(0)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))

res = 0
for i in range(N-1):
    for j in range(i+1,N):
       res += A[i]*A[j]
    
print(res%((10**9)+7))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
 
A_j = sum(A)
mod = (10**9)+7
res = 0
for i in range(N-1):
    A_j -= A[i]
    res += (A[i] * (A_j % mod)) % mod

print(res % mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())
a = list(map(int, input().split()))
cnt = [0, 0, 0, 0]
for x in a:
    cnt[x] += 1
p, q, r = cnt[1], cnt[2], cnt[3]

dp = [[[0] * (n + 1) for _ in range(n + 1)] for _ in range(n+1)]

for k in range(r + 1):
    for j in range(r + q + 1):
        for i in range(n + 1):
            if not (0 < i + j + k <= n): continue
            tmp = 0
            if i > 0: tmp += dp[i - 1][j][k] * i
            if j > 0: tmp += dp[i + 1][j - 1][k] * j
            if k > 0: tmp += dp[i][j + 1][k - 1] * k
            tmp += n
            dp[i][j][k] = tmp / (i + j + k)

print(dp[p][q][r])


### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq
sys.setrecursionlimit(10**7)
INF = 10**18
MOD = 10**9 + 7
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N = NI()
a = [0,0,0]
for x in LI():
    a[x-1] += 1
dp = [[[0.0] * (N+1) for _ in range(N+1)] for _ in range(N+1)]

for k in range(a[2]+1):
    for j in range(a[1]+a[2]+1):
        for i in range(N+1):
            if not (0 < i+j+k <= N): continue
            x = 0.0
            if i > 0: x += dp[i-1][j][k] * (i/N)
            if j > 0: x += dp[i+1][j-1][k] * (j/N)
            if k > 0: x += dp[i][j+1][k-1] * (k/N)
            x += 1.0
            x *= N / (i+j+k)
            dp[i][j][k] = x
print(dp[a[0]][a[1]][a[2]])
### BUGGY CODE ###

s=input()
l=len(s)

dp=[[0]*3 for i in range(l)]
mod=10**9+7
c=0

for i in range(l):
    if s[i]=="A":
        dp[i][0]=dp[i-1][0]+3**c
        dp[i][1]=dp[i-1][1]
        dp[i][2]=dp[i-1][2]
    elif s[i]=="B":
        dp[i][0]=dp[i-1][0]
        dp[i][1]=dp[i-1][1]+dp[i-1][0]
        dp[i][2]=dp[i-1][2]
    elif s[i]=="C":
        dp[i][0]=dp[i-1][0]
        dp[i][1]=dp[i-1][1]
        dp[i][2]=dp[i-1][2]+dp[i-1][1]
    else:
        dp[i][0]=dp[i-1][0]*3+3**c
        dp[i][1]=dp[i-1][1]*3+dp[i-1][0]
        dp[i][2]=dp[i-1][2]*3+dp[i-1][1]
        c+=1
    dp[i][0]=dp[i][0]%mod
    dp[i][1]=dp[i][1]%mod
    dp[i][2]=dp[i][2]%mod

print(dp[-1][2])


### FIXED CODE ###

s=input()
l=len(s)
dp=[[0]*4 for i in range(l+1)]
dp[0][0]=1
mod=10**9+7
for i in range(l):
    c = s[i]
    dp[i+1][0]=dp[i][0] 
    dp[i+1][1]=dp[i][1] 
    dp[i+1][2]=dp[i][2] 
    dp[i+1][3]=dp[i][3] 
    if c=="A":
        dp[i+1][1]+=dp[i][0]
    if c=="B":
        dp[i+1][2]=dp[i][2]+dp[i][1] 
    if c=="C":
        dp[i+1][3]=dp[i][3]+dp[i][2]
    if c=="?":
        dp[i+1][0] = (3*dp[i][0])%mod
        dp[i+1][1] = (dp[i][0] + 3*dp[i][1]) % mod
        dp[i+1][2] = (dp[i][1] + 3*dp[i][2]) % mod
        dp[i+1][3] = (dp[i][2] + 3*dp[i][3]) % mod
        

print(dp[-1][3]%mod)
### BUGGY CODE ###

n, m = map(int, input().split())
cnt = 0
for i in range(n):
    if m<=2:
        break
    cnt+=1
    m-=2
print(int(m//4)+cnt)


### FIXED CODE ###

n, m = map(int, input().split())
mm = m//2
print(mm if n>mm else (mm-n)//2+n)
### BUGGY CODE ###

D = int(input())
c = [int(i) for i in input().split()]
s = [[int(i) for i in input().split()] for _ in range(D)]
t = [int(input())-1 for _ in range(D)]
llst = [0]*26

def scoreing():
    res = 0
    for i in range(26): llst[i] = 0
    for day,i in enumerate(range(D),1):
        llst[t[i]] = day
        res += s[i][t[i]]
        for j in range(26): res -= c[j]*(day-llst[j])
    return res
        
M = int(input())
ans = [0]*M
for i in range(M):
    d,q = map(int,input().split())
    d -= 1
    q -= 1
    t[d] = q
    ans[i] = scoreing()
for i in range(M): print(ans[i])

### FIXED CODE ###

D = int(input())
c = [int(i) for i in input().split()]
s = [[int(i) for i in input().split()] for _ in range(D)]
t = [int(input())-1 for _ in range(D)]

def scoreing(x):
    res = 0
    last = 0
    for day,i in enumerate(range(D),1):
        if t[i] == x:
            last = day
            res += s[i][x]
        res -= c[x]*(day-last)
    return res

score = [0]*26
for i in range(26): score[i] = scoreing(i)
M = int(input())
ans = [0]*M
for i in range(M):
    d,q = map(int,input().split())
    d -= 1
    q -= 1
    old = t[d]
    t[d] = q
    score[old] = scoreing(old)
    score[q] = scoreing(q)
    ans[i] = sum(score)
for i in range(M): print(ans[i])
### BUGGY CODE ###

#!/usr/bin/env python3

from pprint import pprint
import sys

sys.setrecursionlimit(10 ** 6)


# s, t \in V (s < t) に対して、s から t への最短経路を d_min(s, t) とすると、
# d_min(s, t) は、
# d_min(s, t) = min(t - s, abs(x - s) + 1 + abs(t - y))
# で与えられる。
# なので、s, t の全ての組み合わせに対して d_min(s, t) を計算し、条件を満たすような s, t の組を数え上げればよい。


N, X, Y = map(int, input().split())
# 0-index
X -= 1
Y -= 1

# O(N^2)
for k in range(1, N):
    count = 0
    for s in range(N - 1):
        for t in range(s + 1, N):
            dist = min(t - s, abs(X - s) + 1 + abs(t - Y))
            if dist != k:
                continue
            count += 1
    print(count)


### FIXED CODE ###

#!/usr/bin/env python3

from pprint import pprint
from collections import defaultdict
import sys

sys.setrecursionlimit(10 ** 6)


# s, t \in V (s < t) に対して、s から t への最短経路を d_min(s, t) とすると、
# d_min(s, t) は、
# d_min(s, t) = min(t - s, abs(x - s) + 1 + abs(t - y))
# で与えられる。
# なので、s, t の全ての組み合わせに対して d_min(s, t) を計算し、条件を満たすような s, t の組を数え上げればよい。


N, X, Y = map(int, input().split())
# 0-index
X -= 1
Y -= 1

count_dict = defaultdict(int)

# O(N^2)
for s in range(N - 1):
    for t in range(s + 1, N):
        dist = min(t - s, abs(X - s) + 1 + abs(t - Y))
        count_dict[dist] += 1

for k in range(1, N):
    ans = 0
    if k in count_dict:
        ans = count_dict[k]
    print(ans)
### BUGGY CODE ###

MAXN = 2*10**6+2
p = 10**9 + 7

fact = [1] * MAXN
invfact = [1] * MAXN
for i in range(1, MAXN):
    fact[i] = fact[i-1] * i % p
invfact[MAXN-1] = pow(fact[MAXN-1], p-2, p)
for i in range(MAXN-1, 0, -1):
    invfact[i-1] = invfact[i] * i % p
    
def nCk(n, k):
    return fact[n] * invfact[n-k] * invfact[k] % p

K = int(input())
N = len(input())

ans = 0
for i in range(N, N+K+1):
    ans += pow(25, i-N, p) * nCk(i-1, N-1) * pow(26, N+K-i, p) % p
    ans %= p
print(ans)


### FIXED CODE ###

MAXN = 2*10**6+2
p = 10**9 + 7

fact = [1] * MAXN
invfact = [1] * MAXN
for i in range(1, MAXN):
    fact[i] = fact[i-1] * i % p
invfact[MAXN-1] = pow(fact[MAXN-1], p-2, p)
for i in range(MAXN-1, 0, -1):
    invfact[i-1] = invfact[i] * i % p
    
def nCk(n, k):
    return fact[n] * invfact[n-k] * invfact[k] % p

K = int(input())
N = len(input())

ans = 0
for i in range(N, N+K+1):
    ans += pow(25, i-N, p) * nCk(i-1, N-1) * pow(26, N+K-i, p) % p
    ans %= p
print(ans)
### BUGGY CODE ###

import sys
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))

if N == 2:
  print(max(A))
  sys.exit()

g = gcd(A[0], A[1])
#X = set([A[0], A[1]])
X = [A[0], A[1]]

for a in A[2:]:
  XX = [g]
  g = gcd(g, a)
  for x in X:
    XX.append(gcd(x, a))
  X = XX

print(max(X))

### FIXED CODE ###

import sys
from fractions import gcd

N = int(input())
A = list(map(int, input().split()))

if N == 2:
  print(max(A))
  sys.exit()

g = gcd(A[0], A[1])
X = set([A[0], A[1]])

for a in A[2:]:
  XX = set([g])
  g = gcd(g, a)
  for x in X:
    XX.add(gcd(x, a))
  X = XX

print(max(X))
### BUGGY CODE ###

import itertools
import bisect

n = int(input())

L = list(map(int,input().split()))

A = sorted(L)

ans = 0

for a,b in itertools.combinations(A,2):
    total = a + b
    l = bisect.bisect(A,max(a,b))
    r = bisect.bisect_left(A,total) 
    ans += max(0,r-l)

print(ans)        


### FIXED CODE ###

import itertools
import bisect

n = int(input())

L = list(map(int,input().split()))

A = sorted(L)

ans = 0

for i in range(n):
    for j in range(i+1,n):
        total = L[i] + L[j]
        ans += bisect.bisect_left(A,total) - (j+1)

print(ans)
### BUGGY CODE ###

from math import ceil, floor

N = int(input())
A = [int(t) for t in input().split()]
if len(A) != N: raise

p = [A[i-1] - i for i in range(1, N+1)]

q = []
for b in p:
    q.append(sum(abs(x - b) for x in p))
print(min(q))

### FIXED CODE ###

from math import ceil, floor

N = int(input())
A = [int(t) for t in input().split()]
if len(A) != N: raise

p = [A[i-1] - i for i in range(1, N+1)]
p.sort()

q = []
for b in p[N//2 - 1 : N//2 + 2]:
    q.append(sum(abs(x - b) for x in p))
print(min(q))
### BUGGY CODE ###

s=input()
n=len(s)
ans=0
for i in range(n-3):
  for j in range(i+3,n+1):
    if int(s[i:j])%2019==0:
      ans+=1
print(ans)

### FIXED CODE ###

from collections import Counter
s=input()
n=len(s)
ans=0
arr=[0]*(n+1)
if s=='0':
    print(1)
    exit()
elif n==1:
    print(0)
    exit()
for i in reversed(range(n)):
    arr[i]=(arr[i+1]+int(s[i])*pow(10,n-i-1,2019))%2019
m=Counter(arr)
for j in m.keys():
    ans+=m[j]*(m[j]-1)//2
print(ans)
### BUGGY CODE ###

#import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial#, gcd
from bisect import bisect_left #bisect_left(list, value)
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep='\n')

N = int(input())
A = list(map(int, input().split()))
A.sort()
maxA = A[-1]

fact = [1]
for i in range(1, maxA+10):
    fact.append(fact[-1] * i % MOD)
def rev(x):
    return pow(x, MOD-2, MOD)
def cmb(i, k):
    if(i < k): return 0
    return fact[i] * rev(fact[k]) * rev(fact[i-k]) % MOD

ans = [A[1], A[0]]
mcand = cmb(A[1], A[0])
for a in A:
    even = a%2==0
    div = a//2
    ind = bisect_left(A, div)
    cand1 = cmb(a, A[ind-1])
    cand2 = cmb(a, A[ind])
    if mcand < cand1:
        ans = [a, A[ind-1]]
    if mcand < cand2:
        ans = [a, A[ind]]

print(*ans)


### FIXED CODE ###

# import numpy as np
import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial, gcd
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10 ** 7)
enu = enumerate
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline()[:-1]
pl = lambda x: print(*x, sep="\n")

N = int(input())
A = list(map(int, input().split()))

fact = [1]
for i in range(1, N + 10):
    fact.append(fact[-1] * i % MOD)


def rev(x):
    return pow(x, MOD - 2, MOD)


def cmb(i, k):
    if i < k:
        return 0
    return fact[i] * rev(fact[k]) * rev(fact[i - k]) % MOD


A.sort()
if N == 2:
    print(A[1], A[0])
    exit()

mv = A[-1]
vm = mv // 2
bli = bisect_left(A, vm)
if bli == N - 1:
    print(mv, A[bli - 1])
elif bli == 0:
    print(mv, A[bli])
else:
    if vm - A[bli - 1] < A[bli] - vm:
        print(mv, A[bli - 1])
    else:
        print(mv, A[bli])
### BUGGY CODE ###

n, k = map(int, input().split())
alist = sorted(list(map(int, input().split())))
mod = 10**9 + 7

fact = [1]
i = 1
while i < n:
    fact.append(fact[i-1] * i)
    i += 1 

def comb_fac(n, k):
    return fact[n] // (fact[n-k] * fact[k])

def comb(n, k):
    n1 = n+1
    r = min(k, n-k)
    numer = denom = 1
    i = 1
    while i < r+1:
        numer = numer * (n1-i) % mod
        denom = denom * i % mod
        i += 1
    
    #memo[n][k] = numer // denom
    #memo[n][k] = numer * pow(denom, mod - 2, mod) % mod
    return numer // denom


amax = 0
i = n-1
while i >= k-1:
    amax += (alist[i] * comb_fac(i, k-1))%mod
    i -= 1

amin = 0
i = 0
while i <= n-k:
    amin += (alist[i] * comb_fac(n-i-1, k-1))%mod
    i += 1
print((amax - amin) % mod)

### FIXED CODE ###

n, k = map(int, input().split())
alist = sorted(map(int, input().split()))
mod = 10**9 + 7

def comb(n, r, p=mod):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % p

fact = [1, 1]
factinv = [1, 1]
inv = [0, 1]
p = mod
N = n
for i in range(2, N + 1):
    fact.append((fact[-1] * i) % p)
    inv.append((-inv[p % i] * (p // i)) % p)
    factinv.append((factinv[-1] * inv[-1]) % p)

amax = 0
amin = 0
i = 0
while i <= n-k:
    cnt = comb(n-i-1, k-1)
    amax += (alist[n-i-1] * cnt)%mod
    amin += (alist[i] * cnt)%mod
    i += 1

print((amax - amin) % mod)
### BUGGY CODE ###

n=int(input())
S=list(input())
R=[0 for _ in range(n)]
G=[0 for _ in range(n)]
B=[0 for _ in range(n)]
r=0;g=0;b=0
for i in range(n):
    if S[i]=="R":
        r+=1 
    if S[i]=="G":
        g+=1
    if S[i]=="B":
        b+=1
    R[i]=r; G[i]=g; B[i]=b
cnt=0
for i in range(n-2):
    for j in range(i,n-1):
        if S[i]==S[j]:
            continue
        if (S[i]=="R" or S[i]=="G") and (S[j]=="R" or S[j]=="G"):
            cnt+=B[-1]-B[j]
            try:
                if S[2*j-i]=="B":
                    cnt-=1
            except:
                pass
        if (S[i]=="G" or S[i]=="B") and (S[j]=="G" or S[j]=="B"):
            cnt+=R[-1]-R[j]
            try:
                if S[2*j-i]=="R":
                    cnt-=1
            except:
                pass
        if (S[i]=="B" or S[i]=="R") and (S[j]=="B" or S[j]=="R"):
            cnt+=G[-1]-G[j]
            try:
                if S[2*j-i]=="G":
                    cnt-=1
            except:
                pass
print(cnt)

### FIXED CODE ###

n=int(input())
S=list(input())
R=[0 for _ in range(n)]
G=[0 for _ in range(n)]
B=[0 for _ in range(n)]
r=0;g=0;b=0
for i in range(n):
    if S[i]=="R":
        r+=1 
    if S[i]=="G":
        g+=1
    if S[i]=="B":
        b+=1
    R[i]=r; G[i]=g; B[i]=b
cnt=0
for i in range(n-2):
    for j in range(i,n-1):
        if S[i]==S[j]:
            continue
        if (S[i]=="R" or S[i]=="G") and (S[j]=="R" or S[j]=="G"):
            cnt+=B[-1]-B[j]
            try:
                if S[2*j-i]=="B":
                    cnt-=1
            except:
                pass
        if (S[i]=="G" or S[i]=="B") and (S[j]=="G" or S[j]=="B"):
            cnt+=R[-1]-R[j]
            try:
                if S[2*j-i]=="R":
                    cnt-=1
            except:
                pass
        if (S[i]=="B" or S[i]=="R") and (S[j]=="B" or S[j]=="R"):
            cnt+=G[-1]-G[j]
            try:
                if S[2*j-i]=="G":
                    cnt-=1
            except:
                pass
print(cnt)
### BUGGY CODE ###

a, b, k =  map(int, input().split())
l = []
for i in range(a, b+1):
    l.append(i)
m = list(set(l[0:k] + l[-k:]))
m.sort()
for j in m:
    print(j)

### FIXED CODE ###

a, b, k =  map(int, input().split())
for i in range(a, min(a+k, b+1)):
    print(i)
for j in range(max(a+k, b-k+1), b+1):
    print(j)
### BUGGY CODE ###

import itertools
import math
import fractions
import functools
import copy

n, k = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))

h.sort()
minimum = 10**10
for i in range(n-k+1):
    minimum = min(minimum,max(h[i:i+k])-min(h[i:i+k]))

print(minimum)

### FIXED CODE ###

import itertools
import math
import fractions
import functools
n, k = map(int, input().split())
h = []
for i in range(n):
    h.append(int(input()))

h.sort()
subs = []
for i in range(1,n):
    subs.append(h[i]-h[i-1])

amount = [0]*(n)
sums = 0
for i in range(0,len(subs)):
    sums += subs[i]
    amount[i+1] = sums


minimum = 10**10
for i in range(k-1,n):
    minimum = min(minimum,amount[i]-amount[i-k+1])

print(minimum)
### BUGGY CODE ###

from statistics import median

N, K = [int(x) for x in input().split()]
line_in_dice = list([median(range(1, int(x)+1)) for x in input().split()])

max_value = 0

for i in range(N):
    if i + K > N:
        break

    check = 0
    for x in range(K):
        check += line_in_dice[i + x]

    if check > max_value:
        max_value = check

print(max_value)


### FIXED CODE ###

from statistics import median
from time import time

t = time()

N, K = [int(x) for x in input().split()]
line_in_dice = list([int(x) for x in input().split()])

result = [0] * (N + K)

result[0] = line_in_dice[0]
result[K] -= line_in_dice[0]

max_point = 0
max_value = 0

for i in range(1, N):
    result[i] += (result[i - 1] + line_in_dice[i])
    result[i + K] -= line_in_dice[i]

    if result[i] > max_value:
        max_point = i
        max_value = result[i]


def create_median(x):
    if x % 2 == 1:
        return (1 + x) // 2
    else:
        return ((x // 2) + (x // 2 + 1)) / 2


print(sum(create_median(x)
          for x in line_in_dice[max_point - K + 1: max_point+1]))
### BUGGY CODE ###

import sys 

def main(n, a_n, q, bc_n):
    m = {}
    for i in range(n):
        if a_n[i] not in m:
            m[a_n[i]] = 0 
        m[a_n[i]] += 1

    s = []
    for j in range(q):
        b, c = bc_n[j]

        if b in m:
            if c not in m:
                m[c] = m[b]
            else:
                m[c] += m[b]
            del m[b]

        ts = 0 
        for k, v in m.items():
            ts += k * v 
        s.append(ts)
    return s


n = int(sys.stdin.readline().strip())
a_n = [int(x) for x in sys.stdin.readline().strip().split(" ")]
q = int(sys.stdin.readline().strip())
bc_n = []
for _ in range(q):
    b, c = [int(x) for x in sys.stdin.readline().strip().split(" ")]
    bc_n.append((b, c)) 
for i in main(n, a_n, q, bc_n):
    print(i)


### FIXED CODE ###

import sys

def main(n, a_n, q, bc_n):
    m = {}
    for i in range(n):
        if a_n[i] not in m:
            m[a_n[i]] = 0
        m[a_n[i]] += 1

    s = []
    for j in range(q):
        b, c = bc_n[j]

        diff = 0
        if b in m:
            diff = m[b] * c  - m[b] * b
            if c not in m:
                m[c] = m[b]
            else:
                m[c] += m[b]
            del m[b]

        ts = 0
        if len(s) == 0:
            for k, v in m.items():
                ts += k * v
        else:
            ts = s[-1] + diff
        s.append(ts)
    return s


n = int(sys.stdin.readline().strip())
a_n = [int(x) for x in sys.stdin.readline().strip().split(" ")]
q = int(sys.stdin.readline().strip())
bc_n = []
for _ in range(q):
    b, c = [int(x) for x in sys.stdin.readline().strip().split(" ")]
    bc_n.append((b, c))
for i in main(n, a_n, q, bc_n):
    print(i)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

n = int(input())
a = list(map(int, input().split()))

d = {}


def func(b, m):
    if m == 0:
        return 0
    if m == 1:
        return b[0]
    if m in d:
        return d[m]

    if m % 2 == 0:
        ans0 = b[0] + func(b[2:], m - 2)
        ans1 = sum(b[i] for i in range(1, m, 2))
        ans = max(ans0, ans1)
    else:
        ans0 = b[0] + func(b[2:], m - 2)
        ans1 = b[1] + func(b[3:], m - 3)
        ans2 = sum(b[i] for i in range(2, m, 2))
        ans = max(ans0, ans1, ans2)

    d[m] = ans
    return ans


ans = func(a, n)

print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

n = int(input())
a = list(map(int, input().split()))

a_cs = [0] * (n + 1)
a_cs[-2] = a[-1]
for i in reversed(range(n - 1)):
    a_cs[i] = a[i] + a_cs[i + 2]
# print(a_cs)

d = {}


def func(i):
    if i == n:
        return 0
    if i == n - 1:
        return a[-1]
    if i in d:
        return d[i]

    m = n - i
    if m % 2 == 0:
        ans0 = a[i] + func(i + 2)
        ans1 = a_cs[i + 1]
        ans = max(ans0, ans1)
    else:
        ans0 = a[i + 0] + func(i + 2)
        ans1 = a[i + 1] + func(i + 3)
        ans2 = a_cs[i + 2]
        ans = max(ans0, ans1, ans2)

    d[i] = ans
    return ans


ans = func(0)

print(ans)
### BUGGY CODE ###

import math
N, K = map(int, input().split())
A = list(map(int, input().split()))


for i in range(K):
    cum_sum = [0]*N
    for j in range(N):
        left = max(0, j - A[j])
        right = min(N-1, j+A[j])
        cum_sum[left] += 1
        if right + 1 < N:
            cum_sum[right+1] -= 1
    A[0] = cum_sum[0]
    for j in range(N-1):
        cum_sum[j+1] += cum_sum[j]
        A[j+1] = cum_sum[j+1]
    
    if A[0] == N and A[N-1] == N:
        break
        
for i in range(N):
    print(A[i], " ", end = "")
print()

### FIXED CODE ###

import math
N, K = map(int, input().split())
A = list(map(int, input().split()))


for i in range(min(K, 42)):
    cum_sum = [0]*N
    for j in range(N):
        left = max(0, j - A[j])
        right = min(N-1, j+A[j])
        cum_sum[left] += 1
        if right + 1 < N:
            cum_sum[right+1] -= 1
    A[0] = cum_sum[0]
    for j in range(N-1):
        cum_sum[j+1] += cum_sum[j]
        A[j+1] = cum_sum[j+1]
    
        
for i in range(N):
    print(A[i], " ", end = "")
print()