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

def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    P = []
    for _ in range(N):
        x, y = map(int, input().split())
        P.append((x, y))

    def calc_dist(pi):
        ret = -1
        reti = -1
        px, py = P[pi]
        for i, (x, y) in enumerate(P):
            d = abs(px - x) + abs(py - y)
            if d > ret:
                ret = d
                reti = i
        return ret, reti

    prev = -2
    ans = -1

    used = {0}
    from random import randrange

    i = 0
    while True:
        ret, i = calc_dist(i)
        if ret == prev:
            ans = ret
        if ~ans and i in used:
            break
        if prev < ret:
            prev = ret

        if len(used) == N:
            break

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    P = []
    M = []
    for _ in range(N):
        x, y = map(int, input().split())
        P.append(x + y)
        M.append(x - y)
    P.sort()
    M.sort()
    ans = max(P[-1] - P[0], M[-1] - M[0])
    print(ans)


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

N = int(input())
S = []
count = 0
for _ in range(N):
    s = list(input())
    s.sort()
    S.append(s)

for i in range(N):
    for j in range(i+1,N):
        if S[i] == S[j]:
            count += 1

print(count)


### FIXED CODE ###

import math
N = int(input())
S = []
ans = 0
count = 1
for _ in range(N):
    s = list(input())
    s.sort()
    S.append(''.join(s))
S.sort()
S.append('a')

for i in range(N):
    if S[i] == S[i+1]:
        count += 1
    else:
        if count > 2:
            ans += math.factorial(count)//(math.factorial(count-2)*math.factorial(2))
        elif count == 2:
            ans += 1
        count =1

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

N = int(input())
S = input()
c = [0] * 26
for s in S:
    c[ord(s)-ord('a')] = (c[ord(s)-ord('a')] + 1) % (10**9+7)
import itertools
import operator
from functools import reduce
ans = 0
for j in range(1, 27):
    for i in itertools.combinations(c, j):
        ans += reduce(operator.mul,i) % (10**9+7)
print(ans)


### FIXED CODE ###

import operator
import functools
N = int(input())
S = input()
c = [1] * 26
for s in S:
    c[ord(s)-ord('a')] += 1
print((functools.reduce(operator.mul,c)-1) % (10**9+7))
### BUGGY CODE ###

a = input()

def int2019(s):
    modTable = [0] * 2019
    total = 0
    for i in range(len(s)):
        nextTable = [0] * 2019
        for j in range(2019):
            nextTable[(j * 10 + int(s[i])) % 2019] = modTable[j]

        nextTable[int(s[i]) % 2019] += 1
        total += nextTable[0]
        modTable = nextTable

    return total


print(int2019(a))


### FIXED CODE ###

a = input()

def int2019(s):
    s = [int(i) for i in s]
    modTable = [0] * 2019
    total = 0
    for i in range(len(s)):
        nextTable = [0] * 2019
        for j in range(2019):
            nextTable[(j * 10 + (s[i])) % 2019] = modTable[j]

        nextTable[(s[i]) % 2019] += 1
        total += nextTable[0]
        modTable = nextTable

    return total


print(int2019(a))
### BUGGY CODE ###

n = int(input())
a= list(map(int, input().split()))
s = [0]*n
ans1 = 0
ans2 = ""
for i in range(1, n+1):
  temp = sum(s[n-i::n+1-i])
  #print("i: " + str(i) + "n+1-i: " + str(n+1-i))
  #print(temp)
  if temp % 2 == 0 and a[-i] == 0:
    s[-i] = 0
  elif temp % 2 == 1 and a[-i] == 1:
    s[-i] = 0
  else:
    s[-i] = 1
    ans1 += 1
    ans2 = str(n+1-i) + " " + ans2
  #print(a[-i]) 
  #print(a[n-i::n+1-i])

print(ans1)
print(ans2)

### FIXED CODE ###

n = int(input())
a= list(map(int, input().split()))
s = [0]*n
ans2 = []
for i in range(1, n+1):
  temp = sum(s[n-i::n+1-i])
  if (temp % 2 == 0 and a[-i] == 1) or (temp % 2 == 1 and a[-i] == 0) :
    s[-i] = 1
    ans2.append(str(n+1-i)) 

ans2.reverse()
print(sum(s))
print(" ".join(ans2))
### BUGGY CODE ###

s=input()
K=int(input())

dic={}
for i in range(len(s)):
    dic[s[i:]]=1
arr=sorted(dic)
dic={}
for x in arr:
    for i in range(0,len(x)):
        tmp = x[:i+1]
        if dic.get(tmp,0)==0:
            K-=1
            dic[tmp]=1
        else:
            continue
        if K==0:
            print(x[:i+1])
            break

### FIXED CODE ###

s=input()
K=int(input())

dic={}
for i in range(len(s)):
    dic[s[i:]]=1
arr=sorted(dic)
dic={}

for x in arr:
    for i in range(0,len(x)):
        tmp = x[:i+1]
        if dic.get(tmp,0)==0:
            K-=1
            dic[tmp]=1
        else:
            continue
        if K==0:
            print(x[:i+1])
            break
    if K<0:
        break
### BUGGY CODE ###

#ABC068C
N,M=map(int,input().split())
A=[]
B=[]
for m in range(M):
	I=list(map(int,input().split()))
	A.append(I[0])
	B.append(I[1])
def DP(next,c):
	global N,A,B
	r=-1
	if c==3:
		return -1
	if c==2 and next==N:
		return 1
	for i,x in enumerate(A):
		if x==next:
			r=max(r,DP(B[i],c+1))
	for i,x in enumerate(B):
		if x==next:
			r=max(r,DP(A[i],c+1))
	return r

if DP(1,0)==1:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')

### FIXED CODE ###

#ABC068C
N,M=map(int,input().split())
A=[]
B=[]
C=[]
D=[]
for m in range(M):
	I=list(map(int,input().split()))
	if I[0]==1:
		A.append(I[0])
		B.append(I[1])
	elif I[1]==N:
		C.append(I[0])
		D.append(I[1])
if len(set(B)&set(C))>0:
	print('POSSIBLE')
else:
	print('IMPOSSIBLE')
### BUGGY CODE ###

import sys
import numpy as np
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


N = readint()
A = np.array(list(readnums()))

ans = 0
for i in range(N):
    r = np.arange(N - i)
    a = A[i:]
    ans += np.count_nonzero((a - r) == -A[i])

print(ans)


### FIXED CODE ###

import sys
from collections import Counter
input = sys.stdin.readline


def readstr():
    return input().strip()


def readint():
    return int(input())


def readnums():
    return map(int, input().split())


def readstrs():
    return input().split()


N = readint()
A = list(readnums())

L = [i + x for i, x in enumerate(A)]
R = [i - x for i, x in enumerate(A)]

l_c = Counter(L)
r_c = Counter(R)

x1 = min(max(L), max(R))
x2 = max(min(L), min(R))

ans = 0
for i in range(x2, x1 + 1):
    ans += l_c[i] * r_c[i]

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

#!/usr/bin/env python

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7

    a.sort()
    ret = 1
    if k % 2 == 0 or a[-1] >= 0:
        for _ in range(k//2):
            mlt1 = a[0] * a[1]
            mlt2 = a[-2] * a[-1]
            if mlt1 >= mlt2:
                ret *= mlt1 % mod
                a = a[2:]
            else:
                ret *= mlt2 % mod
                a = a[:-2]
            ret %= mod

        if k % 2 == 1:
            ret *= a[-1]
            ret %= mod

    else:
        for i in range(k):
            ret *= a[n-1-i]
            ret %= mod

    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python

def main():
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    mod = 10**9+7

    a.sort()
    ret = 1
    if k % 2 == 0 or a[-1] >= 0:
        l = 0
        r = -1
        mlt1 = a[0] * a[1]
        mlt2 = a[-2] * a[-1]
        for _ in range(k//2):
            if mlt1 >= mlt2:
                ret *= mlt1 % mod
                l += 2
                if l <= n-2:
                    mlt1 = a[l+1] * a[l]
            else:
                ret *= mlt2 % mod
                r -= 2
                if r >= -n+1:
                    mlt2 = a[r-1] * a[r]
            ret %= mod

        if k % 2 == 1:
            ret *= a[r]
            ret %= mod

    else:
        for i in range(k):
            ret *= a[n-1-i]
            ret %= mod

    print(ret)


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

n,m=map(int,input().split())
a=[0]*n
b=[0]*n
ans=0
temp=0
for i in range(n):
  at,bt=map(int,input().split())
  a[i]=at
  b[i]=bt
import numpy as np
a=np.array(a)
b=np.array(b)
while temp<m:
  t=np.argmin(a)
  if temp+b[t]>=m:
    ans=ans+a[t]*(m-temp)
    break
  else:
    ans=ans+a[t]*b[t]
    temp=temp+b[t]
    a=np.delete(a,t)
    b=np.delete(b,t)
    t=np.argmin(a)
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
t=[0]*n
ans=0
temp=0
for i in range(n):
  at,bt=map(int,input().split())
  t[i]=[at,bt]
t.sort()
i=0
while True:
  if temp+t[i][1]>=m:
    ans=ans+t[i][0]*(m-temp)
    break
  else:
    ans=ans+t[i][0]*t[i][1]
    temp=temp+t[i][1]
    i=i+1
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
def f(x):
  if a[x]>=k:
    return True
  dp=[False]*k
  dp[0]=True
  y=0
  for i in range(n):
    if i==x:
      continue
    for j in range(y,-1,-1):
      if j+a[i]>=k:
        continue
      dp[j+a[i]]|=dp[j]
    y=min(k-1,y+a[i])
  return sum(dp[k-a[x]:k])
if not f(n-1):
  print(n)
  exit()
if f(0):
  print(0)
  exit()
l,r=0,n-1
while r-l>1:
  mid=(r+l)//2
  if f(mid):
    r=mid
  else:
    l=mid
print(r)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
def f(x):
  if a[x]>=k:
    return True
  dp=[False]*k
  dp[0]=True
  y=0
  for i in range(n):
    if i==x:
      continue
    for j in range(y,-1,-1):
      if j+a[i]>=k:
        continue
      dp[j+a[i]]|=dp[j]
    y=min(k-1,y+a[i])
  return sum(dp[k-a[x]:k])
if not f(n-1):
  print(n)
  exit()
if f(0):
  print(0)
  exit()
l,r=0,n-1
while r-l>1:
  mid=(r+l)//2
  if f(mid):
    r=mid
  else:
    l=mid
print(r)
### BUGGY CODE ###

N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

class SegTreeMin:
    def __init__(self, n, inf=10 ** 15):
        self.n = n
        n2 = 1
        while n2 < n:
            n2 <<= 1
        self.n2 = n2
        self.tree = [inf] * (n2 << 1)
        self.inf = inf
        
    def update(self, i, x):
        i += self.n2
        self.tree[i] = x
        while i > 1:
            x = min(x, self.tree[i ^ 1])
            self.tree[i >> 1] = x
            i >>= 1
            
    def get_min(self, a, b):
        result = self.inf
        q = [(1, 0, self.n2)]
        while q:
            k, l, r = q.pop()
            if a <= l and r <= b:
                result = min(result, self.tree[k])
                continue
                
            m = (l + r) // 2
            k <<= 1
            if a < m and l < b:
                q.append((k, l, m))
            if a < r and l < m:
                q.append((k + 1, m, r))
                
        return result

INF = float("inf")
seg_tree = SegTreeMin(N, INF)
seg_tree.update(0, 0)
X.sort()
for l, r, c in X:
    l -= 1
    r -= 1
    tmp = seg_tree.get_min(l, r)
    seg_tree.update(r, min(tmp + c, seg_tree.get_min(r, r + 1)))
ans = seg_tree.get_min(N - 1, N)
print(ans if ans != INF else -1)


### FIXED CODE ###

from heapq import heappop, heappush
N, M = map(int, input().split())
X = [list(map(int, input().split())) for _ in range(M)]

edges = [[] for _ in range(N)]
for u, v, c in X:
    edges[u - 1].append((v - 1, c))
    
for i in range(N - 1):
    edges[i + 1].append((i, 0))

INF = float("inf")
d = [INF] * N
d[0] = 0

pq = []
heappush(pq, (0, 0))

while len(pq) > 0:
    cost, u = heappop(pq)
    for v, c in edges[u]:            
        if d[v] > d[u] + c:
            d[v] = d[u] + c
            heappush(pq, (d[v], v))
            
print(d[-1] if d[-1] != INF else -1)
### BUGGY CODE ###

def main():
  s = ''.join(reversed(input()))
  multiplier = 1
  divisor = 10 ** 9 + 7
  list10 = list(range(10))
  list13 = list(range(13))
  p = [0 for i in list13]
  np = [0 for i in list13]
  if s[0] != '?':
    p[int(s[0])] = 1
  else:
    for j in list10:
      p[j] = 1
  for i in range(1, len(s)):
    multiplier = (10 * multiplier) % 13
    if s[i] != '?':
      r = int(s[i]) * multiplier
      for j in list13:
        np[(j + r) % 13] = p[j]
    else:
      r = 0
      for j in list10:
        np[(0 + r) % 13] += p[0]
        np[(1 + r) % 13] += p[1]
        np[(2 + r) % 13] += p[2]
        np[(3 + r) % 13] += p[3]
        np[(4 + r) % 13] += p[4]
        np[(5 + r) % 13] += p[5]
        np[(6 + r) % 13] += p[6]
        np[(7 + r) % 13] += p[7]
        np[(8 + r) % 13] += p[8]
        np[(9 + r) % 13] += p[9]
        np[(10 + r) % 13] += p[10]
        np[(11 + r) % 13] += p[11]
        np[(12 + r) % 13] += p[12]
        r += multiplier
    for j in list13:
      p[j] = np[j] % divisor
      np[j] = 0
  print(p[5] % divisor)
main()

### FIXED CODE ###

s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)
### BUGGY CODE ###

n = int(input())
s = input()
cou = []
for i in range(1000):
  i = "{0:03d}".format(i)
  a,b,c = i[0],i[1],i[2]
  for j in range(n):
    if s[j]==a:
      for k in range(j+1,n):
        if s[k]==b:
          for m in range(k+1,n):
            if s[m]==c:
              cou.append(i)
print(len(set(cou)))

### FIXED CODE ###

n = int(input())
s = input()
cou = 0
for i in range(1000):
  i = "{0:03d}".format(i)
  t = 0
  r = 0
  while r!=n:
    if s[r]==i[t]:
      t += 1
    if t==3:
      cou += 1
      r = n-1
    r += 1            
print(cou)
### BUGGY CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

def power(x):
	return pow(2, x, MOD)-1

MOD = 998244353
class BIT():#1-indexed
	def __init__(self, size):
		self.table = [0 for _ in range(size+2)]
		self.size = size

	def Sum(self, i):#1からiまでの和
		s = 0
		while i > 0:
			s += self.table[i]
			i -= (i & -i)
		return s

	def PointAdd(self, i, x):#
		while i <= self.size:
			self.table[i] += x
			i += (i & -i)
		return

n = int(input())
dd = [list(map(int, input().split())) + [i] for i in range(n)]
d = [[-1, -1] for _ in range(n)]
dd.sort()
for i, x in enumerate(dd):
	d[x[2]][0] = i+1
dd.sort(key=lambda x: x[1])
for i, x in enumerate(dd):
	d[x[2]][1] = i+1
d.sort()
lu = [0 for _ in range(n)]
ld = [0 for _ in range(n)]
rd = [0 for _ in range(n)]
ru = [0 for _ in range(n)]
bitl, bitr = BIT(n), BIT(n)

for i in range(n):
	lu[i] = i - bitl.Sum(d[i][1])
	ld[i] = i - lu[i]
	bitl.PointAdd(d[i][1], 1)

for i in range(n-1, -1, -1):
	ru[i] = n-1-i - bitr.Sum(d[i][1])
	rd[i] = n-1-i - ru[i]
	bitr.PointAdd(d[i][1], 1)
#print(lu, ld, rd, ru, sep="\n")

ans = 0
for i in range(n):
	ans += power(n)
	ans -= power(lu[i]+ld[i]) + power(ld[i]+rd[i]) + power(rd[i]+ru[i]) + power(ru[i]+lu[i])
	ans += power(lu[i]) + power(ld[i]) + power(rd[i]) + power(ru[i])
	ans %= MOD

print(ans)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

MOD = 998244353
class Rsum():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [0] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Add(self, x, val):
		x += self.n-1
		self.node[x] += val
		while x > 0:
			x = (x-1)//2
			self.node[x] = self.node[2*x+1] + self.node[2*x+2]
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = 0
		while L<R:
			if R & 1:
				R -= 1
				s += self.node[R-1]
			if L & 1:
				s += self.node[L-1]
				L += 1
			L >>= 1
			R >>= 1
		return s

n = int(input())
d = []
for i in range(n):
	x, yy = map(int, input().split())
	d.append((x, yy, i))
y = [-1 for _ in range(n)]
d.sort(key=lambda x: x[1])
for i, x in enumerate(d):
	y[x[2]] = i

d.sort()
lus = [-1 for _ in range(n)]
lds = [-1 for _ in range(n)]
rus = [-1 for _ in range(n)]
rds = [-1 for _ in range(n)]

st = Rsum(n)
for i in range(n):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	lus[i] = g
	lds[i] = i - g
	st.Add(pnt, 1)

st = Rsum(n)
for i in range(n-1, -1, -1):
	pnt = y[d[i][2]]
	g = st.Get(pnt, n)
	rus[i] = g
	rds[i] = n-1-i - g
	st.Add(pnt, 1)

pws = [1]
for _ in range(n-1):
	pws.append((pws[-1] * 2) % MOD)

ans = (n * pws[n-1]) % MOD
for lu, ld, ru, rd in zip(lus, lds, rus, rds):
	ans += ((pws[lu]-1) * (pws[rd]-1))
	ans += ((pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[rd]-1))
	ans += ((pws[lu]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[ld]-1) * (pws[rd]-1) * (pws[ru]-1))
	ans += ((pws[lu]-1) * (pws[ld]-1) * (pws[ru]-1) * (pws[rd]-1))
	ans %= MOD
print(ans)
### BUGGY CODE ###

from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[0 for i in range(W)] for j in range(H)]
    todo = deque()
    if S[x0][y0]=='@':return 0
    seen[x0][y0] = 1
    todo.append(x0*W+y0)
    while todo:
      x0,y0 = divmod(todo.popleft(),W)
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if seen[x][y]==1:continue
          if S[x][y]=='@':break
          seen[x][y] = 1
          todo.append(x*W+y)
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans > 0 else -1)
  
if __name__ == "__main__":
  main()

### FIXED CODE ###

from collections import deque

def main():
  H,W,K=map(int,input().split())
  x1,y1,x2,y2 = map(lambda x: int(x)-1,input().split())
  S=[list(input()) for _ in range(H)]
  INF = 10**20

  def bfs(x0,y0,x_goal,y_goal):
    seen = [[0 for i in range(W)] for j in range(H)]
    d = [[INF for i in range(W)] for j in range(H)]
    d[x0][y0] = 0
    todo = deque()
    seen[x0][y0] = 1
    todo.append((x0,y0))
    while todo:
      x0,y0 = todo.popleft()
      dx,dy = (1,-1,0,0),(0,0,1,-1)
      for i in range(4):
        for k in range(K):
          x,y = x0+dx[i]*(k+1), y0+dy[i]*(k+1)
          if x<0 or x>=H:break
          if y<0 or y>=W:break
          if d[x][y] < d[x0][y0] + 1: break
          if S[x][y]=='@':break
          if seen[x][y]: continue
          seen[x][y] = 1
          todo.append((x,y))
          d[x][y] = d[x0][y0] + 1
          if x==x_goal and y == y_goal: return d[x][y]
    return d[x_goal][y_goal]

  ans = bfs(x1,y1,x2,y2)
  print(ans if ans < INF else -1)
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
    t=factorization(a[i])
    for j,k in t:
        if j==2:
            ans+=k
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
for i in range(n):
    while a[i]%2==0:
        ans+=1
        a[i]/=2
print(ans)
### BUGGY CODE ###

def judge(x, y):
  #if x < 0 or y < 0:
  #  return True
  if P[x] > P[y]:
    return True
  #if P[x] == P[y]:
  #  return judge(x-1, y-1)
  return False

N, K = list(map(int, input().strip().split()))
P = list(map(int, input().strip().split()))
start = 0
_sum = 0
for i in range(1, N - K + 1):
  if judge(i+K-1, i-1):
    tmp = sum(P[i:i+K])
    if tmp > _sum:
      _sum = tmp
      start = i
    #print(start)
ans = 0.0
for _p in P[start:start+K]:
  ans += (1+_p) / 2
print(ans)
#print(P[start:start+K])

### FIXED CODE ###

N, K = list(map(int, input().strip().split()))
P = list(map(int, input().strip().split()))
start = 0
rec_sum = sum(P[0:K])
max_sum = rec_sum
for i in range(1, N - K + 1):
  rec_sum = rec_sum - P[i-1] + P[i+K-1]
  if rec_sum > max_sum:
    start = i
    max_sum = rec_sum
    
ans = 0.0
for _p in P[start:start+K]:
  ans += (1+_p) / 2
print(ans)
#print(P[start:start+K])
### BUGGY CODE ###

def main():
    from numpy import array,searchsorted
    n,*t=map(int,open(0).read().split())
    a,b=array(t[:n]),array(t[n:])
    c=0
    for k in range(28,-1,-1):
        l,h=2**k,2**-~k
        a%=h
        b%=h
        b.sort()
        m=0
        for t in a:
            if l-t<0:
                i=searchsorted(b,(l-t)%h)-n
            else:
                i=searchsorted(b,l-t)
            j=searchsorted(b,h-t)
            m+=j-i
        c+=m%2*2**k
    print(c)
if __name__=='__main__':
    main()

### FIXED CODE ###

def main():
    from numpy import array,searchsorted,sum,hstack
    n,*t=map(int,open(0).read().split())
    a,b=array(t[:n],'i4'),array(t[n:],'i4')
    c=0
    for k in range(28,-1,-1):
        l,h=pow(2,k),pow(2,k+1)
        a%=h
        b%=h
        b.sort()
        y=hstack((b-h,b))
        i=searchsorted(y,l-a)
        j=searchsorted(y,h-a)
        m=sum(j-i)
        c+=m%2*l
    print(c)
if __name__=='__main__':
    main()
### BUGGY CODE ###

import math
import heapq

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

for i in range(M):
    heapq.heapify(A)
    heapq.heappush(A, heapq.heappop(A)/2)

B = [math.floor(-A[i]) for i in range(len(A))]
print(sum(B))

### FIXED CODE ###

import heapq

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

heapq.heapify(A)

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

import math
import queue
import bisect
import heapq

mod = 1e9+7

def swap(a,b):
    return (b,a)

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

def divisors(a):
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def prime_num(a):
    pn = [2]
    for i in range(3,a):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
        if prime:
            pn.append(i)
    return pn

def main():
    a,b = map(int,input().split())
    div_a = divisors(a)
    div_a.sort()
    div_b = divisors(b)
    div_b.sort()
    g = []
    for i in div_a:
        if i!=2 and i%2==0:
            continue
        if i in div_b:
            g.append(i)
    pn = prime_num(max(g)+1)
    ans = 1
    for i in g:
        if i in pn:
            ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
import queue
import bisect
import heapq
import time

mod = 1e9+7

def swap(a,b):
    return (b,a)

def gcd(a,b): #最大公約数
    if (a<b):
        a,b = swap(a,b)
    if (b==0):
        return a
    else:
        return gcd(b,a%b)

def divisors(a): # 約数列挙
    divisors = []
    for i in range(1,int(a**0.5)+1):
        if a%i==0:
            divisors.append(i)
            if i!=a//i:
                divisors.append(a//i)
    return divisors

def is_prime(a): #素数判定
    if a<2:
        return False
    elif a==2:
        return True
    elif a%2==0:
        return False
    sqrt_num = int(a**0.5)
    for i in range(3,sqrt_num+1,2):
        if a%i==0:
            return False
    return True

def prime_num(a): #素数列挙
    pn = [2]
    for i in range(3,int(a**0.5),2):
        prime = True
        for j in pn:
            if i%j==0:
                prime = False
                break
        if prime:
            pn.append(i)
    return pn

def main():
    a,b = map(int,input().split())
    g = gcd(a,b)
    g_l = divisors(g)
    ans = 1
    for i in g_l:
        if is_prime(i):
            ans += 1
    print(ans)
    return

if __name__ == '__main__':
    main()