Harryxun/stf_run huggingface dataset:
import sys
input=sys.stdin.readline
n=int(input())
x=input().rstrip()
p=x.count("1")
numx=0
for i in range(n):
    if x[-i-1]=="1":
        numx+=2**i
minus=numx%(p-1)
plus=numx%(p+1)

def popcnt(x):
    cnt=str(bin(x)).count("1")
    x%=cnt
    return x

for i in range(n):
    if x[i]=="0":
        amari=(plus+2**(n-i-1)%(p+1))%(p+1)
        ans=1
        while amari>=1:
            amari=popcnt(amari)
            ans+=1
        print(ans)
    else:
        if p==1:
            print(0)
            continue
        amari=(minus-2**(n-i-1)%(p-1))%(p-1)
        ans=1
        while amari>=1:
            amari=popcnt(amari)
            ans+=1
        print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
x=input().rstrip()
x10=int(x,2)
pcx=x.count("1")

plus=x10%(pcx+1)
if pcx>=2:
    minus=x10%(pcx-1)

def popcnt(x):
    cnt=1
    while x>=1:
        x%=(bin(x).count("1"))
        cnt+=1
    return cnt

for i in range(n):
    if x[i]=="0":
        amari=(plus+pow(2,n-i-1,pcx+1))%(pcx+1)
        print(popcnt(amari))
    else:
        if pcx==1:
            print(0)
        else:
            amari=(minus-pow(2,n-i-1,pcx-1))%(pcx-1)
            print(popcnt(amari))
a = list(input())
b = list(input())
if a == reverse(b):
    print("YES")
else:
    print("NO")

### FIXED CODE ###

a = list(input())
b = list(input())
if a == list(reversed(b)):
    print("YES")
else:
    print("NO")
import math

def P(n, r):
    return math.factorial(n)//math.factorial(n-r)
def C(n, r):
    return P(n, r)//math.factorial(r)

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

dic = {}
for i in range(N):
  if A[i] in dic:
    dic[A[i]] += 1
  else:
    dic[A[i]] = 1

memo = 
ans = 0
for k in dic:
  tmp  =dic[k]
  if tmp >= 2:
    memo[k] = C(tmp, 2)
    ans += memo[k]

for i in range(N):
  tmp = dic[A[i]]
  if tmp == 1:
    print(ans)
  elif tmp == 2:
    print(ans - 1)
  else
    print(ans - (memo[A[i]] - C(tmp-1, 2)))


### FIXED CODE ###

import math

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

dic = {}
for i in range(N):
  if A[i] in dic:
    dic[A[i]] += 1
  else:
    dic[A[i]] = 1

memo = [0 for i in range(10 ** 6)]
ans = 0
for k in dic:
  tmp  =dic[k]
  if tmp >= 2:
    if memo[tmp] == 0:
      memo[tmp] = tmp * (tmp - 1) // 2
      ans += memo[tmp]
    else:
      ans += memo[tmp]

for i in range(N):
  tmp = dic[A[i]]
  if tmp == 1:
    print(ans)
  elif tmp == 2:
    print(ans - 1)
  else:
    print(ans - tmp * (tmp - 1) // 2 + (tmp - 1) * (tmp - 2) // 2)
def main():
    N = int(input())
    S = input()
    if N % 2 == 0:
        print("No")
        quit()
    yesno = "Yes" if S[:N / 2] == S[N / 2:] else "No"
    print(yesno)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N = int(input())
    S = input()
    if N % 2 == 1:
        print("No")
        quit()
    n = N // 2
    yesno = "Yes" if S[:n] == S[n:] else "No"
    print(yesno)


if __name__ == "__main__":
    main()
n = int(input())
S = input()
letters = list("abcdefghijklmnopqrstuvwxyz")
print(max([len([x for x in letters if (x in S[:i]) & (x in S[i:])]) for i in range(1, n - 1)]))

### FIXED CODE ###

n = int(input())
S = input()
letters = list("abcdefghijklmnopqrstuvwxyz")
print(max([len([x for x in letters if (x in S[:i]) & (x in S[i:])]) for i in range(1, n)]))
h,w=map(int,raw_input().split())
n=input()
g=map(int,raw_input().split())
l=[]
for i in range(n):
    l=l+[i+1]*g[i]
for i in range(h):
    l1=[]
    for j in range(w):
        l1.append(l[h*i+j])
    if i%2==1:
        l1.reverse()
    for j in l1:
        print j,
    print 


### FIXED CODE ###

h,w=map(int,raw_input().split())
n=input()
g=map(int,raw_input().split())
l=[]
for i in range(n):
    l=l+[i+1]*g[i]
for i in range(h):
    l1=l[i*w:(i+1)*w]
    if i%2==1:
        l1.reverse()
    for j in l1:
        print j,
    print
from collections import defaultdict

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

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

par=[None]*n
frmember=defaultdict(int)

def dfs(v):
    if par[i]==None:
        par[v]=v
        frmember[par[v]]+=1
    for f in friend[v]:
        if par[f]==None:
            par[f]=par[v]
            frmember[par[v]]+=1
            dfs(f)

for i in range(n):
    if par[i]==None:
        dfs(i)

ans=[0]*n
for i in range(n):
    ans[i]+=frmember[par[i]]-len(friend[i])-1

for i in range(k):
    a,b=map(int, input().split()) 
    if par[a-1]==par[b-1]:
        ans[a-1]-=1
        ans[b-1]-=1

print(*ans)

### FIXED CODE ###

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

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        return self.find(x) == self.find(y)

ans=[0]*N
uf1=UnionFind(N)
for i in range(M):  # range(m):
    a,b=map(int, input().split()) #a,b:つながっている辺
    uf1.union(a-1,b-1)
    ans[a-1]-=1
    ans[b-1]-=1

for i in range(N):
    uf1.find(i)  # 一周findすることによって接続漏れをなくす。

from collections import defaultdict
ll=defaultdict(int)
for i in uf1.par:
    ll[i]+=1

for i in range(N):
    ans[i]+=ll[uf1.par[i]]-1

for i in range(K):
    a,b=map(int, input().split()) #a,b:つながっている辺
    if uf1.is_same(a-1,b-1):
        ans[a-1]-=1
        ans[b-1]-=1

print(*ans)
# -*- coding: utf-8 -*-

N = int(input())
V = map(int, input().split())
C = map(int, input().split())

gain = 0
for i in range(0,N):
    if(V[i]>C[i]):
        gain += V[i] - C[i]

print(gain)

### FIXED CODE ###

n=int(input())
v=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=0
for i in range(n):
  if v[i]>c[i]:
    ans+=v[i]-c[i]
print(ans)
import numpy as np

n,m = input().split(" ")
n = int(n)
m = int(m)

H = input().split(" ")
H = np.array([int(h) for h in H])

M = np.zeros((n,n))
for i in range(m):
    a, b = input().split(" ")
    M[int(a)-1, int(b)-1] = 1
    M[int(b)-1, int(a)-1] = 1

G = []
for i in range(n):
    # no path
    if sum(M[i,:])==0:
        G += [i]
    else:
        connected = np.where(M[i, :]==1)[0]
        flag = 0
        for c in connected:
            if (H[c] >= H[i]):
                flag  = 1
                break
        if flag == 0:
            G+= [i]

print(len(G))


### FIXED CODE ###

import numpy as np
 
n,m = input().split(" ")
n = int(n)
m = int(m)
 
H = input().split(" ")
H = np.array([int(h) for h in H])
Hs = np.zeros(n)

for i in range(m):
    a, b = input().split(" ")
    a = int(a) - 1
    b = int(b) - 1
    Hs[a] = np.max([Hs[a], H[b]])
    Hs[b] = np.max([Hs[b], H[a]])
 
G = []
for i in range(n):
    if Hs[i] < H[i]:
        G += [i]
 
print(len(G))
x, y = map(int, input.split())
print(x + y // 2)

### FIXED CODE ###

x, y =map(int, input().split())
print(x + y // 2)
a = list(map(int,input().split()))
for k in range(m):
  s, t = map(int,input().split())
  for i in range(s):
    a.append(t)
ans = 0
a.sort(reverse=True)
for v in range(n):
  ans += a[v]
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
b = [list(map(int,input().split())) for p in [0]*m]
b.sort(key=lambda q: -q[1])
#print(a)
#print(b)

c = 0
for s in b:
	for t in [0]*s[0]:
		#print(s)
		if c + 1 > n:
			break
		if s[1] <= a[c]:
			break
		a[c] = s[1]
		c += 1
		#print(a)
	else:
		continue
	break
print(sum(a))
N = int(input())
A = list(map(int, input().split()))
for val in A:
    if val % 2 == 1:
        continue
    elif val % 2 == 0:
        if val % 3 == 0:
            continue
        elif val % 5 == 0:
            continue
        else:
            print('DENIED')
            break
else:
    print('APPROVED')

### FIXED CODE ###

A = set(map(int, input().split()))
if len(A) == 2:
    print('Yes')
else:
    print('No')
import collections
import numpy as np

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

n1, n2 = np.meshgrid(np.arange(1,N+1),np.arange(1,N+1))
t1, t2 = np.meshgrid(np.array(A), np.array(A))
ans = (np.abs(n2-n1)==t1 + t2)

print(np.count_nonzero(ans)//2)

### FIXED CODE ###

import collections

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

P = [i+A[i] for i in range(N)]
Q = [j-A[j] for j in range(N)]

Q_dict = collections.Counter(Q)

cnt = 0
for i in range(N-1):
    Q_dict[Q[i]] -= 1
    cnt += Q_dict[P[i]]

print(cnt)
a,b = [ = [int(v) for v in input().split()]

d = a+b
e = a-b
f = a*b
print(max(max(d,e),f))


### FIXED CODE ###

a,b = [int(v) for v in input().split(" ")]

d = a+b
e = a-b
f = a*b
print(max(max(d,e),f))
a,b,c=map(int,input().split())
s=sum(a,b,c)
t=min(a,b,c)
l=s-t-max(a,b,c)
print(t*l//2)

### FIXED CODE ###

li=list(map(int,input().split()))
s=sum(li)
t=min(li)
l=s-t-max(li)
print(t*l//2)
from fractions import gcd

def get_primes(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i*2, n+1, i):
            is_prime[j] = False
    return [i for i in range(n+1) if is_prime[i]]

def factorization_num(n, pl):
    count = 0
    for p in pl:
        if n % p == 0: count += 1
    return count

A, B = map(int, input().split())
print(factorization_num(gcd(A, B), get_primes(gcd(A, B))) + 1)

### FIXED CODE ###

from fractions import gcd
def factorization(n):
    fac = {}
    count = 0
    while n % 2 == 0:
        n //= 2
        count += 1
    if count > 0:
        fac[2] = count
    for i in range(3, int(n ** .5) + 1, 2):
        count = 0
        while n % i == 0:
            n //= i
            count += 1
        if count > 0:
            fac[i] = count
    if n > 1:
        fac[n] = 1
    return fac

A, B = map(int, input().split())
fac = factorization(gcd(A, B))
print(len(fac) + 1)
N,M,K=map(int,input().split())
ans="No"
for x in range(N+1):
  a=K-x*M
  b=N-2*x
  if a!=0 and a%b==0 and 0<=a//b<M:
    print("Yes")
    exit()
print("No")

### FIXED CODE ###

N,M,K=map(int,input().split())
for n in range(0,N+1):
  for m in range(0,M+1):
    if n*M+m*N-2*n*m==K:
      print("Yes")
      exit(0)
print("No")
class Point():
    def __init__(self, x, y):
        self.x = x
        self.y = y    

w, h, x, y = map(int, input().split(' '))

square_area = w * h

px = w / 2  # 3
py = h / 2  # 3.5

multiple_ans = 0
if px == x and py == y:
    multiple_ans = 1

a = py - y / px - x
b = y - x * a

cross_point = []

cross_x = (h - b) / a  # 一番上
if not 0 <= cross_x <= w:
    cross_point.append(Point(cross_x, h))
cross_x = (b / a) * -1  # 一番下
if not 0 <= cross_x <= w:
    cross_point.append(Point(cross_x, 0))
cross_y = b
if not 0 <= cross_y <= h:
    cross_point.append(Point(0, cross_y))
cross_y = w * a + b
if not 0 <= cross_y <= h:
    cross_point.append(Point(w, cross_y))

cross_1 = cross_point[0]
cross_2 = cross_point[1]

if cross_1.y == 0 and cross_2.x == w:
    area_a = ((h - cross_2.y) * cross_1.x) / 2
    area_b = square_area - area_a
elif cross_2.x == w and cross_1.y == 0:
    area_a = ((w - cross_2.x) * cross_1.y) / 2
    area_b = square_area - area_a
elif cross_2.x == w and cross_1.y == h:
    area_a = (w - cross_1.x) * (h - cross_2.y) / 2
    area_b = square_area - area_a
elif cross_2.x == w and cross_1.y == 0:
    area_a = (cross_1.x * cross_2.x) / 2
    area_b = square_area - area_a
else:
    area_a = (cross_1.y * cross_2.y) / 2
    area_b = square_area - area_a

print('{max_area} {multiple_ans}'.format(max_area=str(min(area_a, area_b)), multiple_ans=str(multiple_ans)))


### FIXED CODE ###

w, h, x, y = map(int, input().split(' '))

max_area = 0
square_area = w * h
multiple_ans = 1 if 2 * x == w and 2 * y == h else 0

print('{max_area} {multiple_ans}'.format(max_area=str(square_area / 2), multiple_ans=str(multiple_ans)))
str = input()
list = list(str)
abc = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z']
i = 0
while abc[i] in str:
    i += 1

print(abc[i])

### FIXED CODE ###

str = input()
abc = ['a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z','aa']
i = 0
while abc[i] in str:
    if i < 26:
        i += 1
    else:
        break

if i < 26:
    print(abc[i])

else:
    print("None")
base = 127
mask = (1 << 32) - 1


def calc_hash(f, pl, tl, with_array):
    dl = tl - pl
    tmp = []

    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.append(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.append(e)
    if with_array:
        return set(tmp), tmp
    else:
        return set(tmp)


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
h = dict()
while q:
    p = [ord(c) for c in input().strip()]
    pl = len(p)
    if pl > tl:
        print(0)
        q -= 1
        continue
    if pl >= 10:
        keys_set, keys_array = calc_hash(p, 10, pl, with_array=True)
        keys0, keys1 = keys_array[0], keys_array[1:pl - 9]
        if pl not in h:
            hash_set, hash_array = h[10] = calc_hash(t, 10, tl, with_array=True)
        else:
            hash_set, hash_array = h[10]

        if keys_set.issubset(hash_set):
            for idx, hash in enumerate(hash_array):
                if keys0 == hash and hash_array[idx + 1:idx + pl - 9] == keys1:
                    print(1)
                    break
            else:
                print(0)
        else:
            print(0)
    else:
        key = calc_hash(p, pl, pl).pop() & mask
        if pl not in h:
            h[pl] = calc_hash(t, pl, tl, with_array=False)
        print(1 if key in h[pl] else 0)
    q -= 1

### FIXED CODE ###

base = 127
mask = (1 << 32) - 1


def calc_hash(f, pl, tl):
    dl = tl - pl
    tmp = set()

    t = 1
    for _ in range(pl):
        t = (t * base) & mask
    e = 0
    for i in range(pl):
        e = (e * base + f[i]) & mask
    for i in range(dl):
        tmp.add(e)
        e = (e * base - t * f[i] + f[i + pl]) & mask
    tmp.add(e)
    return tmp


t = [ord(c) for c in input().strip()]
tl = len(t)
q = int(input())
ps = [input().strip() for _ in range(q)]
h = dict()
a = []
hash_len = 19
for p in ps:
    p = [ord(c) for c in p]
    pl = len(p)
    if pl > tl:
        a.append(0)
        continue
    bs = min(hash_len, pl)
    keys = calc_hash(p, bs, pl)
    if bs not in h:
        h[bs] = calc_hash(t, bs, tl)
    a.append(1 if keys.issubset(h[bs]) else 0)
print('\n'.join(map(str, a)))
n = int(input())
p = list(map(int,input().split()))
q = list(map(int,input().split()))
res = list(permutations(range(1,n+1)))
ans = abs(res.index(p) - res.index(q))
print(ans)

### FIXED CODE ###

from itertools import permutations
 
n = int(input())
p = tuple(map(int, input().split()))
q = tuple(map(int, input().split()))
a = list(permutations(range(1, n + 1)))
print(abs(a.index(p) - a.index(q)))
package main

import (
	"fmt"
)

func main(){
	var a int
	for i:=1; ; i++{
		fmt.Scan(&a)
		if a == 0{
			break
		}
		fmt.Printf("Case %d: %d\n", i, a)
	}
}


### FIXED CODE ###

import sys
a = sys.stdin.readlines()[:-1]
for i in range(len(a)):
    print('Case {}: {}'.format(i+1, a[i]), end='')
a,b=map(int,input().split())

if (a+b==15):
  print("+")
elseif (a*b==15):
  print("*")
else:
  print("×")

### FIXED CODE ###

A, B = map(int, input().split())
if(A+B==15):
    print("+")
elif(A*B==15):
    print("*")
else:
    print("x")
num = input()
if num == 1:
  print(1)
 else:
  print(0)

### FIXED CODE ###

num = int(input())
if num == 1:
  print(0)
else:
  print(1)
import collections

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

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

for i in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)
    
check = [0] * (n+1)
count = [0] * (n+1)

for i in range(q):
    p,x = map(int,input().split())
    count[p] += x
    
def dfs(x):
    check[x] = 1
    for u in g[x]:
        if check[u] == 1:
            continue
        count[u] += count[x]
        dfs(u)

check[1] = 1
dfs(1)

print(*count[1:])

### FIXED CODE ###

import collections

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

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

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

count = [0] * (n+1)
check = [0] * (n+1)

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

q = collections.deque()  
q.append(1)

while q:
    v = q.pop()
    check[v] = 1
    for u in g[v]:
        if check[u] == 1:
            continue
        count[u] += count[v]
        q.append(u)
        
print(*count[1:])
arr = ['NONE', 'SAT', ' FRI', 'THU', 'WED', 'TUE', 'MON', 'SUN']
s = input()
print(arr.index(s))


### FIXED CODE ###

arr = ['NONE', 'SAT', 'FRI', 'THU', 'WED', 'TUE', 'MON', 'SUN']
s = input()
print(arr.index(s))
for line in sys.stdin.readlines():
    a, b = map(int, line.split())
    print(len(str(a + b)))


### FIXED CODE ###

while True:
    try:
        a, b = map(int, input().split())
        print(len(str(a+b)))
    except EOFError:
        break
from collections import deque,Counter

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

cnt = Counter(lisA)

if len(cnt)>3:
    print("No")
    exit()

if len(cnt) == 1:
    if lisA[0] == 0:
        print("Yes")
        exit()
    else:
        print("No")
        exit()
elif len(cnt) == 2:
    if not 0 in cnt:
        print("No")
        exit()
    else:
        keys = sorted(list(cnt.keys()))
        another = keys[-1]
        if cnt[0]*2 == cnt[another]:
            print("Yes")
            exit()
        else:
            print("No")
            exit()
else:
    keys = sorted(list(cnt.keys()))
    if keys[0]^keys[1]^keys[2] != 0:
        print("No")
        exit()
    else:
        if cnt(keys[0])==cnt(keys[1])==cnt(keys[2]):
            print("yes")
            exit()
        else:
            print("No")
            exit()






### FIXED CODE ###

from collections import deque,Counter

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

cnt = Counter(lisA)

if len(cnt)>3:
    print("No")
    exit()

if len(cnt) == 1:
    if lisA[0] == 0:
        print("Yes")
        exit()
    else:
        print("No")
        exit()
elif len(cnt) == 2:
    if not 0 in cnt:
        print("No")
        exit()
    else:
        keys = sorted(list(cnt.keys()))
        another = keys[-1]
        if cnt[0]*2 == cnt[another]:
            print("Yes")
            exit()
        else:
            print("No")
            exit()
else:
    keys = sorted(list(cnt.keys()))
    if keys[0]^keys[1]^keys[2] != 0:
        print("No")
        exit()
    else:
        if cnt[keys[0]]==cnt[keys[1]]==cnt[keys[2]]:
            print("Yes")
            exit()
        else:
            print("No")
            exit()
x = input().split()[1]
ans = 0
 
a = input().split()
a.sort()
 
for i in len(a):
  if a[i] > x:
    print(ans)
    break
  else:
    x-=a[i]
    if i!=len(a)-1:
      ans+=1
    else:
      if a[i]=x:
        ans+=1
      print(ans)

### FIXED CODE ###

line = input().split()
N = int(line[0])
x = int(line[1])
ans = 0

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

for i in range(N):
    if a[i] > x:
        print(ans)
        break
    else:
        x -= a[i]
        if i != (N - 1):
            ans += 1
        else:
            if x == 0:
                ans += 1
            print(ans)
k=int(input())
x=int(input())

if 500*k =< x:
    print("yes")
else:
    print("no")

### FIXED CODE ###

k,x=map(int,input().split())

if 500*k >= x:
    print("Yes")
else:
    print("No")
N,K = list(map(int, input().split()))
a = list(map(int, input().split()))
print( (n-1 + k-1 - 1)// (k-1) )

### FIXED CODE ###

n,k = list(map(int, input().split()))
a = list(map(int, input().split()))
print( (n-1 + k-1 - 1)// (k-1) )
n,m = map(int,input().split())
ab = []
for _ in range(m):
    a, b = (int(x) for x in input().split())
    ab.append([a, b])

cp = copy.copy(ab)

cp = sorted(cp, key=lambda x: x[1])

cost = [[] for _ in range(n+1)]

for i,j in cp:
    cost[i].append(j)

for i,j in ab:
    ID = cost[i].index(j)+1
    i = str(i)
    i = (6-len(i))*'0'+i
    ID = str(ID)
    ID = (6-len(ID))*'0'+ID
    print(i+ID)

### FIXED CODE ###

n,m = map(int,input().split())
py = []
p_y = [[] for i in range(n)]
for _ in range(m):
    p,y = map(int,input().split())
    py.append((p,y))
    p_y[p-1].append(y)
ans = {}
for i, tmp in enumerate(p_y):
    cnt = 1
    p_y[i] = tmp.sort()
    for j, jj in enumerate(tmp):
 
        ans[(i+1, jj)] = str(i+1).zfill(6) + str(j+1).zfill(6)
 
 
for i, tmp in enumerate(py):
    print(ans[tmp])
i = int(input())
j = 1

while j <= i:
  if j%3 == 0 or j%10 ==3 or'3' in str(j):
    print(' ',end='')
    print(j,end='')
  j += 1

print()

### FIXED CODE ###

n = int(input())
i = 1

while i <= n:
	if i % 3 == 0 or "3" in str(i):
		print(" ",end='')
		print(i,end='')
	i += 1
print()
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
m = map(int, read().split())
S, C = zip(*zip(m, m))

def main(S, C):
    nums = [-1] * N
    for s, c in zip(S, C):
        s -= 1
        if nums[s] != -1 and nums[s] != c:
            return -1
        nums[s] = c
    if nums[0] == 0:
        return -1
    if nums[0] == -1:
        nums[0] = 1
    for i in range(1, N):
        if nums[i] == -1:
            nums[i] = 0
    return ''.join(map(str, nums))

print(main(S, C))

### FIXED CODE ###

import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
if M == 0:
    print([0, 10, 100][N - 1])
    exit()
m = map(int, read().split())
S, C = zip(*zip(m, m))

def test(n):
    st = str(n)
    if len(st) != N:
        return False
    for i, c in zip(S, C):
        i -= 1
        if st[i] != str(c):
            return False
    return True

def main():
    for n in range(1000):
        if test(n):
            return n
    return -1

print(main())
a=[int(input())for _ in range(5)]
k=int(input())
if e-a<=k:print("Yay!")
else:print(":(")

### FIXED CODE ###

a,b,c,d,e=int(input()),int(input()),int(input()),int(input()),int(input())
k=int(input())
print("Yay!"if e-a<=k else":(")
while 1:
    n = int(raw_input())
    max = 0
    for i in range(n):
        tmax = max + int(raw_input())
        if tmax > max:
            max = tmax
    print tmax

### FIXED CODE ###

while(1):
    N = int(input())
    if N==0: break
    sums = []
    nums = []
    s = 0
    for i in range(N):
        n = int(input())
        nums.append(n)
        s += n
        if s<0: s=0
        sums.append(s)
    if max(nums) >= 0:
        print(max(sums))
    else:
        print(max(nums))
N_K=input()
pn=input()
list_pn=[]
# N,K,Pnの切り出し
for i in range(len(N_K)):
    if N_K[i]==" ":
        N =int(N_K[0:i])
        K =int(N_K[i+1:len(N_K)])
a = 0
for i in range(len(pn)):
    if pn[i]==" ":
        list_pn.append(int(pn[a:i]))
        a = i
list_pn.append(int(pn[a+1:len(pn)]))
# Pnの期待値を計算
pn_ave=[]
for i in range(N):
    pn_ave.append(list_pn[i]*(list_pn[i]+1)/2/list_pn[i])

#最大値を算出
pn_ave_total=[]
for i in range(N-K+1):
    ave = 0
    list_ave = pn_ave[i:i+K]
    for j in range(K):
        ave += list_ave[j]
    pn_ave_total.append(ave)
pn_ave_total.sort()
print(pn_ave_total[-1])

### FIXED CODE ###

N,K=map(int,input().split())
list_pn=list(map(int,input().split()))
# Pnの期待値を計算
pn_ave=[]
for i in range(N):
    pn_ave.append((list_pn[i]+1)/2)
# Sj+k-Sjの累積和を用いて考える
Sj = []
Sj.append(0)
S=0
for i in range(N):
    S += pn_ave[i]
    Sj.append(S)
# print(Sj)
Sk = []
for i in range(N-K+1):
    Sk.append(Sj[i+K]-Sj[i])
# print(Sk)
Sk.sort()
print(Sk[-1])