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

a = [1, 10, 100, 1000, 1924, 1069, 595, 1912, 949, 1414, 7, 70, 700, 943, 1354, 1426, 127, 1270, 586, 1822, 49, 490,
     862, 544, 1402, 1906, 889, 814, 64, 640, 343, 1411, 1996, 1789, 1738, 1228, 166, 1660, 448, 442, 382, 1801, 1858,
     409, 52, 520, 1162, 1525, 1117, 1075, 655, 493, 892, 844, 364, 1621, 58, 580, 1762, 1468, 547, 1432, 187, 1870,
     529, 1252, 406, 22, 220, 181, 1810, 1948, 1309, 976, 1684, 688, 823, 154, 1540, 1267, 556, 1522, 1087, 775, 1693,
     778, 1723, 1078, 685, 793, 1873, 559, 1552, 1387, 1756, 1408, 1966, 1489, 757, 1513, 997, 1894, 769, 1633, 178,
     1780, 1648, 328, 1261, 496, 922, 1144, 1345, 1336, 1246, 346, 1441, 277, 751, 1453, 397, 1951, 1339, 1276, 646,
     403, 2011, 1939, 1219, 76, 760, 1543, 1297, 856, 484, 802, 1963, 1459, 457, 532, 1282, 706, 1003, 1954, 1369, 1576,
     1627, 118, 1180, 1705, 898, 904, 964, 1564, 1507, 937, 1294, 826, 184, 1840, 229, 271, 691, 853, 454, 502, 982,
     1744, 1288, 766, 1603, 1897, 799, 1933, 1159, 1495, 817, 94, 940, 1324, 1126, 1165, 1555, 1417, 37, 370, 1681, 658,
     523, 1192, 1825, 79, 790, 1843, 259, 571, 1672, 568, 1642, 268, 661, 553, 1492, 787, 1813, 1978, 1609, 1957, 1399,
     1876, 589, 1852, 349, 1471, 577, 1732, 1168, 1585, 1717, 1018, 85, 850, 424, 202]

length = 224
mod = 2019
cont = [0 for _ in range(length)]
sums = [0 for _ in range(length)]
count = 0
s = list(map(int, input()))
n = len(s)
for i in range(n):
    m = s[n-1-i]
    for j in range(min(i + 1, length)):
        sums[j] += m * a[(i-j) % length]
        if i > j:
            sums[j] %= mod
            if i % length == j:
                if sums[j - 1] == 0:
                    cont[j] += 1
                else:
                    cont[j] = 0
            if sums[j] == 0:
                count += cont[j] + 1
print(count)

### FIXED CODE ###

s = input()
n = len(s)
table = [0 for _ in range(n + 1)]
for i in range(n):
    table[-2 - i] = (int(s[-1 - i]) * pow(10, i, 2019) + table[-1 - i]) % 2019
count = [0 for _ in range(2019)]
ans = 0
for t in table:
    if count[t] != 0:
        ans += count[t]
    count[t] += 1
print(ans)
### BUGGY CODE ###

from sys import stdin

def main():

    input = stdin.readline

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

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

    itta_list = []
    idou_num = 0

    pos = 0

    for i in range(K):
        # itta_list記憶
        if pos not in itta_list:
            itta_list.append(pos)
        else:
            idou_num = i
            break

        # 次の街へ
        pos = A[pos] - 1
    else:
        ans_num = pos + 1
        print(ans_num)
        return

    roop_list = itta_list[itta_list.index(pos):]

    amari = (K - idou_num) % len(roop_list)

    ans_pos = roop_list[amari] + 1

    print(ans_pos)

if __name__ == "__main__":
    main()

### FIXED CODE ###

from sys import stdin

def main():

    input = stdin.readline

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

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

    itta_set = set()
    itta_list = []
    idou_num = 0

    pos = 0

    for i in range(K):
        # itta_list記憶
        if pos not in itta_set:
            itta_set.add(pos)
            itta_list.append(pos)
        else:
            idou_num = i
            break

        # 次の街へ
        pos = A[pos] - 1
    else:
        ans_num = pos + 1
        print(ans_num)
        return

    roop_list = itta_list[itta_list.index(pos):]

    amari = (K - idou_num) % len(roop_list)

    ans_pos = roop_list[amari] + 1

    print(ans_pos)

if __name__ == "__main__":
    main()
### BUGGY CODE ###

def main():
  import sys
  from collections import deque
  num,capacity=map(int,input().split())
  items=deque([list(map(int,sys.stdin.readline().split())) for _ in range(num)])
  DP=[-1]*(capacity+1)
  DP[0]=0
  while(items):
    item=items.popleft()
    weight=item[0]
    value=item[1]
    left=capacity-weight
    for i in range(left,-1,-1):
      if DP[i]<0:
        continue
      DP[i+weight]=max(DP[i]+value,DP[i+weight])
  print(max(DP))
      
if __name__=="__main__":
  main()

### FIXED CODE ###

n,w=map(int,input().split())
goods=[list(map(int,input().split())) for _ in range(n)]
DP=[[0]*(w+1) for _ in range(n+1)]
for i in list(range(n))[::-1]:
  wi,vi=goods[i][0],goods[i][1]
  for j in range(w+1):
    if j<wi:
      DP[i][j]=DP[i+1][j]
    else:
      DP[i][j]=max(DP[i+1][j],DP[i+1][j-wi]+vi)
print(DP[0][w])
### BUGGY CODE ###

s = input()
maxi = 0

for i in range(len(s)):
    if s[i] == 'A':
        for j in range(i, len(s)):
            if s[j] == 'Z' and j-i+1 > maxi:
                maxi = j-i+1

print(maxi)

### FIXED CODE ###

s = list(input())

while s[0] != 'A' or s[-1] != 'Z':
    if s[0] == 'A':
        s.pop()
    elif s[-1] == 'Z':
        s.pop(0)
    else:
        s.pop(0)
        s.pop()

print(len(s))
### BUGGY CODE ###

import sys
import math
import itertools as it
def i():return int(sys.stdin.readline().replace("\n",""))
def i2():return map(int,sys.stdin.readline().replace("\n","").split())
def s():return str(sys.stdin.readline().replace("\n",""))
def l():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def lx():return list(map(lambda x:int(x)*-1,sys.stdin.readline().replace("\n","").split()))
def t():return tuple(map(int,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":pass
n = i()
s = [input() for _ in range(n)]
s.sort()
ss = list(set(s))
ss.sort()
a = [0]*len(ss)
i = 0
while n-1 > i:
    if s[i] == s[i+1]:
        a[ss.index(s[i])] += 1
        i += 1
    else:
        i += 1
m = max(a)
for k in range(len(a)):
    if a[k] == m:
        print(ss[k])


### FIXED CODE ###

import sys
import math
import itertools as it
def i():return int(sys.stdin.readline().replace("\n",""))
def i2():return map(int,sys.stdin.readline().replace("\n","").split())
def s():return str(sys.stdin.readline().replace("\n",""))
def l():return list(sys.stdin.readline().replace("\n",""))
def intl():return [int(k) for k in sys.stdin.readline().replace("\n","").split()]
def lx():return list(map(lambda x:int(x)*-1,sys.stdin.readline().replace("\n","").split()))
def t():return tuple(map(int,sys.stdin.readline().replace("\n","").split()))

if __name__ == "__main__":pass
n = i()
s = [input() for _ in range(n)]
s.sort()
ss = list(set(s))
ss.sort()
a = [0]*len(ss)
i = 0
j = 0
while n-1 > i:
    if s[i] == s[i+1]:
        a[j] += 1
        i += 1
    else:
        i += 1
        j += 1
m = max(a)
for k in range(len(a)):
    if m == a[k]:
        print(ss[k])
### BUGGY CODE ###

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
from functools import lru_cache
INF = float("inf")
import sys
sys.setrecursionlimit(10000)

a = []
@lru_cache(None)
def dfs(no, i, Z, W):
    global a
    if i >= len(a):
        return abs(Z - W)

    # X
    if no % 2 == 0:
        ans = 0
        for j in range(i, len(a)):
            ans = max(ans, dfs(1 - no, j + 1, a[j], W))
        return ans
    # Y
    else:
        ans = INF
        for j in range(i, len(a)):
            ans = min(ans, dfs(1 - no, j + 1, Z, a[j]))
        return ans


def solve2(N, Z, W):
    return dfs(0, 0, Z, W)


def solve(N, Z, W):
    global a
    ans = abs(a[-1] - W)
    if len(a) > 1:
        ans = max(ans, abs(a[-2] - a[-1]))
    return ans


def main():
    global a
    N, Z, W = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve2(N, Z, W))


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
from string import ascii_lowercase
INF = float("inf")
import sys
sys.setrecursionlimit(10000)


def solve(N, Z, W, a):
    ans = abs(a[-1] - W)
    if len(a) > 1:
        ans = max(ans, abs(a[-2] - a[-1]))
    return ans


def main():
    N, Z, W = map(int, input().split())
    a = list(map(int, input().split()))
    print(solve(N, Z, W, a))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

from collections import deque
N = int(input())
S = list(input())
R = deque()
G = deque()
B = deque()
for i in range(N):
    if S[i] == "R":
        R.append(i)
    elif S[i] == "G":
        G.append(i)
    elif S[i] == "B":
        B.append(i)
count = 0


for a in R:
    for b in G:
        for c in B:
            num = [a, b, c]
            num.sort()
            if num[1] - num[0] != num[2] - num[1]:
                count += 1
print(count)

### FIXED CODE ###

N = int(input())
S = list(input())
R = []
G = []
B = []
Reval = {}
Geval = {}
Beval = {}
for i in range(N):
    if S[i] == "R":
        R.append(i)
        Reval[2*i] = 2*i
    elif S[i] == "G":
        G.append(i)
        Geval[2*i] = 2*i
    elif S[i] == "B":
        B.append(i)
        Beval[2*i] = 2*i
count = len(R)*len(G)*len(B)

for a in R:
    for b in G:
        if (a + b) in Beval:
            count -= 1
for a in G:
    for b in B:
        if (a + b) in Reval:
            count -= 1
for a in B:
    for b in R:
        if (a + b) in Geval:
            count -= 1
print(count)
### BUGGY CODE ###

n = int(input())
s = [input() for _ in range(n)]

l = []
c=0
for i in s:
    if i not in l:
        l.append(i)
        c+=1
print(c)

### FIXED CODE ###

n = int(input())
s = [input() for _ in range(n)]

import collections

c = collections.Counter(s)

print(len(c.keys()))
### BUGGY CODE ###

N,H=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N)]
B=[]
C=[]
for a,b in A:
  B.append(a)
  C.append(b)
D=sorted(B)[::-1]
F=[]
for i in C:
  if max(B)<i:
    F.append(i)
cnt=0
for i in F:
  H-=i
  cnt+=1
  if H<=0:
    print(cnt)
    exit()
print(cnt-((-H)//D[0]))
    

### FIXED CODE ###

N,H=map(int,input().split())
A=[list(map(int,input().split())) for i in range(N)]
B=[]
C=[]
for a,b in A:
  B.append(a)
  C.append(b)
D=sorted(B)[::-1]
b=D[0]
F=[]
for i in C:
  if b<i:
    F.append(i)
G=sorted(F)[::-1]
cnt=0
for i in G:
  H-=i
  cnt+=1
  if H<=0:
    print(cnt)
    exit()
print(cnt-((-H)//b))
### BUGGY CODE ###

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

def ver(i, j, length):
    for f in range(length):
        if S[i+f] != S[j+f]: return False
    return True

def check(length):
    for i in range(N):
        for j in range(i+length, N-length+1):
            if ver(i, j, length): return True
    return False

def binarySearch(lo, hi):
    if lo >= hi:
        return lo
    mid = lo + (hi - lo + 1) // 2
    if check(mid):
        return binarySearch(mid, hi)
    else:
        return binarySearch(lo, mid - 1)

print(binarySearch(0, N//2))


### FIXED CODE ###

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

def z_advanced(s):
    # Taken from https://ivanyu.me/blog/2013/10/15/z-algorithm/
    """An advanced computation of Z-values of a string."""
 
    Z = [0] * len(s)
    Z[0] = len(s)
 
    rt = 0
    lt = 0
 
    for k in range(1, len(s)):
        if k > rt:
            # If k is outside the current Z-box, do naive computation.
            n = 0
            while n + k < len(s) and s[n] == s[n+k]:
                n += 1
            Z[k] = n
            if n > 0:
                lt = k
                rt = k+n-1
        else:
            # If k is inside the current Z-box, consider two cases.
 
            p = k - lt  # Pair index.
            right_part_len = rt - k + 1
 
            if Z[p] < right_part_len:
                Z[k] = Z[p]
            else:
                i = rt + 1
                while i < len(s) and s[i] == s[i - k]:
                    i += 1
                Z[k] = i - k
 
                lt = k
                rt = i - 1
    return Z

best = 0
for i in range(N):
    lst = z_advanced(S[i:])
    for j, longest in enumerate(lst):
        best = max(best, min(j, longest))
print(best)
### BUGGY CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


def main():
    n = I()
    a = LI()
    if a[-1] != 2:
        return -1
    b = 2
    c = 4
    for i in range(n-2,-1,-1):
        t = a[i]
        if b * 2 <= t:
            return -1
        if b % t == 0:
            pass
        elif b > t:
            b += t-b%t
        else:
            b = t
        if c % t == 0:
            pass
        elif c > t:
            c += t-c%t
        else:
            return -1
    bb = b
    cc = c-1
    while True:
        bb = b
        for i in range(n):
            bb -= bb%a[i]
        if bb != 2:
            b += a[0]
        else:
            break
    for i in range(n):
        cc -= cc%a[i]
    if cc != 2:
        while 1:
            cc += 1

    return '{} {}'.format(b, c-1)

print(main())




### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)

# 下がtrue, falseになる最小値を返す
def bs(f, mi, ma):
    mm = -1
    while ma > mi:
        mm = (ma+mi) // 2
        if f(mm):
            mi = mm + 1
        else:
            ma = mm
    if f(mm):
        return mm + 1
    return mm

def main():
    n = I()
    a = LI()

    def f(i):
        for c in a:
            i -= i%c
        return i < 2

    def g(i):
        for c in a:
            i -= i%c
        return i <= 2

    mi = bs(f,0,sum(a)+3)
    ma = bs(g,0,sum(a)+3) - 1
    if mi <= ma:
        return '{} {}'.format(mi,ma)
    return -1




print(main())
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        for k in range(j+1, n):
            if l[i]+l[j] > l[k]:
                ans += 1
print(ans)


### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0

for i in range(n-2):
    for j in range(i+1, n-1):
        idx = bisect.bisect_right(l, l[i]+l[j]-1, j+1)
        ans+=idx-(j+1)
print(ans)
### BUGGY CODE ###

s=input()
n=len(s)
sn=[0]*n
x=pow(10,n-1)
for i in range(n):
    sn[i]=(int(s[i])*x)%2019
    x=x//10
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-sn[i-1]
    t[i]%=2019
t.sort()
t2=sorted(list(set(t)))
tcnt=[0]*len(t2)
f=0
for i in range(n+1):
    if t2[f]==t[i]:
        tcnt[f]+=1
    else:
        f+=1
        tcnt[f]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)


### FIXED CODE ###

s=input()
n=len(s)
s_int=[0]*n
x=(pow(10,n-1))%2019
for i in range(n):
    s_int[i]=(int(s[i])*x)%2019
    x=(x*202)%2019
t=[0]*(n+1)
t[0]=int(s)%2019
for i in range(1,n):
    t[i]=t[i-1]-s_int[i-1]
    t[i]%=2019
t.sort()
t_set=sorted(list(set(t)))
tcnt=[0]*len(t_set)
num=0
for i in range(n+1):
    if t_set[num]==t[i]:
        tcnt[num]+=1
    else:
        num+=1
        tcnt[num]+=1
sum=0
for i in range(len(tcnt)):
    sum+=(tcnt[i]*(tcnt[i]-1))//2
print(sum)
### BUGGY CODE ###

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

for i in range(N):
    x = sorted(X)
    x.remove(X[i])
    print(x[-N // 2])

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
x = sorted(X)
a = x[-(N // 2) - 1]
b = x[-(N // 2)]

for i in X:
    if i <= a:
        print(b)
    else:
        print(a)
### BUGGY CODE ###

N=int(input())
L=list(map(int, input().split()))
L.sort()
L.reverse()
a=L.pop(0)
count=0
while(L!=[]):
    for i in range(len(L)):
        for j in range(i+1,len(L)):
            if a < L[i]+L[j]:
                count+=1
    a=L.pop(0)
print(count)


### FIXED CODE ###

import bisect

N=int(input())
L=list(map(int, input().split()))
ll=len(L)
L.sort()

s=0
for i in range(ll):
    for j in range(i+1,ll):
        s+=bisect.bisect_right(L,L[i]+L[j]-1)-j-1

print(s)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
N=int(sys.stdin.readline())
H=list(map(int,sys.stdin.readline().split()))

dp=[0]*N
def rec(i):
    if dp[i]:
        return dp[i]
    if i==N-1:
        return 0
    elif i==N-2:
        return abs(H[i]-H[i+1])

    o=min(rec(i+1)+abs(H[i]-H[i+1]),rec(i+2)+abs(H[i]-H[i+2]))
    dp[i]=o
    return o
print(rec(0))


### FIXED CODE ###

import sys
N=int(sys.stdin.readline())
H=list(map(int,sys.stdin.readline().split()))

dp=[0]*N

dp[1]=abs(H[0]-H[1])
for i in range(2,N):
    dp[i]=min(dp[i-1]+abs(H[i-1]-H[i]),dp[i-2]+abs(H[i-2]-H[i]))
print(dp[-1])
### BUGGY CODE ###

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

dp = [0]*N
for i in range(1,N):
    start = max(0,i-K)
    dp[i] = min([dp[j] + abs(h[j]-h[i]) for j in range(start,i)])
print(dp[-1])

### FIXED CODE ###

def calc_dp():
    N, K = map(int, input().split())
    h = list(map(int, input().split()))

    dp = [0]*N
    for i in range(1,N):
        start = max(0,i-K)
        dp[i] = min([dp[j] + abs(h[j]-h[i]) for j in range(start,i)])
    print(dp[-1])

if __name__ == "__main__":
    calc_dp()
### BUGGY CODE ###

import sys
sy = sys.stdin.readlines()
N,Q = map(int, sy[0].split())
S = sy[1]

for i, sy_list in enumerate(sy):
  if i >= 2:
    l, r = map(int, sy_list.split())
    s = S[l-1:r]
    print(s.count('AC'))

### FIXED CODE ###

import sys
sy = sys.stdin.readlines()
N,Q = map(int, sy[0].split())
S = sy[1]
ACindex = [0 for _ in range(N+1)]
count = 0
for n in range(1, N):
  if S[n-1]=="A" and S[n]=="C":
    count += 1
  ACindex[n+1] = count

for i in range(Q):
  l, r = map(int, sy[2+i].split())
  print(ACindex[r]-ACindex[l])
### BUGGY CODE ###

import math
K = int(input())
sum = 0
for i in range(1,K+1):
  for j in range(1, K+1):
    for k in range(1, K+1):
      sum += math.gcd(k, math.gcd(i, j))
print(sum)


### FIXED CODE ###

from math import gcd

k = int(input())
sum = 0

for a in range(1, k + 1):
    for b in range(1, k + 1):
        for c in range(1, k + 1):
            sum += gcd(c, gcd(a, b))
print(sum)
### BUGGY CODE ###

N = int(input())
AList = list(map(int, input().split()))
divider = 10**9 + 7
count = 0

for i in range(N-1) :
    for j in range(i+1,N) :
        count += AList[i]^AList[j]
print(count%divider)

### FIXED CODE ###

import numpy as np
 
N = int(input())
A = np.fromiter(map(int, input().split()), np.int64)
 
result = 0
for bit in range(60):
    c = int((A & 1).sum())
    result = (result + c * (N - c) * (1 << bit)) % 1000000007
    A >>= 1
print(result)
### BUGGY CODE ###

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

total_list = []
count = 0
for i in range(int(10e100)):
    for i in range(A):
        total_list.append("b")
        if len(total_list) <= N:
            count += 1
    for i in range(B):
        total_list.append("r")
    if len(total_list) >= N:
        break

print(count)

### FIXED CODE ###

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

amari = N % (A + B)
sho = N // (A + B)

blue_num = 0

if amari < A:
    blue_num += A * sho + amari
else:
    blue_num += A * sho + A

print(blue_num)
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
import collections
c = collections.Counter(A)
ans = 0
while len(c) > K:
    n = c.most_common()[-1][0]
    ans += c[n]
    del c[n]
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
import collections
c = collections.Counter(A)
print(N - sum([pair[1] for pair in c.most_common(K)]))
### BUGGY CODE ###

from functools import reduce
MOD = 10**9+7
n = int(input())
A = list(map(int, input().split()))


def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a % b)


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

  
x = reduce(lcm, A)
print(sum(x//a % MOD for a in A) % MOD)

### FIXED CODE ###

from collections import defaultdict
MOD = 10**9+7
n = int(input())
A = list(map(int, input().split()))


def factorization(n):
    retval = []
    tmp = n
    for i in range(2, int(-(-n**.5//1))+1):
        if tmp % i == 0:
            cnt = 0
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            retval.append((i, cnt))
    if tmp != 1:
        retval.append((tmp, 1))
    return retval


x = defaultdict(int)
for a in A:
    for p, q in factorization(a):
        if x[p] < q:
            x[p] = q

mod_x = 1
for p, q in x.items():
    mod_x *= pow(p, q, MOD)
mod_x %= MOD

B = [mod_x*pow(a, MOD-2, MOD) % MOD for a in A]
print(sum(B) % MOD)
### BUGGY CODE ###

N, M = map(int, input().split())
A = [int(x) for x in input().split()]

for i in range(M):
    A[A.index(max(A))] = A[A.index(max(A))]//2
print(sum(A))

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = [-int(x) for x in input().split()]

heapq.heapify(A)
for i in range(M):
    heapq.heappush(A,-(-heapq.heappop(A)//2))
                   
print(-sum(A))
### BUGGY CODE ###

H, W = map(int, input().split())
dist_matrix = [[-1] * W for i in range(H)]
queue = []
for i in range(H):
  line_list = list(input())
  black_index_list = [i for i, x in enumerate(line_list) if x == '#']
  for j in black_index_list:
    dist_matrix[i][j] = 0
    queue.append([i,j])
  #for j in range(W):
  #  if line_list[j] == "#":  
  #    dist_matrix[i][j] = 0
  #    queue.append([i,j])

#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  i,j = queue.pop(0)
  max_value = dist_matrix[i][j]
  #cnt += 1
  if i > 0 and dist_matrix[i-1][j] == -1:
    dist_matrix[i-1][j] = max_value + 1
    queue.append([i-1,j])
  if i < H-1 and dist_matrix[i+1][j] == -1:
    dist_matrix[i+1][j] = max_value + 1
    queue.append([i+1,j])
  if j > 0 and dist_matrix[i][j-1] == -1:
    dist_matrix[i][j-1] = max_value + 1
    queue.append([i,j-1])
  if j < W-1 and dist_matrix[i][j+1] == -1:
    dist_matrix[i][j+1] = max_value + 1
    queue.append([i,j+1])

#print(cnt)
#print(dist_matrix)
print(max_value)

### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline
 
H, W = map(int, input().split())
mark_matrix = [[True]*(W+2)]
#mark_matrix.extend([[True]+[False]*(W)+[True] for _ in range(H)])
mark_matrix.extend([[True]+[x!='.' for x in input()] for _ in range(H)])
mark_matrix[H].append(True)
mark_matrix.append([True]*(W+2))
#queue = []
queue = deque()
for i in range(1,H+1):
  for j in range(1,W+1):
    if mark_matrix[i][j]:
      queue.append((i,j))
#  line = input()
#  for j,ch in enumerate(line):
#    if ch == "#":
#      mark_matrix[i+1][j+1] = True
#      queue.append((i+1,j+1))
#for i in range(1,H+1):
#  mark_matrix[i][0] = True
#  mark_matrix[i][W+1] = True
#for j in range(W+2):
#  mark_matrix[0][j] = True
#  mark_matrix[H+1][j] = True
#print(mark_matrix)
 
#cnt = 0
#print(queue)
max_value = 0
while(True):
  #print(len(queue))
  if len(queue) == 0:
    break
  
  new_queue = deque()
  for i,j in queue:
  
    if not mark_matrix[i-1][j]:
      mark_matrix[i-1][j] = True
      #queue.append((i-1,j))
      new_queue.append((i-1,j))
    if not mark_matrix[i+1][j]:
      mark_matrix[i+1][j] = True
      #queue.append((i+1,j))
      new_queue.append((i+1,j))
    if not mark_matrix[i][j-1]:
      mark_matrix[i][j-1] = True
      #queue.append((i,j-1))
      new_queue.append((i,j-1))
    if not mark_matrix[i][j+1]:
      mark_matrix[i][j+1] = True
      #queue.append((i,j+1))
      new_queue.append((i,j+1))
 
  if len(new_queue) == 0:
    break
  else:
    queue = new_queue
    max_value += 1
  
#print(cnt)
#print(dist_matrix)
print(max_value)