Harryxun/stf_run huggingface dataset:
import fractions
N,M = map(int,input().split())
S = input()
T = input()
X = (N * M) // fractions.gcd(N,M)

div_N = X // N
div_M = X // M  
s = [""] * X

for ss in range(N):
  if ss == 0:
    s[0] = S[0]
    if s[0] != T[0]:
      print(-1)
      exit()
  else:
    s[ss * (div_N)] = S[ss]

for tt in range(M):
  if tt == 0:
    if s[0] != T[tt]:
      print(-1)
      exit()
  else:
    pro = tt * (div_M)
    if s[pro] != "" and s[pro] != T[tt]:
      print(-1)
      exit()
print(X)



### FIXED CODE ###

import fractions
N,M = map(int,input().split())
S = input()
T = input()
G = fractions.gcd(N,M)
L = (N * M) // G
div_N = N // G
div_M = M // G

i = 0
j = 0

while i < N and j < M:
  if S[i] != T[j]:
    print(-1)
    exit()
  else:
    i += div_N
    j += div_M
print(L)
abc = list(map(int, input.split()))
if len(set(abc)) == 1:
    print('Yes')
else:
    print('No')


### FIXED CODE ###

abc = list(map(int, input().split()))
if len(set(abc)) == 1:
    print('Yes')
else:
    print('No')
n = int(input())
aaa = list(map(int, input().split()))
aaa.sort()
mod = 10 ** 9 + 7
ans = int(2 ** (n / 2) % mod) if n % 2 == 0 else int(2 ** ((n - 1) / 2) % mod)
if n % 2 == 0:
    for i in range(0, n, 2):
        if aaa[i] != aaa[i + 1]:
            ans = 0
            break
else:
    for i in range(1, n, 2):
        if aaa[i] != aaa[i + 1]:
            ans = 0
            break
print(ans)

### FIXED CODE ###

def pow_mod(n, k, m):
    if k == 0:
        return 1
    if k & 1:
        return (pow_mod(n, k - 1, m) * n % m) % m
    else:
        return (pow_mod(n, k // 2, m) ** 2) % m

n = int(input())
aaa = list(map(int, input().split()))
mod = 10 ** 9 + 7
aaa.sort()
if n % 2 == 0:
    for i in range(0, n, 2):
        if aaa[i] != aaa[i + 1]:
            print(0)
            exit()
    print(pow_mod(2, (n // 2), mod))
else:
    for i in range(1, n, 2):
        if aaa[i] != aaa[i + 1]:
            print(0)
            exit()
    print(pow_mod(2, ((n - 1) // 2), mod))
import numpy as np

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

l = np.zeros(N)

for i in range(1,N+1):
    l[i-1] = np.floor((A*i)/B) - A * np.floor(i/B)

print(int(np.max(l)))

### FIXED CODE ###

import numpy as np
import math

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

i = B-1

if i >= N:
  x = N
else:
  x = B-1

print(math.floor((A*x)/B) - A * math.floor((x/B)))
n = int(input())
x = (n+1000)//1000*1000-n
if x==1000:
  print(0)
  else:
    print(x)

### FIXED CODE ###


from collections import deque



# for #!/usr/bin/env python
import os
import sys
from io import BytesIO, IOBase


# region fastio

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
from bisect import bisect_left as bl
from math import log2,ceil
from heapq import heappush, heappop
from itertools import permutations 
def main():
    # for t in range(int(input())):
        n = int(input())
        x = (n+1000)//1000*1000-n
        if x==1000:
            print(0)
        else:
            print(x)

            # heappush(h, l[i])

        


        
        




# endregion

if __name__ == "__main__":
    main()
from collections import deque

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

kotae = deque([])
lst = []
d = deque(a)
shugo = []
pattern = 0
while True:
    for kazu in d:
        if kazu in kotae:
            ind = kotae.index(kazu)
            for _ in range(len(kotae) - ind):
                kotae.pop()
        else:
            kotae.append(kazu)
    kotae_lst = list(kotae)
    if kotae_lst in shugo:
        break
    else:
        shugo.append(kotae_lst)
        lst.append(kotae_lst)
        pattern += 1

doko = k % pattern
ans = lst[doko-1]
if ans != []:
    print(' '.join(map(str, ans)))

### FIXED CODE ###

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

dic = {}
for i in range(n):
    if a[i] in dic:
        dic[a[i]].append(i)
    else:
        dic[a[i]] = [i]

zero = [-1 for i in range(n)]
for key, value in dic.items():
    num = len(value)
    for i in range(num-1):
        zero[value[i]] = value[i+1] - value[i] + 1
    zero[value[-1]] = n - value[-1] + value[0] + 1

lst = [zero]
while lst[-1][0] <+ n*k - 1:
    before = lst[-1]
    after = []
    for i in range(n):
        after.append(before[i] + before[(before[i]+i)%n])
    lst.append(after)
lst.pop()

i = 0
while lst != []:
    lsti = lst.pop()
    while True:
        if i + lsti[i%n] <= n*k - 1:
            i = i + lsti[i%n]
        else:
            break

i = i % n
nokori = a[i:]
lst = []
dic = {}
ko = 0
for i in range(len(nokori)):
    if nokori[i] not in dic:
        lst.append(nokori[i])
        dic[nokori[i]] = ko
        ko += 1
    else:
        lst = lst[:dic[nokori[i]]]
        dic = {}
        for j in range(len(lst)):
            dic[lst[j]] = j
        ko = len(lst)
print(*lst)
a=input()#500
b=input()#100
c=input()#50
x=input()

count=0

for a_num in range(a+1):
  for b_num in range(b+1):
    for c_num in range(c+1):
      if a*500+b*100+c*50==x:
        count+=1

print(str(count))

### FIXED CODE ###

a,b,c,x = [int(input()) for _ in range (4)]


count=0

for a_num in range(a+1):
  for b_num in range(b+1):
    for c_num in range(c+1):
      if a_num*500+b_num*100+c_num*50==x:
        count+=1

print(str(count))
a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
if v <= w:
    print('NO')
else:
    elif 1 <= ((b - a) / (v - w)) <= t:
        print('YES')
    else:
        print('NO')

### FIXED CODE ###

a, v = map(int, input().split())
b, w = map(int, input().split())
t = int(input())
if v <= w:
    print('NO')
else:
    if 1 <= (abs(b - a) / (v - w)) <= t:
        print('YES')
    else:
        print('NO')
4 54

### FIXED CODE ###

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

print(int(A+B/2))
"""
N = int(input())
S = input()

def main(N,S):
    count=0
    for i in range(1,N-2 +1):
        for j in range(i+1, N-1 +1):
            for k in range(j+1, N +1):
                if j-i != k-j and S[i-1]!=S[j-1]!=S[k-1]!=S[i-1]:
                    count += 1
    print(count)

if __name__=='__main__':
    main(N,S)
    
    """
import itertools
N = int(input())
S = input()
out = S.count('R') * S.count('G') * S.count('B')

RGBs = list(itertools.permutations(['R', 'G', 'B'], 3))

for i in range(1, N-1):
  for j in range(i+1,N):
      for k in range(j+1,N+1):
          if (S[i], S[j], S[k]) in RGBs:
              out -= 1
print(out)


### FIXED CODE ###


N=int(input())
S=input()

#(RGB)になる組み合わせをカウント
count= S.count("R")*S.count("G")*S.count("B")
count0=0

#条件を満たさないものを引いていく
for i in range(1,N-2 +1):
    for j in range(i+1,(N+i)//2 +1):
        k=2*j-i
        if S[k-1]!=S[i-1] and S[k-1]!=S[j-1] and S[i-1]!=S[j-1]:
            count0 += 1
print(count-count0)
s = input()
ans = 0
lis = []

for a in s:
  if a == "A" or a == "T" or a == "C" or a == "G":
    ans += 1
  else:
    lis.append(ans)
    ans = 0

print(max(lis))
 

### FIXED CODE ###

s = input()
ans1 = 0
ans2 = 0

for a in s:
  if a == "A" or a == "T" or a == "C" or a == "G":
    ans2 += 1
  else:
    if ans1 < ans2:
      ans1 = ans2
      ans2 = 0
    else:
      ans2 = 0
print(max(ans1, ans2))
# solution

import numpy as np
n,m = map(int,input().split())
ar = np.array([list(input()) for _ in range(h)]) == '.'
l = np.zeros((n,m),dtype=int)
r = np.zeros((n,m),dtype=int)
u = np.zeros((n,m),dtype=int)
d = np.zeros((n,m),dtype=int)

for i in range(n):
  u[i] = (u[i-1]+1)*ar[i]
  d[-i-1] = (d[-i]+1)*ar[-i-1]
  
for j in range(m):
  l[:,j] = (l[:,j-1]+1)*ar[:,j]
  r[:,-j-1] = (r[:,-j]+1)*ar[:,-j-1]
print(np.max(u+d+l+r)-3)

### FIXED CODE ###

import numpy as np
h,w = map(int,input().split())
ar = np.array([list(input()) for _ in range(h)]) == '.'
#print(ar)
l = np.zeros((h,w),dtype=int)
r = np.zeros((h,w),dtype=int)
u = np.zeros((h,w),dtype=int)
d = np.zeros((h,w),dtype=int)

for i in range(h):
  u[i] = (u[i-1]+1)*ar[i]
  #print(u)
  d[-i-1] = (d[-i]+1)*ar[-i-1]
  #print(d)
  
for j in range(w):
  l[:,j] = (l[:,j-1]+1)*ar[:,j]
  #print(l)
  r[:,-j-1] = (r[:,-j]+1)*ar[:,-j-1]
  #print(r)
print(np.max(u+d+l+r)-3)
sa = input()
sb = input()
sc = input()
ia = 0
ib = 0
ic = 0
next = 'a'
while True:
  if ia == len(sa)-1:
    print('A')
    break
  if ib == len(sb)-1:
    print('B')
    break
  if ic == len(sc)-1:
    print('C')
    break
  if next == 'a':
    next = S[ia]
    ia += 1
  if next == 'b':
    next = S[ib]
    ib += 1
  if next == 'c':
    next = S[ic]
    ic += 1
  

### FIXED CODE ###

sa = input()
sb = input()
sc = input()
next = sa[0]
while True:
  if next == 'a':
    if len(sa) == 0:
      print('A')
      break
    else:
      next = sa[0]
      sa = sa[1:]
  elif next == 'b':
    if len(sb) == 0:
      print('B')
      break
    else:
      next = sb[0]
      sb = sb[1:]
  else:
    if len(sc) == 0:
      print('C')
      break
    else:
      next = sc[0]
      sc = sc[1:]
q=int(input())
ab=[list(map(int,input().split())) for _ in range(q)]
for a,b in ab:
    if a>b:a,b=b,a
    if a==b:
        print(2*a-2)
    elif a+1==b:
        print(2*a-2)
    else:
        c=int((a*b)**0.5)
        if c*(c+1)>=a*b:
            print(2*c-2)
        elif c**2<a*b:
            print(2*c-1)


q=int(input())
ab=[list(map(int,input().split())) for _ in range(q)]
from math import floor
for a,b in ab:
    # a*bをぎりぎりまで攻めたい
    # (1,1)とかはもったいない。(1,a*b-1)は良い。片方は√a*b未満で、片方は√a*bより大きい組み合わせ。
    # a==bならa未満の整数yについて適切な数字xを選べばy*x<a*bとできる。xは他のxと被らないように選択できる。
    if a==b:
        print(2*a-2)
    else:
        # t,t+1 組み合わせの積がa*bで抑えられているかどうか。(t+1)*(t+1)は必ずa*bを超える。
        # t未満の自然数については適切な整数を選べばa*b以下にできる。
        t=floor((a*b)**0.5)
        # (1,2*t-1),(2,2*t-2),(3,(a*b-1)//3),...,(t-1,(a*b-1)//(t-1))
        if t*t>=a*b: 
            # t*tはだめ。t*t=a*b、a!=bのとき。t未満の数字と適切な数字を選べばよいが、t未満の数字の内一つはaなので、その分を引く。
            print(2*t-3)
        elif t*(t+1)>=a*b: 
            # t*tはOK。t*(t+1)はだめ。t未満の数字と適切な数字を選べばよいが、t未満の数字の内一つはaなので、その分を引く。
            # さらに一回目tの人は2回目もtで条件を満たす。この分を足す。t!=a,t!=bなので(t,t)は選択できる。
            print(2*t-2)
        else:
            # t*tもt*(t+1)もOK。(t,t+1),(t+1,t)をまず選ぶ。あとはt未満の数字と適切な数字を選べばよいが、t未満の数字の内一つはaなので、その分を引く。
            print(2*t-1)


### FIXED CODE ###

q=int(input())
ab=[list(map(int,input().split())) for _ in range(q)]
from math import floor
for a,b in ab:
  if a==b:
    print(2*a-2)
    continue
  t=floor((a*b)**0.5)
  # t,t+1 組み合わせの積がa*bで抑えられているかどうか
  if t*t>=a*b: # t*tもだめ
    print(2*t-3)
  elif t*(t+1)>=a*b: # t*(t+1)はだめ
    print(2*t-2)
  else: # t*tもt*(t+1)もOK
    print(2*t-1)
N , A , B = map(int, input().split())
res = 0

for i in range(N):
  temp = 0
  
  while (a >= 10):
  
  	temp += i % 10
  	a = i // 10
  temp += a
  
  if (temp >= A and temp <= B):
    res += temp
    
print(res)

### FIXED CODE ###

def findSUM(n):
    sum = 0
    while (n > 0):
        sum += n % 10
        n //= 10
    return sum

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

total = 0
for i in range(N+1):
    sum = findSUM(i)
    if (sum >= A and sum <= B):
        total += i

print(total)
import numpy as np
N, M = list(map(int, input().split()))
p = list(map(int, input().split()))
x = []
y = []
for _ in range(M):
    xi, yi = list(map(int, input().split()))
    x.append(xi - 1)
    y.append(yi - 1)

def count(l):
    out = 0
    for i, v in enumerate(l):
        if i + 1 == v:
            out += 1
    return out

def swap(l, a, b):
    va = l[a]
    vb = l[b]
    l1 = l.copy()
    l1[a] = vb
    l1[b] = va
    return l1

depth = 0
max_count = count(p)
max_d = M**5
children = [p]
next_children = []
while depth <= max_d:
    for child in children:
        for i in range(M):
            pi = swap(child, x[i], y[i])
            ci = count(pi)
            if ci > max_count:
                max_count = ci
	    if not pi in next_children:
                next_children.append(pi)
    depth += 1
    children = next_children
    next_chldren = []
    if max_count == len(p):
        break

print(max_count)

### FIXED CODE ###

import numpy as np

s = input()
K = int(input())
L = len(s)

candidate = []

for l in range(1, K + 1):
    for j in range(0, L - l + 1):
        candidate.append(s[j:j+l])

candidate = list(set(candidate))
print(np.sort(candidate)[K-1])
import numpy

inp=input().split(" ")
n=int(inp[0])
m=int(inp[1])
inh=input().split(" ")
for i in range(len(inh)):
  inh[i]=int(inh[i])
pairs=numpy.zeros(2*m,dtype=">i4").reshape(-1,2)
for i in range(m):
  a=input().split(" ")
  pairs[i][0]=int(a[0])
  pairs[i][1]=int(a[1])
lists=[[] for i in range(n+1)]
for i in range(len(pairs)):
  lists[pairs[i][0]-1].append(pairs[i][1])
  lists[pairs[i][1]-1].append(pairs[i][0])
for i in range(len(lists)):
  lists[i]=list(set(lists[i]))
count=0
for i in range(len(lists)):
  if len(lists[i])==0:
    count+=1
    continue
  for j in range(len(lists[i])):
    if inh[i-1] <= inh[lists[i][j]]:
      break
    if j == len(lists[i])-1:
      count+=1
print(count)

### FIXED CODE ###

import numpy

inp=input().split(" ")
n=int(inp[0])
m=int(inp[1])
inh=input().split(" ")
for i in range(len(inh)):
  inh[i]=int(inh[i])
pairs=numpy.zeros(2*m,dtype=">i4").reshape(-1,2)
for i in range(m):
  a=input().split(" ")
  pairs[i][0]=int(a[0])
  pairs[i][1]=int(a[1])
lists=[[] for i in range(n)]
for i in range(len(pairs)):
  lists[pairs[i][0]-1].append(pairs[i][1]-1)
  lists[pairs[i][1]-1].append(pairs[i][0]-1)
for i in range(len(lists)):
  lists[i]=list(set(lists[i]))
count=0
for i in range(len(lists)):
  if len(lists[i])==0:
    count+=1
    continue
  for j in range(len(lists[i])):
    if inh[i] <= inh[lists[i][j]]:
      break
    if j == len(lists[i])-1:
      count+=1
print(count)
a = int(input())

b=0#約数の個数

for i in range(1,a+1, 2):#i:1~inputまで,奇数だけ
  #ある数Niについて約数を数える
	yakusuu_array = []

	for i in range(1,num):
	    if num % i == 0:
            yakusuu_array.append(i)
            
  	if len(yakusuu_array) == 8:
  		b += 1
print(b)

### FIXED CODE ###

a = int(input())
 
b=0#約数の個数
 
for num in range(1,a+1):#i:1~inputまで,奇数だけ
  if num % 2 == 1:
  #ある数Niについて約数を数える
    yakusuu = 0
    for i in range(1,num):
      if num % i == 0:
        yakusuu += 1
    if yakusuu == 7:
      b += 1
print(b)
t,x=map(int,input().split)
print(t/x)

### FIXED CODE ###

inp=list(map(int,input().split()))
print(inp[0]/inp[1])
a, b, n = map(int, input().split())
p = min(b, n)
if p % b == 0:
    print( int( a(p-1)/b ))
else:
    print( int(a*p/b))

### FIXED CODE ###

A,B,N = map(int, input().split())
c = min(N,B)
if c % B == 0:
    print(int(A*(c-1)/B))
else :
    print(int(A*(c)/B))
a, b = map(int, input().split())
c　= (a*b)%2
if c==0:
  print('Even')
else:
  print('Odd')


### FIXED CODE ###

# -*- coding: utf-8 -*-
a, b = map(int, input().split())
c = (a * b) % 2
if c == 0:
  print("Even")
else :
  print("Odd")
if __name__ == '__main__':
    print(int(x) ** 3)


### FIXED CODE ###

num = int(input())
print(num ** 3)
n=int(input())

import numpy as np
dist=np.full((n,n),-1,dtype=int)
for i in range(n-1):
  dist[i][i]=0
  a,b,c=map(int,input().split())
  dist[a-1][b-1]=c
  dist[b-1][a-1]=c

Q,K=map(int,input().split())
distFromK=np.full(n,-1,dtype=int)

# start from K
stack=[]
stack.append([K-1,0,-1])
while stack:
  node=stack.pop()
  num=node[0]
  d=node[1]
  parent=node[2]
  if distFromK[num]==-1:
    distFromK[num]=d
  else:
    distFromK[num]=np.minimum(d,distFromK[num])
  targets=dist[num]
  for i in range(len(targets)):
    if i==parent or i==num:
      continue
    if targets[i]==-1:
      continue
    stack.append([i,targets[i]+d,num])
    
for i in range(Q):
  x,y=map(int,input().split())
  print(distFromK[x-1]+distFromK[y-1])


### FIXED CODE ###

n=int(input())
dist=[[] for i in range(n)]
for i in range(n-1):
  a,b,c=map(int,input().split())
  dist[a-1].append([b-1,c])
  dist[b-1].append([a-1,c])  

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

INF=10**9+1
distFromK=[-1 for i in range(n)]

# start from K
stack=[]
stack.append([K-1,0,-1])
while stack:
  node=stack.pop()
  v=node[0]
  d=node[1]
  parent=node[2]
  if distFromK[v]==-1:
    distFromK[v]=d
  else:
    distFromK[v]=min(distFromK[v],d)
  targets=dist[v]
  for child in targets:
    if child[0]==parent or child[0]==v:
      continue
    stack.append([child[0],d+child[1],v])

for i in range(Q):
  x,y=map(int,input().split())
  print(distFromK[x-1]+distFromK[y-1])
n=int(input())
from decimal import Decimal as D
# A=[]
excel=[[0]*20 for i in range(50)]
query=[]
for i in range(n):
    q=input()
    q=D(q)
    q=int(q*10**9)
    num2=0 ;num5=0
    k=q
    for i in range(50):
        if k%2==0:
            k//=2
            num2+=1
        else:break
    k=q
    for i in range(20):
        if k%5==0:
            k//=5
            num5+=1
        else:break
    excel[num2][num5]+=1
    query.append([max(0,18-num2),max(0,18-num5)])

A=[[0] * 20 for i in range(50)] #累積和
for i in range(49,-1,-1):
    for j in range(19,-1,-1):
        if i==49 and j==19:
            A[i][j]=excel[i][j]
        elif i==49:
            A[i][j]=A[i][j+1]+excel[i][j]
        elif j==19:
            A[i][j]=A[i+1][j] + excel[i][j]
        else:
            A[i][j]=excel[i][j]+ A[i+1][j]+A[i][j+1]-A[i+1][j+1]

ans=0
for l in query:
    num2,num5=l
    if num2<=9 and num5<=9:
        ans+=A[num2][num5]-1
    else:a
        ans+=A[num2][num5]

#for i in range(50):
 #   print(excel[:][i] , A[:][i])
print(ans//2)


### FIXED CODE ###

n=int(input())
from decimal import Decimal as D
# A=[]
excel=[[0]*20 for i in range(50)]
query=[]
for i in range(n):
    q=input()
    q=D(q)
    q=int(q*10**9)
    num2=0 ;num5=0
    k=q
    for i in range(50):
        if k%2==0:
            k//=2
            num2+=1
        else:break
    k=q
    for i in range(20):
        if k%5==0:
            k//=5
            num5+=1
        else:break
    excel[num2][num5]+=1
    query.append([max(0,18-num2),max(0,18-num5)])

A=[[0] * 20 for i in range(50)] #累積和
for i in range(49,-1,-1):
    for j in range(19,-1,-1):
        if i==49 and j==19:
            A[i][j]=excel[i][j]
        elif i==49:
            A[i][j]=A[i][j+1]+excel[i][j]
        elif j==19:
            A[i][j]=A[i+1][j] + excel[i][j]
        else:
            A[i][j]=excel[i][j]+ A[i+1][j]+A[i][j+1]-A[i+1][j+1]

ans=0
for l in query:
    num2,num5=l
    if num2<=9 and num5<=9:
        ans+=A[num2][num5]-1
    else:
        ans+=A[num2][num5]

#for i in range(50):
 #   print(excel[:][i] , A[:][i])
print(ans//2)
#!/usr/bin/env python3
import sys
import math
import numpy as np
import heapq
from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

#### input
N, M = map(int, input().split())
A = list(map(lambda x:int(x)*(-1), input().split()))

sys.stdin = open('/dev/tty')

heapq.heapify(A)

#### functions
def discount(num_coupon):
  max = -heapq.heappop(A) / 2
  heapq.heappush(A, -max)

#### execution
# if em: embed()
for i in range(0, M):
  max = math.floor(-heapq.heappop(A) / 2)
  heapq.heappush(A, -max)

print(-sum(A))


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import math
import numpy as np
import heapq
from functools import lru_cache

args = sys.argv
if len(args) == 2:
  from IPython import embed
  em = True
else:
  em = False

#### input
N, M = map(int, input().split())
A = list(map(lambda x:int(x)*(-1), input().split()))

# sys.stdin = open('/dev/tty')

heapq.heapify(A)

#### functions
def discount(num_coupon):
  max = -heapq.heappop(A) / 2
  heapq.heappush(A, -max)

#### execution
# if em: embed()
for i in range(0, M):
  max = math.floor(-heapq.heappop(A) / 2)
  heapq.heappush(A, -max)

print(-sum(A))
N = int(input())
C = []
S = []
F = []
for i in range(N-1) :
    c,s,f = map(int,input().split())
    C.append(c)
    S.append(s)
    F.append(f)
for i in range(N) :
    if j == N-1 :
        print(0)
    else :
        ans = 0
        for j in range(i,N-1) :
            if ans < S[j] :
                ans = S[j]
            if ans % F[j] != 0 :
                ans = (ans//F[j]-1)*F[j]
            ans += C[j]
        print(ans)


### FIXED CODE ###

N = int(input())
C = []
S = []
F = []
for i in range(N-1) :
    c,s,f = map(int,input().split())
    C.append(c)
    S.append(s)
    F.append(f)
for j in range(N) :
    if j != N-1 :
        answer = 0
        for k in range(j,N-1) :
            if answer < S[k] :
                answer = S[k]
            if answer % F[k] != 0 :
                answer = (answer // F[k] + 1) * F[k]
            answer += C[k]
        print(answer)
    else :
        print(0)
N = int(input())
a = [int(i) for i in input().split()]
a = a.sort(reverse=True)

for i in range(1,N+1):
  ans = sum(a[2*i-1])
print(ans)

### FIXED CODE ###

N = int(input())
a = [int(i) for i in input().split()]
a.sort(reverse=True)

ans = sum(a[2*i-1] for i in range(1,N+1))
print(ans)
import sys
input = sys.stdin.buffer.readline
 
def main():
    t,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(x1,y2):
        return (fac[x1+y2]*pow(fac[x1],MOD-2,MOD)*pow(fac[y2],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,t)+comb(t,b))%MOD)
    
if _name_ == "_main_":
    main()
#print the result

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
 
def main():
    a,b,c,d = map(int,input().split())
    MOD = 10**9+7
    N = c+d+5
    fac = [0 for _ in range(N+1)]
    fac[0],fac[1] = 1,1
 
    for i in range(2,N+1):
        fac[i] = (fac[i-1]*i)%MOD
        
    def comb(g,h):
        return (fac[g+h]*pow(fac[g],MOD-2,MOD)*pow(fac[h],MOD-2,MOD))%MOD
 
    print((comb(c+1,d+1)-comb(c+1,b)-comb(d+1,a)+comb(a,b))%MOD)
    
if __name__ == "__main__":
    main()
def getCalc(NUM):
    sum = 0
    for i in range(len(NUM)):
        sum += i*NUM[i]


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)

max_num = max(max(A), max(B), max(C))

NUM = [0]*max_num + 1

for i in range(NUM):
    NUM[i] = A.count(i)

for i in range(Q):
    NUM[B[i]], NUM[C[i]] = 0, NUM[B[i]] + NUM[C[i]]

    print(getCalc(NUM))


### FIXED CODE ###


N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []
for i in range(Q):
    b, c = list(map(int, input().split()))
    B.append(b)
    C.append(c)

max_num = max(max(A), max(B), max(C))

NUM = [0] * (max_num + 1)

num_list = []

for a in A:
    NUM[a] += 1

total = sum(A)

for i in range(Q):

    total += (C[i] - B[i]) * NUM[B[i]]
    NUM[B[i]], NUM[C[i]] = 0, NUM[B[i]] + NUM[C[i]]

    print(total)