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

h,w,d = map(int,input().split())
adr = [-1]*(h*w) #indexの数字は[i,j]に書かれている
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        adr[a[j]-1] = [i,j]
q = int(input())

ans = []
for i in range(q):
    l,r = map(int,input().split())
    now = l-1
    cost = 0
    while now != r-1:
        cost += abs(adr[now][0]-adr[now+d][0])+abs(adr[now][1]-adr[now+d][1])
        now += d
    ans.append(cost)
    
for i in ans:
    print(i)

### FIXED CODE ###

h,w,d = map(int,input().split())
adr = [-1]*(h*w) #indexの数字は[i,j]に書かれている
for i in range(h):
    a = list(map(int,input().split()))
    for j in range(w):
        adr[a[j]-1] = [i,j]
        
cost = [0]*(h*w)
for i in range(d,h*w):
    cost[i] = cost[i-d] + abs(adr[i][0]-adr[i-d][0]) + abs(adr[i][1]-adr[i-d][1])
        
q = int(input())
ans = []
for i in range(q):
    l,r = map(int,input().split())
    ans.append(cost[r-1]-cost[l-1])

for i in ans:
    print(i)
### BUGGY CODE ###

n=int(input())
lst=list(map(int,input().strip().split()))
s=0
mod=1000000007
for i in range(0,n):
    for j in range(i+1,n):
        s+=(((lst[i]%mod)*(lst[j]%mod))%mod)
print(s%mod)

### FIXED CODE ###

n=int(input())
lst=list(map(int,input().strip().split()))
s1=sum(lst)
num=s1*s1
denom=0 
mod=1000000007
for i in range(0,n):
        denom+=(lst[i]*lst[i])
print(((num-denom)//2)%mod)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
a = list(map(int, input().split()))

dp = [[[0] * (N + 1) for _ in range(N + 1)] for _ in range(3 * N + 1)]
#dp[n][i3][i2]...n:上に乗ってる寿司の数、i3:寿司が3貫の皿の枚数、i2:2貫の枚数。
n, i3, i2 = 0, 0, 0

for i in range(N):
	if a[i] == 3:
		i3 += 1
		n += 3
	elif a[i] == 2:
		i2 += 1
		n += 2
	elif a[i] == 1:
		n += 1
		
c1, c2, c3 = 0, 0, 0
		
#寿司を引くのではなく足していく
for m in range(0, n + 1):
	for j3 in range(0, N + 1):
		for j2 in range(0, N + 1):
			j1 = m - 3 * j3 - 2 * j2
			if j1 < 0:
				continue
				
			#サイコロで3貫の皿が出たときの処理
			if j3 > 0 and j2 < N:
				c3 = dp[m - 1][j3 - 1][j2 + 1]
				p3 = j3 / N
			else:
				p3 = 0
			
			#2貫
			if j2 > 0:
				c2 = dp[m - 1][j3][j2 - 1] 
				p2 = j2 / N
			else:
				p2 = 0
			
			#1貫
			if j1 > 0:
				c1 = dp[m - 1][j3][j2]
				p1 = j1 / N
			else:
				p1 = 0
			
			p = p3 + p2 + p1
			if p > 0 and p <= 1:
				dp[m][j3][j2] = (c3 * p3 + c2 * p2 + c1 * p1) / p + 1 / p
			
print(dp[n][i3][i2])


### FIXED CODE ###

import sys
input = sys.stdin.readline
'''
allinputs = iter(input().splitlines())
input = lambda : next(allinputs)
#'''
N = int(input())
a = list(map(int, input().split()))
a.sort(reverse = True)
dp = [[[0] * (N + 1) for _ in range(N + 1)] for _ in range(N + 1)]
#dp[i3][i2][i1]...皿を寿司の数が多い順に並べたとき、i1, i2, i3 はそれぞれ寿司の数が1, 2, 3個の皿が終わる点(スライス)。dpはそのときの期待値。
i3, i2, i1 = 0, 0, 0

for i in range(N):
	if a[i] == 3:
		i3 = i + 1
		i2 = i3
		i1 = i3
	elif a[i] == 2:
		i2 = i + 1
		i1 = i2
	elif a[i] == 1:
		i1 = i + 1
		
c1, c2, c3 = 0, 0, 0

for j3 in range(0, i3 + 1):
	for j2 in range(j3, i2 + 1):
		for j1 in range(j2, i1 + 1):
			#サイコロで3貫の皿が出たときの処理
			if j3 > 0:
				c3 = dp[j3 - 1][j2][j1]
				p3 = j3 / N
			else:
				p3 = 0
			
			#2貫
			if j2 > j3:
				c2 = dp[j3][j2 - 1][j1] 
				p2 = (j2 - j3) / N
			else:
				p2 = 0
			
			#1貫
			if j1 > j2:
				c1 = dp[j3][j2][j1 - 1]
				p1 = (j1 - j2) / N
			else:
				p1 = 0
			
			p = p3 + p2 + p1
			if p > 0:
				dp[j3][j2][j1] = (c3 * p3 + c2 * p2 + c1 * p1) / p + 1 / p
			
print(dp[i3][i2][i1])
### BUGGY CODE ###

from collections import defaultdict
import bisect

alphabet="abcdefghijklmnopqrstuvwxyz"

bS = int(input())
S= input()
nQ = int(input())

S = [i for i in S]

query = []
for i in range(nQ):
  query.append(input().split())

locs =defaultdict(list)

for i,char in enumerate(S):
    locs[char].append(i)
    
def countChars(iter,ss,ee):
  nChar = 0
  for i in alphabet:
    if len(locs[i]) == 0:
      pass
    else:
      sptr = bisect.bisect_right(locs[i],ss)
      eptr = bisect.bisect_left(locs[i],ee)
      if sptr == eptr:
        if sptr < 1 or sptr > len(locs[i]):
          continue
        else:
          if locs[i][sptr-1] == ss:
            nChar+=1
      else:
        nChar += 1
  return nChar
    
  
res = []
for iter,iQ in enumerate(query):
  if int(iQ[0]) == 2:
    res.append(str( countChars(iter,int(iQ[1])-1,int(iQ[2])) ))
  if int(iQ[0]) == 1:
    location = int(iQ[1])-1
    curChar  = S[location]
    if curChar != iQ[2]:
      locs[curChar].remove(location) #remove from old
      bisect.insort(locs[iQ[2]],location)
      S[location] = iQ[2]
      
print(" ".join(res))

  

### FIXED CODE ###

from collections import defaultdict
import bisect

alphabet="abcdefghijklmnopqrstuvwxyz"

bS = int(input())
S= input()
nQ = int(input())

S = [i for i in S]

query = []
for i in range(nQ):
  query.append(input().split())

locs =defaultdict(list)

for i,char in enumerate(S):
    locs[char].append(i)
    
def countChars(iter,ss,ee):
  nChar = 0
  for i in alphabet:
    if len(locs[i]) == 0:
      pass
    else:
      sptr = bisect.bisect_right(locs[i],ss)
      eptr = bisect.bisect_left(locs[i],ee)
      if sptr == eptr:
        if sptr < 1 or sptr > len(locs[i]):
          continue
        else:
          if locs[i][sptr-1] == ss:
            nChar+=1
      else:
        nChar += 1
  return nChar
    
  
res = []
for iter,iQ in enumerate(query):
  if int(iQ[0]) == 2:
    res.append(str( countChars(iter,int(iQ[1])-1,int(iQ[2])) ))
  if int(iQ[0]) == 1:
    location = int(iQ[1])-1
    curChar  = S[location]
    if curChar != iQ[2]:
      locs[curChar].remove(location) #remove from old
      bisect.insort(locs[iQ[2]],location)
      S[location] = iQ[2]
      
print(" ".join(res))
### BUGGY CODE ###

from collections import deque

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

G = dict()
for i in range(1, N + 1):
    G[i] = dict()

for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a][b] = 1
    G[b][a] = 1

parents = [0] * (N + 1)
values = [0] * (N + 1)
values_sum = [-1] * (N + 1)

for _ in range(Q):
    p, x = map(int, input().split())
    values[p] += x

# solve
values_sum[1] = values[1]

queue = deque([1])
cnt = 0
while len(queue) > 0:
    p = queue.popleft()
    for q in G[p].keys():
        if G[p][q] == 1 and values_sum[q] == -1:
            values_sum[q] = values_sum[p] + values[q]
            queue.append(q)
            cnt += 1
    if cnt > 2 * N:
        print(0)

print(*values_sum[1:])


### FIXED CODE ###

from collections import defaultdict

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

G = defaultdict(list)

for _ in range(N - 1):
    a, b = map(int, input().split())
    G[a].append(b)
    G[b].append(a)

parents = [0] * (N + 1)
values = [0] * (N + 1)
values_sum = [-1] * (N + 1)

for _ in range(Q):
    p, x = map(int, input().split())
    values[p] += x

# solve
values_sum[1] = values[1]

queue = [1]
while len(queue) > 0:
    p = queue.pop()
    for q in G[p]:
        if values_sum[q] == -1:
            values_sum[q] = values_sum[p] + values[q]
            queue.append(q)

print(*values_sum[1:])
### BUGGY CODE ###

S = input()
cnt = 0
is_end = [False] * (len(S) + 1)
for i in range(len(S)):
    if is_end[i]:
        continue
    is_end[i] = True
    bingo = [i]
    for j in range(i+1, len(S)+1):
        if int(S[i:j]) % 2019 == 0:
            is_end[j] = True
            bingo.append(j)
    l = len(bingo)
    if l >= 2:
        cnt += int(l*(l-1)/2)
print(cnt)


### FIXED CODE ###

S = input()
mod_bucket = [0] * 2019
mod_bucket[0] += 1

_S = S[::-1]
mod = 0
p = 1
for i in range(len(S)):
    mod = (p * int(_S[i]) + mod) % 2019
    mod_bucket[mod] += 1
    p *= 10
    p %= 2019

ans = sum([mod*(mod-1)/2 for mod in mod_bucket])
print(int(ans))
### BUGGY CODE ###

import copy

N = int(input())
A = [int(input()) for i in range(N)]

for i in range(N):
    tmp = copy.deepcopy(A)
    tmp[i] = 0
    print(max(tmp))

### FIXED CODE ###

import copy

N = int(input())
A = [int(input()) for i in range(N)]

A_original = copy.deepcopy(A)
A.sort()

for i in range(N):
    if A_original[i] == A[-1]:
        print(A[-2])
    else:
        print(A[-1])
### BUGGY CODE ###

n = int(input())
v = list(map(int,input().split()))
v_odd = []
v_even = []
for i in range(n//2):
    v_odd.append(v[2*i])
    v_even.append(v[2*i+1])
p1 = 0
p2 = 0
q1 = 0
q2 = 0
o_max = -1
e_max = -1
for i in range(n//2):
    a = v_odd[i]
    b = v_even[i]
    x = v_odd.count(a)
    y = v_even.count(b)
    if p1 <= x:
        if o_max != a:
            o_max = a
            p2 = p1
            p1 = x
    else:
        if x > p2:
            p2 = x
    if q1 <= y:
        if e_max != b:
            e_max = b
            q2 = q1
            q1 = y
    else:
        if y > q2:
            q2 = y
s = p1 + q1
if o_max == e_max:
    s = max(p1+q2,q1+p2)
ans = n-s
print(ans)

### FIXED CODE ###

n = int(input())
v = list(map(int,input().split()))
v_odd = []
v_even = []
d_odd = {}
d_even = {}
o = []
e = []
for i in range(n//2):
    a = v[2*i]
    b = v[2*i+1]
    if a in d_odd:
        d_odd[a] += 1
    else:
        d_odd[a] = 1
        o.append(a)
    if b in d_even:
        d_even[b] += 1
    else:
        d_even[b] = 1
        e.append(b)
O = 0
E = 0
o_max = 0
o_second = 0
e_max = 0
e_second = 0
for i in o:
    x = d_odd[i]
    if x >= o_max:
        O = i
        o_max = x
d_odd.pop(O)
o.remove(O)
for i in o:
    x = d_odd[i]
    if x >= o_second:
        o_second = x
for i in e:
    y = d_even[i]
    if y >= e_max:
        E = i
        e_max = y
d_even.pop(E)
e.remove(E)
for i in e:
    y = d_even[i]
    if y >= e_second:
        e_second = y
if O == E:
    m = max(o_max+e_second,e_max+o_second)
else:
    m = o_max + e_max
print(n-m)
### BUGGY CODE ###

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

rec = [[0] * n for _ in range(n)]
for i in range(n):
    mn = a[i]
    for j in range(n):
        mn = min(mn, a[i-j])
        rec[i][j] = mn

sm_li = []
for j in range(n):
    sm = 0
    for i in range(n):
        sm += rec[i][j]
    sm_li.append(sm)

ans = float("inf")
for j in range(n):
    second = sm_li[j] + j * x
    ans = min(ans, second)

print(ans)


### FIXED CODE ###

import numpy as np

n, x = map(int, input().split())
a = np.array(list(map(int, input().split())), dtype=np.int32)

rec = np.zeros((n, n), dtype=np.int32)
for i in range(n):
    a_tmp = np.concatenate([a[i::-1], a[-1:i:-1]])
    np.minimum.accumulate(a_tmp, out=rec[i])

ans = float("inf")
for j in range(n):
    second = rec[:, j].sum() + j * x
    ans = min(ans, second)

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

import sys
import time
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N, Q = MAP()
S = input().rstrip()
LR = [MAP() for _ in range(Q)]

loc = [0]*N
#start = time.time()
for i in range(N-1):
	if S[i]+S[i+1] == 'AC': loc[i] += 1
#print(loc)
#elapsed_time = time.time() - start
#print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

start = time.time()
for l, r in LR:
	print(sum(loc[l-1:r-1]))
	#tmp = (loc[r-1]-loc[l-1])
elapsed_time = time.time() - start
#print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

### FIXED CODE ###

import sys
import time
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N, Q = MAP()
S = input().rstrip()
LR = [MAP() for _ in range(Q)]

loc = [0]*N
for i in range(N-1):
	if S[i]+S[i+1] == 'AC':
		loc[i+1] += loc[i]+1
	else:
		loc[i+1] = loc[i]
#print(loc)

for l, r in LR:
	print(loc[r-1]-loc[l-1])
### BUGGY CODE ###



import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

import math
from fractions import gcd

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

# 最大公約数
g = gcd(A, B)

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

ggg = []
for i in range(1, g+1):
    if A%i == 0 and B%i == 0:
        ggg.append(i)

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

prime = get_sieve_of_eratosthenes(g)
phash = {}
for p in prime:
    phash[p] = True

#print(prime)
#print(phash)

print( len(set(ggg) & set(prime)) +1 )

### FIXED CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

from fractions import gcd

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

# 最大公約数
g = gcd(A, B)

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

def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a

print(len(prime_factorize(g)) +1)
### BUGGY CODE ###

import sys
from itertools import accumulate

import numpy as np

def _sum_ob_divisors(n):
    def f(n, x):
        y = n // x
        return y * (y + 1) * x / 2
    return sum(f(n, i) for i in range(1, n + 1))


def _sum_ob_divisors(n):
    # L = [1] * (n + 1)
    L = np.ones(n + 1, dtype=np.int64)
    for i in range(2, n + 1):
        # for j in range(i, n + 1, i):
        #     L[j] += 1
        L[i:n + 1:i] += 1
    # print(f'{L=}')
    return sum(i * x for i, x in enumerate(L))


def sum_ob_divisors(f):
    n = int(f.read())

    return _sum_ob_divisors(n)


def main():
    ans = sum_ob_divisors(sys.stdin.buffer)
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

# import numpy as np

def _sum_ob_divisors(n):
    def f(n, x):
        y = n // x
        return y * (y + 1) * x // 2
    return sum(f(n, i) for i in range(1, n + 1))


# def _sum_ob_divisors(n):
#     L = [1] * (n + 1)
#     # L = np.ones(n + 1, dtype=np.int64)
#     for i in range(2, n + 1):
#         for j in range(i, n + 1, i):
#             L[j] += 1
#         # L[i:n + 1:i] += 1
#     # print(f'{L=}')
#     return sum(i * x for i, x in enumerate(L))


def sum_ob_divisors(f):
    n = int(f.read())

    return _sum_ob_divisors(n)


def main():
    ans = sum_ob_divisors(sys.stdin.buffer)
    print(ans)


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

A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
x = [int(input()) for _ in range(Q)]
inf = 10 ** 18

s.insert(0, -inf)
s.insert(A + 1, inf)
t.insert(0, -inf)
t.insert(B + 1, inf)

def binsearch_l(seq, l, r, tar):
    if r - l < 2: return l
    #
    m = l + (r - l) // 2
    # print("##", l, r, (m, seq[m]), tar)
    if seq[m] <= tar:
        return binsearch_l(seq, m, r, tar)
    else:
        return binsearch_l(seq, l, m, tar)

for x_tmp in x:
    i_l = binsearch_l(s, 0, A + 2, x_tmp)
    j_l = binsearch_l(t, 0, B + 2, x_tmp)
    #
    i_l = 1 if i_l < 1 else (A - 1 if i_l > A - 1 else i_l)
    j_l = 1 if j_l < 1 else (B - 1 if j_l > B - 1 else j_l)
    #
    ans = inf
    for i, j in ((i_l, j_l), (i_l + 1, j_l), (i_l, j_l + 1), (i_l + 1, j_l + 1)):
        ans_tmp_s = abs(x_tmp - s[i]) + abs(s[i] - t[j])
        ans_tmp_t = abs(x_tmp - t[j]) + abs(s[i] - t[j])
        ans_tmp = min(ans_tmp_s, ans_tmp_t)
        # print("#", x_tmp, s[i], t[j], ans_tmp)
        if ans > ans_tmp:
            ans = ans_tmp
    #
    print(ans)

### FIXED CODE ###

import sys, bisect
input = sys.stdin.readline
A, B, Q = map(int, input().split())
s = [int(input()) for _ in range(A)]
t = [int(input()) for _ in range(B)]
x = [int(input()) for _ in range(Q)]
inf = 10 ** 18

s = [-inf] + s + [inf]
t = [-inf] + t + [inf]

ans_Q = [None] * Q
i_last = j_last = 0
for idx, x_tmp in sorted(enumerate(x), key=lambda x: x[1]):
    i_l = max(0, bisect.bisect_left(s, x_tmp, lo=i_last) - 1)
    j_l = max(0, bisect.bisect_left(t, x_tmp, lo=j_last) - 1)
    # print("#", x_tmp, (i_l, s[i_l]), (j_l, t[j_l]))
    #
    ans = inf
    for i, j in ((i_l, j_l), (i_l + 1, j_l), (i_l, j_l + 1), (i_l + 1, j_l + 1)):
        if i < 1 or A < i: continue
        if j < 1 or B < j: continue
        ans_tmp_s = abs(x_tmp - s[i]) + abs(s[i] - t[j])
        ans_tmp_t = abs(x_tmp - t[j]) + abs(s[i] - t[j])
        ans_tmp = min(ans_tmp_s, ans_tmp_t)
        # print("#", x_tmp, s[i], t[j], ans_tmp)
        if ans > ans_tmp:
            ans = ans_tmp
    #
    i_last, j_last = i_l, j_l
    ans_Q[idx] = ans

for ansi in ans_Q: print(ansi)
### BUGGY CODE ###

N = int(input())

yaku = []

for i in range(1, N+1):
    if N % i == 0:
        if i in yaku:
            break
        if N/i <= i:
            yaku.append(i)
            break
        yaku.append(i)
        yaku.append(int(N/i))
yaku.sort()
ans = str(yaku[len(yaku)//2])
print(len(ans))


### FIXED CODE ###

N = int(input())

yaku = []

for i in range(1, N+1):
    if N % i == 0:
        if i in yaku:
            break
        if N/i <= i:
            yaku.append(i)
            break
        yaku.append(i)
        yaku.append(N//i)
    elif N/i < i:
        break

yaku.sort()
ans = str(yaku[len(yaku)//2])
print(len(ans))
### BUGGY CODE ###

# 色の最大は辺が一番多い頂点
# 各頂点が現在持ってる色を覚える -> 2次元配列 : color_num = [[]*N]
# 答えを出力するための部分 -> 2次元配列 : ans = [[] * N for _ in range(N)]
# 答えの出し方はN-1ループでa[i], b[i]をansにいれる

from collections import deque
N = int(input())
graph = [[] * N for _ in range(N)]
A = [0] * (N-1)
B = [0] * (N-1)
for i in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    A[i] = a
    B[i] = b
K = 0
for i in range(N):
    K = max(len(graph[i]), K)

ans = [[0] * N for _ in range(N)]

# BFSのためのデータ構造
dist = [False for _ in range(N)]
que = deque()

# 初期条件
dist[0] = True
que.append(0)
color_num = [[] for _ in range(N)]

# BFS開始
while que:
    v = que[0]
    que.popleft()
    for new_v in graph[v]:
        if dist[new_v]:   # すでに探索済みの頂点は探索しない
            continue
        # 新たな頂点 new_vについて距離情報を更新してキューを追加する
        dist[new_v] = True
        que.append(new_v)
        for k in range(1, K+1):
            if k in color_num[v]:
                continue
            if k in color_num[new_v]:
                continue
            else:
                ans[v][new_v] = k
                ans[new_v][v] = k
                color_num[v].append(k)
                color_num[new_v].append(k)
                break
        

# 答えの出力
print(K)
for i in range(N-1):
    print(ans[A[i]][B[i]])

### FIXED CODE ###

#幅優先探索
from collections import deque
d=deque()
e=deque()
import sys
sys.setrecursionlimit(1000000000)
n=int(input())
start_node=0
querie=[]
edge={i:[]for i in range(1,n+1)}
for j in range(n-1):
    a,b=map(int,input().split())
    querie.append((a,b))
    edge[a].append(b)
    edge[b].append(a)
    if j==0:
        start_node=a  

d.append((start_node,0))

#はじめにdequeに入れておいて幅優先探索を行うものを決める。そして、塗り分けの結果はans_dictに保存する
#print(edge) 
ans_dict={i:{}for i in range(1,n+1)}
K=0
for some in edge.values():
    K=max(K,len(some))
    
#幅優先探索に使用する すでに訪れたか確認するためのリスト

visited=[False for i in range(n+1)]
visited[start_node]=True

#使う頂点の数を記録した
#nodeをリスト型にしたリストを返す
#start_nodeを記録しておく
def determine_edge_color(node,color):
    new_color=0
    for some in edge[node]:
        if visited[some]==False:
            visited[some]=True
            new_color+=1
            if new_color==color:
                new_color+=1
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
            else:
                ans_dict[node][some]=new_color
                ans_dict[some][node]=new_color
                e.append((some,new_color))
        else:
            pass
            
while d:
    for some in d:
        if visited[some[0]]==True:
            determine_edge_color(some[0],some[1])
        else:
            determine_edge_color(some[1],some[0])
    d=e
    e=deque()
    
#ans_dictの完成
print(K)
#答えの出力
for item in querie:
    a,b=item[0],item[1]
    print(ans_dict[a][b])
### BUGGY CODE ###

N, K = map(int, input().split())
p = [(int(x)+1)/2 for x in input().split()]
ans = 0
for n in range(N-K+1):
    ans = max(sum(p[n:n+K]),ans)
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
p = [(int(x)+1)/2 for x in input().split()]
cm = [0]
for n in p:
    cm.append(cm[-1]+n)
ans = 0
for n in range(N-K+1):
    ans = max(cm[n+K]-cm[n],ans)
print(ans)
### BUGGY CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
h,w,k=map(int,input().split())
s = []
for i in range(h):
    str=input()
    tmp=[]
    for j in range(w):
        if str[j]=="0":
            tmp.append(0)
        else:
            tmp.append(1)
    s.append(tmp)


tdiv=2**(h-1)
import numpy as np
s = np.array(s)
ans = 100100100
for i in range(tdiv):
    lis=[]
    tmp=np.copy(s[0,:])
    cnt = 0
    #print(s)
    for j in range(h-1):
        if (i>>j&1):
            tmp+=s[j+1,:]
        else:
            lis.append(tmp)
            tmp=np.copy(s[j+1,:])
            cnt+=1
    lis.append(tmp)
    lis = np.array(lis)
    clis=np.zeros(cnt+1)
    #print(lis,cnt)
    for ind in range(w):
        if lis[:,ind].max()>k:
            cnt=10010010
            break
        clis+=lis[:,ind]
        if clis.max()>k:
            clis=lis[:,ind]
            cnt+=1
    #print(cnt)
    ans = min(ans,cnt)
print(ans)


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
h,w,k=map(int,input().split())
s = []
for i in range(h):
    str=input()
    tmp=[]
    for j in range(w):
        if str[j]=="0":
            tmp.append(0)
        else:
            tmp.append(1)
    s.append(tmp)

tdiv=2**(h-1)
#import numpy as np
#s = np.array(s)
ans = 100100100
for i in range(tdiv):
    lis=[]
    #tmp=np.zeros(w)
    #tmp+=s[0,:]
    tmp=[s[0][ii] for ii in range(w)]
    cnt = 0
    #print(tmp)
    for j in range(h-1):
        if (i>>j&1):
            #tmp+=s[j+1,:]
            tmp=[tmp[ii]+s[j+1][ii] for ii in range(w)]
        else:
            lis.append(tmp)
            #tmp=np.zeros(w)
            #tmp+=s[j+1,:]
            tmp=[s[j+1][ii] for ii in range(w)]
            cnt+=1
    lis.append(tmp)
    #lis = np.array(lis)
    #clis=np.zeros(cnt+1)
    clis=[0 for ii in range(cnt+1)]
    #print(lis,cnt)
    tmpcnt=cnt
    for ind in range(w):
        #if any(d>k for d in lis[:,ind]):
        #if lis[:,ind].max()>k:
        if max([lis[ii][ind] for ii in range(tmpcnt+1)])>k:
            cnt=10010010
            break
        clis=[lis[ii][ind]+clis[ii] for ii in range(tmpcnt+1)]
        #if clis.max()>k:
        if max(clis)>k:
            clis=[lis[ii][ind] for ii in range(tmpcnt+1)]
            cnt+=1
    #print(cnt)
    ans = min(ans,cnt)
print(ans)