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

import sys
import math
import fractions
import bisect
import queue
import heapq
import collections
import itertools
sys.setrecursionlimit(4100000)

MOD = int(1e9+7)
PI = 3.14159265358979323846264338327950288
INF = 1e18

'''
1行のint=====================================
N, K = map(int, input().split())
N, M = map(int, input().split())
A, B = map(int, input().split())

H, W = map(int, input().split())

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

1行のstring=================================
S, T = input().split()

1行の整数配列================================
P = list(map(int,input().split()))

A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
D = list(map(int,input().split()))

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

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

改行あり整数==================================
X = []
Y = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    X.append(x1)
    Y.append(y1)

A = []
for i in range(N):
    a=int(input())
    A.append(a)

Pair = []
for i in range(N):
    x1,y1=[int(i) for i in input().split()]
    Pair.append((x1, y1))
    
2次元整数配列=====================================
A = []
for i in range(N):
    tmp = list(map(int,input().split()))
    A.append(tmp)


N行M列の初期化====================================
dp = [[VAL] * RETU for i in range(GYO)]

'''

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

common1 = 1
for a in A[:len(A)// 4]:
    common1 = common1 * a // math.gcd(common1, a)


common2 = 1
for a in A[len(A)// 4: (len(A)// 4) * 2]:
    common2 = common2 * a // math.gcd(common2, a)

common3 = 1
for a in A[(len(A)// 4) * 2: (len(A)// 4) * 3]:
    common3 = common3 * a // math.gcd(common3, a)


common4 = 1
for a in A[(len(A)// 4) * 3 :]:
    common4 = common4 * a // math.gcd(common4, a)


common = common1 * common2 // math.gcd(common1, common2)
common = common * common3 // math.gcd(common, common3)
common = common * common4 // math.gcd(common, common4)

ans = 0
for a in A:
    ans += common // a
    ans %= MOD

print(ans)




### FIXED CODE ###

import sys
sys.setrecursionlimit(4100000)
import math




N = int(input())


import fractions
a = list(map(int, input().split()))
koubai = a[0]
small = []
for i in range(0, N//2):
    small.append(a[2*i + 1] * a[2*i] // fractions.gcd(a[2*i + 1], a[2*i]))

small.append(a[-1])
for i in range(len(small)):
    koubai = koubai * small[i] // fractions.gcd(koubai, small[i])


ans = int(0)
for i in range(N):
    ans += koubai // a[i]
    
ans %= 1000000007

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

n = int(input())

class cell:
    def __init__(self, data, before, _next):
        self.data = data
        self.before = before
        self._next = _next

def search(ddl, data):
    for ind,item in enumerate(ddl):
        if item.data == data:
            return ind
    return None

def getItem(ddl, index):
    if len(ddl) > index and index >= 0:
        return ddl[index]
    return None

ddl = []
for i in range(n):
    inp = input().split()
    if len(inp) == 2:
        op, data = inp
        data = int(data)
    else: op, data = inp[0], None
    if op == 'insert':
        if len(ddl) == 0:
            _next = None
        else:
            _next = ddl[0]
        c = cell(data, None, _next)
        ddl = [c] + ddl
    elif op == 'delete':
        ind = search(ddl, data)
        if ind != None:
            ddl[ind - 1].next = getItem(ddl, ind + 1)
            if getItem(ddl, ind+1) is not None:
                ddl[ind + 1].prev = getItem(ddl, ind - 1)
            ddl = ddl[:ind] + ddl[ind+1:]
    elif op == 'deleteFirst':
        ddl = ddl[1:]
        if len(ddl) != 0:
            ddl[0].prev = None
    elif op == 'deleteLast':
        ddl = ddl[:-1]
        if len(ddl) != 0:
         ddl[-1]._next = None

print(' '.join([str(item.data) for item in ddl]))

### FIXED CODE ###

from collections import deque
from sys import stdin
n = int(input())
line = stdin.readlines()
ddl = deque()
for i in range(n):
    inp = line[i].split()
    if len(inp) == 2:
        op, data = inp
        data = int(data)
    else: op, data = inp[0], None
    if op == 'insert':
        ddl.appendleft(data,)
    elif op == 'delete':
        try:
            ddl.remove(data)
        except ValueError:
            pass
    elif op == 'deleteFirst':
        ddl.popleft()
    elif op == 'deleteLast':
        ddl.pop()

print(' '.join([str(item) for item in ddl]))
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range((N // R) + 1):
    for g in range((N // G) + 1):
        V = r * R + g * G 
        if N >= V and (N - V) % B == 0:
            cnt += 1
print(cnt)


### FIXED CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range((N // R) + 1):
    for g in range((N - (r * R)) // G + 1):
        V = N - (r * R + g * G)
        if V >= 0 and V % B == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

s = input()
n = len(s)
p = 10 ** 9 + 7
 
q = s.count('?')
l_a = [0] * n  # l_a[i] := s[i]より左にあるAの数
l_x = [0] * n  # l_x[i] := s[i]より左にある?の数
r_c = [0] * n  # r_c[i] := s[i]より右にあるCの数
r_x = [0] * n  # r_x[i] := s[i]より右にある?の数
 
for i in range(1, n):  # 1〜n-1
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')
 
ans = 0
for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * (3 ** q % p) % p       # ABC
        if q >= 1:
            ans += (l_x[i] * r_c[i] % p) * (3 ** (q - 1) % p) % p # ?BC
            ans += (l_a[i] * r_x[i] % p) * (3 ** (q - 1) % p) % p # AB?
        if q >= 2:
            ans += (l_x[i] * r_x[i] % p) * (3 ** (q - 2) % p) % p # ?B?
        ans %= p
    elif s[i] == '?':
        if q >= 1:
            ans += (l_a[i] * r_c[i] % p) * (3 ** (q - 1) % p) % p # A?C
        if q >= 2:
            ans += (l_x[i] * r_c[i] % p) * (3 ** (q - 2) % p) % p # ??C
            ans += (l_a[i] * r_x[i] % p) * (3 ** (q - 2) % p) % p # A??
        if q >= 3:
            ans += (l_x[i] * r_x[i] % p) * (3 ** (q - 3) % p) % p # ???
        ans %= p
 
print(ans)

### FIXED CODE ###

s = input()
n = len(s)
p = 10 ** 9 + 7

q = s.count('?')
l_a = [0] * n  # l_a[i] := s[i]より左にあるAの数
l_x = [0] * n  # l_x[i] := s[i]より左にある?の数
r_c = [0] * n  # r_c[i] := s[i]より右にあるCの数
r_x = [0] * n  # r_x[i] := s[i]より右にある?の数

for i in range(1, n):  # 1〜n-1
    l_a[i] = l_a[i - 1] + int(s[i - 1] == 'A')
    l_x[i] = l_x[i - 1] + int(s[i - 1] == '?')
    r_c[n - i - 1] = r_c[n - i] + int(s[n - i] == 'C')
    r_x[n - i - 1] = r_x[n - i] + int(s[n - i] == '?')

ans = 0
pow_q = []
for i in range(0, 4):
    pow_q.append(max(1, 3 ** (q - i) % p))

for i in range(n):
    if s[i] == 'B':
        ans += (l_a[i] * r_c[i] % p) * pow_q[0] % p  # ABC
        ans += (l_x[i] * r_c[i] % p) * pow_q[1] % p # ?BC
        ans += (l_a[i] * r_x[i] % p) * pow_q[1] % p # AB?
        ans += (l_x[i] * r_x[i] % p) * pow_q[2] % p # ?B?
        ans %= p
    elif s[i] == '?':
        ans += (l_a[i] * r_c[i] % p) * pow_q[1] % p # A?C
        ans += (l_x[i] * r_c[i] % p) * pow_q[2] % p # ??C
        ans += (l_a[i] * r_x[i] % p) * pow_q[2] % p # A??
        ans += (l_x[i] * r_x[i] % p) * pow_q[3] % p # ???
        ans %= p

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

N, P = map(int, input().split())
S = input()
if 10 % P == 0:
    ans = 0
    for r in range(N):
        if int(S[r]) % P == 0:
            ans += r + 1
    print(ans)
    exit()

d = [0] * (N + 1)
ten = 1
for i in range(N - 1, -1, -1):
    a = int(S[i]) * ten % P
    d[i] = (d[i + 1] + a) % P
    ten *= 10
    # ten %= P

cnt = [0] * P
ans = 0
for i in range(N, -1, -1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1
print(ans)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()
if 10 % P == 0:
    ans = 0
    for r in range(N):
        if int(S[r]) % P == 0:
            ans += r + 1
    print(ans)
    exit()

d = [0] * (N + 1)
ten = 1
for i in range(N - 1, -1, -1):
    a = int(S[i]) * ten % P
    d[i] = (d[i + 1] + a) % P
    ten *= 10
    ten %= P

cnt = [0] * P
ans = 0
for i in range(N, -1, -1):
    ans += cnt[d[i]]
    cnt[d[i]] += 1
print(ans)
### BUGGY CODE ###

# a, b, k = map(int, input().split())
s = input()

n = len(s)


def rep(str):
    str = str.replace('01', '')
    str = str.replace('10', '')
    return str


input_str = s
ret = None

while ret is None or input_str != ret:
    ret = input_str
    input_str = rep(input_str)

print(n - len(ret))


### FIXED CODE ###


s = input()

n = len(s)

cnt0 = s.count('0')
cnt1 = s.count('1')

print(min(cnt0, cnt1)*2)
### BUGGY CODE ###

N = int(input())

i = 2
while True:
    if i % N == 0:
        print(i)
        break
    i += 2

### FIXED CODE ###

N = int(input())
if N % 2 != 0:
    print(2 * N)
else:
    print(N)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200005)

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

to = [[] for i in range(n)]


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

score = [0]*n

for i in range(q):
    p, x = map(int, input().split())
    score[p-1] += x


def down_tree(index, parent=-1):
    global score
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)
    return


down_tree(0)

for i in range(len(score)):
	print(score[i])


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(200005)
n, q = map(int, input().split())

to = [[] for i in range(n+1)]


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

score = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    score[p] += x


def down_tree(index, parent):
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)



down_tree(1, 1)

print(' '.join(map(str, score[1:])))
### BUGGY CODE ###

def warshall_floyd(G):
    inf = 10**18
    # 重みつきグラフGに対してすべての頂点対の距離を求める
    n = len(G)
    d = [[inf for i in range(n)] for j in range(n)]
    for i in range(n):
        d[i][i] = 0
        for j in G[i].keys():
            d[i][j] = G[i][j]
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j], d[i][k]+d[k][j])
    return d


n, m, l = map(int, input().split())
G = [{} for i in range(n)]
for j in range(m):
    a, b, c = map(int, input().split())
    G[a-1][b-1] = c
    G[b-1][a-1] = c
D = warshall_floyd(G)
G = [{} for i in range(n)]
for i in range(n):
    for j in range(n):
        if D[i][j] <= l:
            G[i][j] = 1
D = warshall_floyd(G)
for k in range(int(input())):
    s, t = map(int, input().split())
    if D[s-1][t-1] > 10**10:
        print(-1)
    else:
        print(D[s-1][t-1]-1)


### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall
N,M,L=map(int,input().split())
inf=10**9+1

distance=[[inf for n in range(N)] for n in range(N)]
for n in range(N):
    distance[n][n]=0
for m in range(M):
    a,b,c=map(int,input().split())
    distance[a-1][b-1]=c
    distance[b-1][a-1]=c
distance=floyd_warshall(distance)

distance2=[[inf for n in range(N)] for n in range(N)]
for i in range(N):
    for j in range(N):
        if distance[i][j]<=L:
            distance2[i][j]=1
for n in range(N):
    distance2[n][n]=0
distance2=floyd_warshall(distance2)

Q=int(input())
for q in range(Q):
    s,t=map(int,input().split())
    if distance2[s-1][t-1]==inf:
        print(-1)
    else:
        print(int(distance2[s-1][t-1]-1))
### BUGGY CODE ###

def pri(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i=i+1
    return 1

l=[]
for i in range(2,50100):
    if pri(i):
        l.append(i)
s=5143
while 1:
    n=int(raw_input())
    ans=set([])
    if n==0:
        break
    for i in range(s):
        for j in range(i,s):
            if l[i]+l[j]==n:
                ans.add((min(l[i],l[j]),max(l[i],l[j])))
            elif l[i]+l[j]>n:
                break
    print len(ans)

### FIXED CODE ###

def pri(t):
    i=2
    while i**2<=t:
        if t%i==0:
            return 0
        i=i+1
    return 1

l=[]
for i in range(2,50000):
    if pri(i):
        l.append(i)
s=5133
ans={}
for i in range(5132):
    for j in range(i,5133):
        a,b=l[i],l[j]
        if a+b>50000:
            break
        if ans.has_key(a+b):
            ans[a+b]+=1
        else:
            ans[a+b]=1
while 1:
    n=int(raw_input())
    if n==0:
        break
    print ans[n] if ans.has_key(n) else 0
### BUGGY CODE ###

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

L = []
R = []
LR = [int(i) for i in range(1, N+1)]
for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)
    LR.append(l)
    LR.append(r)

tmp = []
for gate in range(1, M+1):
    for i in range(L[gate-1], R[gate-1]+1):
        tmp.append(i)
    tmpLR = list(set(tmp) & set(LR))
    LR.clear()
    LR = tmpLR
    tmp.clear()

print(len(LR))

### FIXED CODE ###


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

L = []
R = []

for i in range(M):
    l, r = map(int, input().split())
    L.append(l)
    R.append(r)

maxl = max(L)
minr = min(R)

ans = minr - maxl + 1
if ans > 0:
    print(ans)
else:
    print(0)
### BUGGY CODE ###

n,m=list(map(int,input().split()))
ret=1
for i in range(2,int(m/n)+1):
  if m%i == 0:
    ret = i
print(ret)

### FIXED CODE ###

n,m=list(map(int,input().split()))
d=[i for i in range(1,int(m**0.5)+1) if m%i==0]
d.extend([m//i for i in d])
print(max([i for i in d if m//i >= n]))
### BUGGY CODE ###

n = int(input())
memo1 = 0
memo2 = 0
ans = 0
stra = ""
strb = ""
str1 = ""
str2 = ""

for a in range(1,10):
    for b in range(1,10):
        stra = str(a)
        strb = str(b)
        for i in range(1, n+1):
            str1 = str(i)[0]
            str2 = str(i)[-1]
            if str1 == stra and str2 == strb:
                memo1 += 1
            if str1 == strb and str2 == stra:
                memo2 += 1
        ans += memo1 * memo2
        memo1 = 0
        memo2 = 0



print(ans)

### FIXED CODE ###

n = int(input())
memo1 = 0
memo2 = 0
ans = 0
stra = ""
strb = ""
str1 = ""
str2 = ""

for a in range(1,10):
    for b in range(1,10):
        stra = str(a)
        strb = str(b)
        for i in range(1, n+1):
            str1 = str(i)[0]
            str2 = str(i)[-1]
            if str1 == stra and str2 == strb:
                memo1 += 1
            if str1 == strb and str2 == stra:
                memo2 += 1
        ans += memo1 * memo2
        memo1 = 0
        memo2 = 0



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

import itertools

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

R = []
G = []
B = []
for i in range(len(S)):
    if S[i] == 'R':
        R.append(i)
    elif S[i] == 'G':
        G.append(i)
    else:
        B.append(i)

total = 0
for r, g, b in itertools.product(R, G, B):
    i = min([r, g, b])
    k = max([r, g, b])
    j = sum([r, g, b]) - i - k
    if j - i != k - j:
        total += 1

print(str(total))

### FIXED CODE ###

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

r = 0
g = 0
b = 0
for i in range(N):
    if S[i] == 'R':
        r += 1
    elif S[i] == 'G':
        g += 1
    else:
        b += 1

total = r * g * b
for i in range(N):
    for d in range(N):
        j = i + d
        k = j + d
        if k > N-1:
            break
        if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
            total -= 1

print(total)
### BUGGY CODE ###

N = int(input())
c = list(input())


ans = 0

if c.count("R")==0 or c.count("W") == 0:
    ans = 0
for n in range (N):
    left_W = c[:n].count("W")
    right_R = c[n:].count("R")
    if left_W == right_R:
        ans = right_R
        break
print(ans)

    

### FIXED CODE ###

N = int(input())
c = list(input())


ans = 0
left_W = 0
right_R =c.count("R")

if c.count("R")==0 or c.count("W") == 0:
    ans = 0
for n in range (N):
    if c[n] == "R":
        right_R -= 1
    else:
        left_W += 1


    if left_W == right_R:
        ans = right_R
        break
print(ans)
### BUGGY CODE ###

# from math import gcd
from fractions import gcd
from functools import reduce

n = int(input())
a = [int(x) for x in input().split()]

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

lcm = lcm_list(a)
aa = []
for i in range(len(a)):
    aa.append(lcm // a[i])
ans = sum(aa) % 1000000007
print(ans)

### FIXED CODE ###

# from math import gcd
from fractions import gcd
from functools import reduce

def lcm_list(numbers):
    return reduce(lambda x, y: (x * y) // gcd(x, y), numbers, 1)

def main():
    n = int(input())
    a = [int(x) for x in input().split()]
    lcm = lcm_list(a)
    aa = []
    for i in range(len(a)):
        aa.append(lcm // a[i])
    ans = sum(aa) % 1000000007
    print(ans)

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

N = int(input())
A = list(map(int,input().split()))
As = [[0]*N for _ in range(N-1)]
As[0] = A

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


for i in range(1,N-1):
    for j in range(N):
        As[i][j] = gcd(As[i-1][j-1],As[i-1][j])

print(max(As[-1]))



### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
l = [0]*N
r = [0]*N
gcds = [0]*N
def gcd(a,b):
    if (a < b):
        a,b = b,a
    if (b == 0):
        return a
    return gcd(b, a%b)

l[0] = A[0]
r[-1] = A[-1]
for i in range(1,N):
    l[i] = gcd(A[i],l[i-1])
    r[-1-i] = gcd(A[-1-i],r[-i])

for i in range(N):
    if i == 0:
        gcds.append(gcd(0,r[i+1]))
    elif i == N-1:
        gcds.append(gcd(0,l[i-1]))
    else:
        gcds.append(gcd(l[i-1],r[i+1]))
print(max(gcds))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input().rstrip()

pos = []
i = 0
while i < len(s):
    i = s.find('AC', i)
    if i == -1:
        break
    pos.append(i)
    i += 2

for _ in range(q):
    i, r = map(int, input().split())
    print(len([c for c in pos if i -1 <= c < r - 1]))

### FIXED CODE ###

def main():
    N, Q = map(int, input().split())
    S = input()

    lis = [0 for _ in range(len(S))]
    for i in range(len(S)):
        if i > 0:
            lis[i] += lis[i - 1]
        if i < len(S) - 1 and S[i] == 'A' and S[i + 1] == 'C':
            lis[i + 1] += 1

    for _ in range(Q):
        L = tuple(map(int, input().split()))
        print(lis[L[1] - 1] - lis[L[0] - 1])


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

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

h.sort(reverse = True)

if k <= len(h):
    for i in range(k):
        h.pop(0)

    print(sum(h))

else:
    print("0")

### FIXED CODE ###

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

h.sort(reverse = True)

if k <= len(h):
    h[0:k] = []
    print(sum(h))
else:
    print("0")
### BUGGY CODE ###

import heapq

def dijkstra(s, edge):
    cost = [float('inf')] * n
    hq = [(0, s)]
    heapq.heapify(hq)
    while hq:
        c, v = heapq.heappop(hq)
        if c < cost[v]:
            cost[v] = c
        for d, u in edge[v]:
            if c + d < cost[u]:
                heapq.heappush(hq, (c + d, u))
    return cost

n, m, s, t = map(int, input().split())
s -= 1
t -= 1
yen = [[] for _ in range(n)]
snuuk = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    yen[u].append((a, v))
    yen[v].append((a, u))
    snuuk[u].append((b, v))
    snuuk[v].append((b, u))
py = dijkstra(s, yen)
ps = dijkstra(t, snuuk)
idx = -1
for i in range(n):
    if idx < i:
        res, idx = min((py[j] + ps[j], j) for j in range(i, n))
    print(10 ** 15 - res)


### FIXED CODE ###

import heapq
def dijkstra(s, neighbor):
    dist = [float('inf')] * N
    dist[s] = 0
    que = [(0, s)]
    heapq.heapify(que)
    while que:
        d, v = heapq.heappop(que)
        if d > dist[v]:
            continue
        for u, l in neighbor[v]:
            tmp_d = d + l
            if tmp_d < dist[u]:
                dist[u] = tmp_d
                heapq.heappush(que, (tmp_d, u))
    return dist

N, M, s, t = map(int, input().split())
yen = [[] for _ in range(N)]
snuuk = [[] for _ in range(N)]
for _ in range(M):
    u, v, a, b = map(int, input().split())
    yen[u-1].append((v-1, a))
    yen[v-1].append((u-1, a))
    snuuk[u-1].append((v-1, b))
    snuuk[v-1].append((u-1, b))

dist_s = dijkstra(s-1, yen)
dist_t = dijkstra(t-1, snuuk)
ans = [-1] * N
tmp = float('inf')
for i in range(N-1, -1, -1):
    if dist_s[i] + dist_t[i] < tmp:
        tmp = dist_s[i] + dist_t[i]
    ans[i] = 10 ** 15 - tmp
print(*ans, sep='\n')
### BUGGY CODE ###

import bisect 
n,m = map(int,input().split())
a = sorted(list(map(int,input().split())))

for i in range(m):
  b = a[-1]
  a.remove(b)
  b = int(b/2)
  bisect.insort(a,b)
  
print(sum(a))

### FIXED CODE ###

import heapq

n,m = map(int,input().split())
a = list(map(int,input().split()))
a = list(map(lambda x: x*(-1), a))  # 各要素を-1倍することで，最小最大を逆転

heapq.heapify(a)#優先度付きキューに変換

for i in range(m):
  tmp = heapq.heappop(a)
  heapq.heappush(a,(-tmp//2)*(-1))#負の剰余では切り捨て方向が異なってしまうので，いったんプラスにする．
  
print(-sum(a))
### BUGGY CODE ###

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

s = set()

for i in range(N-K+1):
    p = P[:i] + sorted(P[i:i+K]) + P[i+K:]
    s.add(tuple(p))
print(len(s))


### FIXED CODE ###

import sys
from collections import deque
from itertools import accumulate

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def slide_min(A, K):
    res = []
    Q = deque()
    for i, a in enumerate(A):
        while Q and A[Q[-1]] > a:
            Q.pop()
        Q.append(i)
        if Q[0] == i - K:
            Q.popleft()
        res.append(Q[0])
    return res[K - 1:]

N, K = lr()
P = lr()
mi = slide_min(P, K)
ma = slide_min([-x for x in P], K)
new_pattern = [not (mi == i and ma == i+K) for i, (mi, ma) in enumerate(zip(mi, ma[1:]))]
# Trueの時は新しいパターンが登場
increase = [0] + list(accumulate(x<y for x, y in zip(P, P[1:])))
# K区間で常に上昇
stable_increase = [y-x == K-1  for x, y in zip(increase, increase[K-1:])]
answer = 1 + sum([x for x, y in zip(new_pattern, stable_increase[1:]) if not y])
if not stable_increase[0] and any(stable_increase):
    answer += 1
print(answer)
### BUGGY CODE ###

N = int(input())
power = 1
for num in range(1, N+1):
    power = power*num

print(power%(10**9+7))

### FIXED CODE ###

N = int(input())
power = 1

for i in range(1, N+1):
    power = (power*i)%(10**9+7)
print(power)
### BUGGY CODE ###

from functools import reduce


def gcdd(x, y):
    x, y = max(x, y), min(x, y)
    while y > 0:
        r = x % y
        x = y
        y = r
    return x

def gcd(numbers):
    return reduce(gcdd, numbers)

n = int(input())
a = [int(i) for i in input().split()]
b = []
for i in range(n):
    d = a[:i] + a[i+1:]
    b.append(gcd(d))
print(max(b))

### FIXED CODE ###

def gcd(x, y):
    if x * y == 0:
        return (x+y)
    x, y = max(x, y), min(x, y)
    while y > 0:
        r = x % y
        x, y = y, r
    return x

n = int(input())
a = [int(i) for i in input().split()]
l_list = [0]
r_list = [0]
for i in range(n):
    l = gcd(l_list[i], a[i])
    l_list.append(l)
    r = gcd(r_list[-1], a[-i-1])
    r_list.append(r)
r_list = list(reversed(r_list))
r_list = r_list[1:]
l_list = l_list[:n]
c_list = []
for i in range(n):
    c_list.append(gcd(l_list[i], r_list[i]))
print(max(c_list))