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


import fractions

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

g=fractions.gcd(A,B)

if g==1:
    print(1)
    exit()

d_list=[]
for i in range(1,g+1):
    if g%i==0:
        d_list.append(i)


if len(d_list)==2:
    print(2)
    exit()

i=1

while d_list[i]<g:
    j=2
    temp=d_list[i]
    while temp*j<=d_list[-1]:
        if temp*j in d_list:
            d_list.remove(temp*j)
        j+=1
    i+=1
    if i==len(d_list):
        break


print(len(d_list))








### FIXED CODE ###

def div(N):
    ans = []
    for i in range(1, int(N ** 0.5) + 1):
        if N % i == 0:
            ans.append(i)
            if N // i != i:
                ans.append(N // i)
    ans.sort()
    return ans
import fractions

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

g=fractions.gcd(A,B)

if g==1:
    print(1)
    exit()
cnt=0
di=div(g)

for i in di:
    f=True
    for j in range(2,int(i**0.5)+1):
        if i%j==0:
            f=False
            break
    if f:
        cnt+=1
print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10000000)

N,M,P=map(int,input().split())
INF = 1000000000
edge = []
to = [[] for _ in range(N)]
rto = [[] for _ in range(N)]
reachable_from1 = [False]*N
reachable_fromN = [False]*N
for i in range(M):
    a,b,c = map(int,input().split())
    a-=1
    b-=1
    c=-c
    to[a].append(b)
    rto[b].append(a)
    edge.append([a,b,c])

def dfs(v):
    if reachable_from1[v] == True:
        return
    reachable_from1[v] = True
    for u in to[v]:
        dfs(u)

def rdfs(v):
    if reachable_fromN[v] == True:
        return
    reachable_fromN[v] = True
    for u in rto[v]:
        rdfs(u)

dfs(0)
rdfs(N-1)
ok = [False]*N
for i in range(N):
    ok[i] = reachable_from1[i]&reachable_fromN[i]

d = [INF]*N
d[0] = 0
update = True
step=0
while update:
    update = False
    for i in range(M):
        a,b,c=edge[i]
        if not(ok[a]): continue
        newD = d[a]+c+P
        if newD < d[b]:
            d[b] = newD
            update = True
    step+=1
    if step > N:
        print(-1)
        sys.exit()
print(max(0,-d[N-1]))
    




### FIXED CODE ###

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10000000)

N,M,P=map(int,input().split())
INF = 1000000000
edge = []
to = [[] for _ in range(N)]
rto = [[] for _ in range(N)]
reachable_from1 = [False]*N
reachable_fromN = [False]*N
for i in range(M):
    a,b,c = map(int,input().split())
    a-=1
    b-=1
    c=-c
    to[a].append(b)
    rto[b].append(a)
    edge.append([a,b,c])

def dfs(v):
    if reachable_from1[v] == True:
        return
    reachable_from1[v] = True
    for u in to[v]:
        dfs(u)

def rdfs(v):
    if reachable_fromN[v] == True:
        return
    reachable_fromN[v] = True
    for u in rto[v]:
        rdfs(u)

dfs(0)
rdfs(N-1)
ok = [False]*N
for i in range(N):
    ok[i] = reachable_from1[i]&reachable_fromN[i]

d = [INF]*N
d[0] = 0
update = True
step=0
while update:
    update = False
    for i in range(M):
        a,b,c=edge[i]
        if not(ok[a]): continue
        newD = d[a]+c+P
        if newD < d[b]:
            d[b] = newD
            update = True
    step+=1
    if step > N:
        print(-1)
        sys.exit()
print(max(0,-d[N-1]))
### 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()))

'''
必ず3つからそれぞれ1つずつ取らないといけないので、a,bの組み合わせの大きい順
とa,b,cの組の大きい順で見たときの(a,b)の順は一致している
a,bの組み合わせのうち上からk番目以降は考える必要がない
'''
ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i] + b[j])
ab.sort(reverse=True)
ab = ab[:k]
rec = []
for i in range(min(x*y, k)):
    for j in range(z):
        rec.append(ab[i] + c[j])

rec.sort(reverse=True)
rec = rec[:k]
print(*rec, sep='\n')

### 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()))

c = sorted(c, reverse=True)
ab = []
for i in range(x):
    for j in range(y):
        temp = a[i] + b[j]
        ab.append(temp)

ab = sorted(ab, reverse=True)
ans = []
for i in range(z):
    for j in range(min(x * y, k)):
        temp = c[i] + ab[j]
        ans += [temp]
ans = sorted(ans, reverse=True)

for i in range(k):
    print(ans[i])
### BUGGY CODE ###

import heapq
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
Xp = []
Xm = []
X0 = []
for x in X:
  if x > 0:
    Xp.append(x)
  elif x < 0:
    Xm.append(-x)
  else:
    X0.append(x)
limit = min(sum(Xp), sum(Xm))
Xp = [x for x in Xp if x <= limit]
Xm = [x for x in Xm if x <= limit]
R = [[0, 0] for x in range(limit + 1)]
def c(X, k):
  Q = []
  heapq.heappush(Q, 0)
  for x in X:
    _Q = []
    while Q:
      q = heapq.heappop(Q)
      if q > limit:
        break
      heapq.heappush(_Q, q)
      heapq.heappush(_Q, q + x)
    Q = _Q
  while Q:
    q = heapq.heappop(Q)
    if q > limit:
      break
    R[q][k] += 1
c(Xp, 0)
c(Xm, 1)
print(sum([r[0] * r[1] for r in R]) * (2 ** len(X0)) - 1)

### FIXED CODE ###

from collections import Counter
N, A = map(int, input().split())
X = [int(x) - A for x in input().split()]
C = Counter([0])
for x in X:
  tmp = Counter()
  for i, c in C.items():
    tmp[i + x] += c
  C += tmp
print(C[0] - 1)
### BUGGY CODE ###

n, m = map(int, input().split())
a_s = [int(input()) for _ in range(m)]

dp = [1]

for i in range(1, n + 1):
    if i in a_s:
        dp.append(0)
    else:
        dpim2 = 0 if i-2 < 0 else dp[i-2]
        dp.append((dp[i-1] + dpim2) % 1000000007)

print(dp[-1])


### FIXED CODE ###

n, m = map(int, input().split())
a_s = [int(input()) for _ in range(m)]

dp = [1]
n_with_a = [[i, False] for i in range(n+1)]



for a in a_s:
    n_with_a[a][1] = True



if 1 in a_s:
    dp.append(0)
else:
    dp.append(1)

for i, is_broken in n_with_a[2:]:
    if is_broken:
        dp.append(0)
    else:
        dp.append((dp[i-1] + dp[i-2]) % 1000000007)

print(dp[-1])
### BUGGY CODE ###

n = int(raw_input())
a = [[0] * (n + 1) for _ in range(n + 1)]
for i in xrange(n):
    aa = map(int, raw_input().split())
    for j in range(n):
        a[i + 1][j + 1] = a[i][j + 1] + a[i + 1][j] - a[i][j] + aa[j]
m = -10000 * 100 * 100
for i in xrange(n):
    for j in xrange(n):
        for k in xrange(i + 1, n + 1):
            for l in xrange(j + 1, n + 1):
                r = a[k][l] - a[k][j] - a[i][l] + a[i][j]
                m = max(m, r)
print m

### FIXED CODE ###

n = int(raw_input())
a = [[0] * (n + 1) for _ in range(n + 1)]
m = -10000 * 100 * 100

for i in range(n):
    b = map(int, raw_input().split())
    for j in range(n):
        aa = 0
        for k in range(j, n):
            aa += b[k]
            a[j][k] = max(a[j][k], 0) + aa
            m = max(m, a[j][k])
print m
### BUGGY CODE ###

n = int(input())
abc = [list(map(int, input().split())) for _ in range(n - 1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

mp2 = []
for i in range(len(abc)):
    mp2.append([abc[i][0] - 1, abc[i][1] - 1, abc[i][2]])
    mp2.append([abc[i][1] - 1, abc[i][0] - 1, abc[i][2]])
n_v = n
start = K - 1


# main
# コストテーブルの作成
from heapq import heappop, heappush
inf = float('inf')
prev = [None] * n_v # 経路をたどるときに使う
cost = dict() # コストテーブル
for i, j, k in mp2:
    cost[i] = cost.get(i, []) + [(j, k)]
# print(cost)

d = [inf for i in range(n_v)] # 最短距離
d[start] = 0

q = [] # min-heap, (距離, 頂点)
heappush(q, (d[start], start))
while q:
    # print(q, d, prev)
    du, u = heappop(q) # 最短距離とその頂点
    if d[u] < du:
        continue
    for v, weight in cost.get(u, []):
        alt = du + weight
        if d[v] > alt:
            d[v] = alt
            prev[v] = u
            heappush(q, (alt, v))

for i in range(Q):
    goal1 = xy[i][0] - 1
    goal2 = xy[i][1] - 1

    print(d[goal1] + d[goal2])


### FIXED CODE ###

n = int(input())
abc = [list(map(int, input().split())) for _ in range(n - 1)]
Q, K = map(int, input().split())
xy = [list(map(int, input().split())) for _ in range(Q)]

from heapq import heappop, heappush

def main():
    cost = [[] for _ in range(n)]
    for i in range(n - 1):
        a = abc[i][0] - 1
        b = abc[i][1] - 1
        c = abc[i][2]
        cost[a].append((b, c))
        cost[b].append((a, c))
    # print(cost)

    start = K - 1
    d = [float('inf') for i in range(n)] # 最短距離
    d[start] = 0

    q = [] # min-heap, (距離, 頂点)
    heappush(q, (d[start], start))
    while q:
        du, u = heappop(q) # 最短距離とその頂点
        if d[u] < du:
            continue
        for v, weight in cost[u]:
            alt = du + weight
            if d[v] > alt:
                d[v] = alt
                heappush(q, (alt, v))

    for goal1, goal2 in xy:
        print(d[goal1 - 1] + d[goal2 - 1])

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

n = int(input())
s = input()
ans = 0
for i in range(1000):
    key = "0" * (3 - len(str(i))) + str(i)
    j = 0
    flag = True
    while True:
        if j == n:
            flag = False
            break
        if s[j] == key[0]:
            j += 1
            break
        j += 1
    if not flag:
        continue
    while True:
        if j == n:
            flag = False
            break
        if s[j] == key[1]:
            j += 1
            break
        j += 1
    if not flag:
        continue
    while True:
        if j == n:
            flag = False
            break
        if s[j] == key[2]:
            j += 1
            break
        j += 1
    if flag:
        ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = 0
for i in range(1000):
    key = "0" * (3 - len(str(i))) + str(i)
    j = 0
    flag = True
    while True:
        if j == n:
            flag = False
            break
        if s[j] == key[0]:
            j += 1
            break
        j += 1
    if not flag:
        continue
    while True:
        if j == n:
            flag = False
            break
        if s[j] == key[1]:
            j += 1
            break
        j += 1
    if not flag:
        continue
    while True:
        if j == n:
            flag = False
            break
        if s[j] == key[2]:
            j += 1
            break
        j += 1
    if flag:
        ans += 1
print(ans)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
ans=0
for i in range(n-2):
  for j in range(i+1,n-1):
    for k in range(j+1,n):
      a,b,c=l[i],l[j],l[k]
      if a<b+c and b<c+a and c<a+b:
        ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n):
  k=i
  for j in range(i+1,n):
    while k<n and l[k]<l[i]+l[j]:
      k+=1
    ans+=k-(j+1)
print(ans)
### BUGGY CODE ###

n=int(raw_input())
N=range(n)
N1=N+[n]
A=[[0]*(n+1)]+[[0]+map(int,raw_input().split()) for i in N]
B=[[0 for j in N1] for i in N1]
N1=N1[1:]
for i in N1:
  x=A[i]
  if i==0: y=[0]*n
  else: y=B[i-1][:]
  s=0
  for j in N1:
    s+=x[j]
    y[j]+=s
  B[i]=y
m=-1e6
for i1 in N1:
  for j1 in N1:
    for i2 in range(i1,n+1):
      for j2 in range(j1,n+1):
        m=max(m,B[i1-1][j1-1]+B[i2][j2]-B[i1-1][j2]-B[i2][j1-1])
print m

### FIXED CODE ###

def f(m,b):
  s=0
  for k in N[j:]:
    s+=A[k]
    b[k]=max(b[k],0)+s
    m=max(b[k],m)
  return m,b

m=-1e9
n=int(raw_input())
N=range(n)
B=[[0]*(n+1) for _ in range(n+1)]
for _ in N:
  A=map(int,raw_input().split())
  for j in N: m,B[j]=f(m,B[j])
print m
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)

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

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

    lcm = 1
    for i in a:
        g = gcd(lcm, i)
        lcm *= i // g

    ans = 0
    mod = 10**9 + 7
    for i in a:
        ans += lcm // i
        ans %= mod
    print(ans)

main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

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

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

    lcm = 1
    for i in a:
        g = gcd(lcm, i)
        lcm *= i // g

    ans = 0
    mod = 10**9 + 7
    for i in a:
        ans += lcm // i
    ans %= mod
    print(ans)

main()
### BUGGY CODE ###

n=int(input())
ab=[]
p=[-1 for i in range(n+1)]
edge=[[0 for i in range(n+1)] for j in range(n+1)]
G=[[] for i in range(n+1)]
used=[0 for i in range(n+1)]
for i in range(n-1):
    ab.append(list(map(int,input().split())))
    G[ab[i][0]].append(ab[i][1])
    G[ab[i][1]].append(ab[i][0])

max_n=0

for i in range(n+1):
    tmp=len(G[i])
    if tmp>max_n:
        max_n=tmp
        top=i

queue=[]
queue.append(top)

while len(queue)>0:
    num=queue.pop(0)
    used[num]=1
    color=1
    for i in range(len(G[num])):
        if used[G[num][i]]==0:
            if p[num]==color:
                color+=1
                edge[num][G[num][i]]=color
                edge[G[num][i]][num]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            else:
                edge[num][G[num][i]]=color
                edge[G[num][i]][num]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            color+=1

print(max_n)
for i in range(n-1):

    print(edge[ab[i][0]][ab[i][1]])

        




### FIXED CODE ###

n=int(input())
ab=[]
p=[-1 for i in range(n+1)]
edge={}
G=[[] for i in range(n+1)]
used=[0 for i in range(n+1)]
for i in range(n-1):
    ab.append(list(map(int,input().split())))
    G[ab[i][0]].append(ab[i][1])
    G[ab[i][1]].append(ab[i][0])

max_n=0

for i in range(n+1):
    tmp=len(G[i])
    if tmp>max_n:
        max_n=tmp
        top=i

queue=[]
queue.append(top)

while len(queue)>0:
    num=queue.pop(0)
    used[num]=1
    color=1
    for i in range(len(G[num])):
        if used[G[num][i]]==0:
            if p[num]==color:
                color+=1
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            else:
                edge["{},{}".format(num,G[num][i])]=color
                edge["{},{}".format(G[num][i],num)]=color
                p[G[num][i]]=color
                queue.append(G[num][i])
            color+=1

print(max_n)
for i in range(n-1):

    print(edge["{},{}".format(ab[i][0],ab[i][1])])
### BUGGY CODE ###

def check():
    a = []
    bDict2 = {}
    count = 0
    removeList = []
    N, K = [int(i) for i in input().split(' ')]
    for i in range(1,N+1):
        if (2*i)%K == 0:
            a.append(i)


    while a != []:
        temp = a[0]
        for i in a:
            if (temp+i)%K == 0:
                removeList.append(i)
                if str(temp) not in bDict2:
                    bDict2[str(temp)] = 1
                else:
                    bDict2[str(temp)] += 1  
                    
        for i in removeList:
            a.remove(i)
        removeList.clear()
            
    for i in bDict2:
        count += bDict2[i]**3

    print(count)
check()

### FIXED CODE ###

N, K = map(int, input().split())
cnt1,cnt2 = 0,0

for i in range(1,N+1):
    if i%K == 0:
        cnt1 += 1
    elif i%K == K/2:
        cnt2 += 1
print(cnt1**3+cnt2**3)
### BUGGY CODE ###

N = int(input())

P = [int(i) for i in input().split()]

count = 0

for i in range(0, N):
  flag = True
  for j in range(0, i):
    if P[i] > P[j]:
      flag = False
      break
  if flag == True:
    count += 1

print(count)


### FIXED CODE ###

N = int(input())

P = [int(i) for i in input().split()]

count = 1	# 一つ目は絶対OK
min = P[0]

for i in range(1, N):
  if P[i] > min:
    continue
  min = P[i]
  count += 1

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

import numpy as np
from numba import njit
from bisect import *
n, m = map(int, input().split())
A, B, C = zip(*(map(int, input().split()) for _ in range(n)))
D, E, F = zip(*(map(int, input().split()) for _ in range(m)))
X = sorted(set(C + E + F))
Y = sorted(set(A + B + D))
H = len(Y)-1
W = len(X)-1
def TX(i):
    return bisect(X, i)-1
def TY(i):
    return bisect(Y, i)-1
U = np.ones((H+1, W))
for d, e, f in zip(D, E, F):
    d, e, f = TY(d), TX(e), TX(f)
    U[d, e:f] = False
L = np.ones((H, W+1))
for a ,b, c in zip(A, B, C):
    a, b, c = TY(a), TY(b), TX(c)
    L[a:b, c] = False
S = np.outer(np.diff(Y), np.diff(X))
@njit
def f(i,j):
    s = [(i,j)]
    v = set()
    r = 0
    while s:
        i, j = s.pop()
        if (i,j) in v:
            continue
        v.add((i,j))
        if not (0<=i<H and 0<=j<W):
            print('INF')
            break
        r += S[i][j]
        if U[i][j]:
            s.append((i-1,j))
        if U[i+1][j]:
            s.append((i+1,j))
        if L[i][j]:
            s.append((i,j-1))
        if L[i][j+1]:
            s.append((i,j+1))
    else:
        print(r)
i = bisect(Y, 0)-1
j = bisect(X, 0)-1
f(i,j)

### FIXED CODE ###

import numpy as np
from numba import njit
from bisect import *
n, m = map(int, input().split())
A, B, C = zip(*(map(int, input().split()) for _ in range(n)))
D, E, F = zip(*(map(int, input().split()) for _ in range(m)))
X = sorted(set(C))
Y = sorted(set(D))
H = len(Y)-1
W = len(X)-1
def TX(i):
    return bisect(X, i)-1
def TY(i):
    return bisect(Y, i)-1
U = np.ones((H+1, W))
for d, e, f in zip(D, E, F):
    #d, e, f = TY(d), TX(e), TX(f)
    d = TY(d)
    e = bisect_left(X, e)
    f = bisect_right(X, f)-1
    U[d, e:f] = False
L = np.ones((H, W+1))
for a ,b, c in zip(A, B, C):
    #a, b, c = TY(a), TY(b), TX(c)
    c = TX(c)
    a = bisect_left(Y, a)
    b = bisect_right(Y, b)-1
    L[a:b, c] = False
S = np.outer(np.diff(Y), np.diff(X))
@njit
def dfs(i, j):
    s = [(i,j)]
    v = np.zeros((H,W))
    r = 0
    while s:
        i, j = s.pop()
        if not (0<=i<H and 0<=j<W):
            return -1
        if v[i,j]:
            continue
        v[i,j] = True
        r += S[i,j]
        if U[i,j]:
            s.append((i-1,j))
        if U[i+1,j]:
            s.append((i+1,j))
        if L[i,j]:
            s.append((i,j-1))
        if L[i,j+1]:
            s.append((i,j+1))
    return r
r = dfs(TY(0), TX(0))
print('INF' if r<0 else r)
### BUGGY CODE ###

N,K,Q=map(int,input().split())
A = [K] * N
B = ["Yes"] *N
if K>Q:
    for i in range(N):
        print(B[i])
else:
    for i in range(Q):
        a=int(input())-1
        for j in range(N):
            if j!=a and A[j]>0:
                A[j]=A[j]-1
    for k in range(N):
        if A[k]>0:
            print("Yes")
        else:
            print("No")

### FIXED CODE ###

N,K,Q=map(int,input().split())
A = [0] * N
if K>Q:
    for i in range(N):
        print("Yes")
else:
    for i in range(Q):
        a=int(input())-1
        A[a]+=1
    for k in range(N):
        if K>Q-A[k]:
            print("Yes")
        else:
            print("No")
### BUGGY CODE ###

n, m, k = map(int, input().split())

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

a = [0] * (n + 1)
b = [0] * (m + 1)

for i in range(1, n + 1):
    a[i] = A[i - 1] + a[i - 1]

for j in range(1, m + 1):
    b[j] = B[j - 1] + b[j - 1]

ans = 0

for i in range(n + 1):
    if a[i] > k:
        break
    for j in range(m, -1, -1):
        if b[j] <= k - a[i]:
            break
    ans = max(ans, i + j)

print(ans)

### FIXED CODE ###

n, m, k = map(int, input().split())

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

a = [0] * (n + 1)
b = [0] * (m + 1)

for i in range(1, n + 1):
    a[i] = A[i - 1] + a[i - 1]

for j in range(1, m + 1):
    b[j] = B[j - 1] + b[j - 1]

ans = 0
num_b = m

for i in range(n + 1):
    if a[i] > k:
        break
    for j in range(num_b, -1, -1):
        if b[j] <= k - a[i]:
            break
        num_b -= 1
    ans = max(ans, i + j)

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

import copy
N = int(input())

A = [0]*N

for r in range(N):
  A[r] = int(input())
  
B = copy.copy(A)
  
for r in range(N):
  A.pop(r)
  print(max(A))
  A = copy.copy(B)

### FIXED CODE ###

N = int(input())
A = [0]*N

for r in range(N): A[r] = int(input())
A_max = max(A)
A_sec = sorted(A)[-2]

for r in range(N):
  if A[r] == A_max: print(A_sec)
  elif A[r] == A_sec: print(A_max)
  else: print(A_max)
### BUGGY CODE ###

div = (10**9) + 7

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

c = sorted(c, reverse=True)

ans = 0
for i in range(n):
    ans = (ans*4 + c[i] * (i+2) * (4**i) ) % div

print(ans)

### FIXED CODE ###

div = (10**9) + 7

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

c = sorted(c, reverse=True)

ans = 0

exp4_div = [0]*n
exp4_div[0] = 1
for i in range(1,n):
    exp4_div[i] = (exp4_div[i-1]*4)%div

for i in range(n):
    ans = (ans*4 + c[i] * (i+2) * exp4_div[i] ) % div

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

import numpy as np
N, K=map(int,input().split())
P=np.array(list(map(int,input().split())))
l=2

sum_max=0
for l in range(N-K+1):
    sum=P[l:l+K].sum() 
    if(sum>=sum_max):
        sum_max=sum

print(K*0.5+0.5*sum_max)

### FIXED CODE ###

N, K=map(int,input().split())
P=list(map(int,input().split()))
Sum=[0]* (N + 1)
for i in range(N):
    Sum[i+1]=Sum[i]+(P[i]+1)/2.0
Ans=0
for i in range(N-K+1):
    Ans=max(Ans,Sum[i+K]-Sum[i])
print(Ans)
### BUGGY CODE ###

# from pprint import pprint
# import math
import collections

# n = int(input())
n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = [None] * m
c = [None] * m
for i in range(m):
    _b, _c = map(int, input().split(' '))
    b[i] = _b
    c[i] = _c


def update_list(c):
    a.pop(a.index(min(a)))
    a.append(c)


for j in range(m):
    # 数字の登場個数を数える
    cnt = collections.Counter(a)

    for _ in range(b[j]):
        # cjより小さい数字がaにあれば更新する
        if min(cnt.keys()) < c[j]:
            update_list(c[j])

print(sum(a))

### FIXED CODE ###

# from pprint import pprint
# import math
import collections

# n = int(input())
n, m = map(int, input().split(' '))
a = list(map(int, input().split(' ')))
b = [None] * m
c = [None] * m
for i in range(m):
    _b, _c = map(int, input().split(' '))
    b[i] = _b
    c[i] = _c

# # リストに連結していって最後に大きい順に出力
# for j in range(m):
#     l = [c[j]] * b[j]
#     a.extend(l)


cnt = collections.Counter(a)

# カウンターのdictのみ更新
for j in range(m):
    cnt.update({c[j]: b[j]})

a_tup = cnt.items()

# print(a_tup)

# カウンターの結果を逆順にして合計n個になるまで取り出して加算
res = 0
num_cnt = 0
for _ in sorted(a_tup, reverse=True):
    res += _[0] * _[1]
    num_cnt += _[1]

    if num_cnt >= n:
        res -= _[0] * (num_cnt - n)
        break

print(res)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
def gcd(a,b):
    return gcd(b,a%b) if b else a
def lcm(a,b):
    return a*b//gcd(a,b)
k=1
for i in a:
    k = lcm(k,i)
ans=0
for i in a:
    ans += k//i
    ans %= 1000000007
print(ans)


### FIXED CODE ###

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

def gcd(a,b):
    return gcd(b,a%b) if b != 0 else a
mod = 10**9+7

def lcm(a,b):
    return a*b%mod * pow(gcd(a,b),mod-2,mod) % mod

num = {}

for i in range(n):
    nown=a[i]
    tmp = {}
    for i in range(2,int(nown**0.5) + 5):
        while nown % i ==0:
            nown//=i
            if(i in tmp):
                tmp[i]+=1
            else:
                tmp[i] = 1
    if nown != 1:
        tmp[nown] = 1    
    for key in tmp:
        if (key in num):
            num[key] = max(num[key],tmp[key])
        else:
            num[key] = tmp[key]

kobai = 1
for key in num:
    kobai *= pow(key, num[key],mod)
    kobai %= mod
    
ans = 0

for i in range(n):
    ans += kobai * pow(a[i],mod-2,mod) %mod
    ans %= mod

print(ans)