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

N = int(input())

dp = [0 for _ in range(N+1)]
for x in range(1,N):
    if x * x > N:
        continue
    for y in range(1,N):
        if x * x + y * y + x * x > N:
            continue
        for z in range(1,N):
            t = x * x + y * y + z * z + x * y + y * z + z * x
            if t <= N:
                dp[t] += 1

for i in range(1,N+1):
    print(dp[i])

### FIXED CODE ###

N = int(input())

dp = [0 for _ in range(N+1)]
for x in range(1,int(N**0.5)+1):
    for y in range(1,int(N**0.5)+1):
        for z in range(1,int(N**0.5)+1):
            t = x * x + y * y + z * z + x * y + y * z + z * x
            if t <= N:
                dp[t] += 1

for i in range(1,N+1):
    print(dp[i])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
if True:
    n = int(input())
    an= list(map(int, input().split()))

else:
   n=5
   an=[1,1,2,1,2]


for k in range(0,n):
    an2 = an[:]
    del an2[k]
    # print(an2)
    ans = 0
    for b1 in range(0,n-1):
        for b2 in range(b1+1,n-1):
            if an2[b1] == an2[b2]:
                ans += 1
    print(int(ans))
    an2.clear()

### FIXED CODE ###

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

datas = [0] * (n+1)
for a in an:
    datas[a] += 1

ans = 0
for i in range(1,n+1):
    if datas[i] > 1:
        ans += datas[i] * (datas[i]-1)/2
ans = int(ans)

for k in range(0,n):
    if datas[an[k]] > 1:
        print(int(ans - datas[an[k]] * (datas[an[k]]-1)/2 + (datas[an[k]]-1) * (datas[an[k]]-2)/2))
    else:
        print(ans)
### BUGGY CODE ###

N,Q=map(int,input().split())
S=input()
LR=[list(map(int,input().split())) for _ in range(Q)]

F=[0]*len(S)
for i in range(N):
    if S[i:i+2]=='AC':
        F[i]=1
for l,r in LR:
    print(sum(F[l-1:r-1]))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
LR=[list(map(int,input().split())) for _ in range(Q)]

F=[0]*len(S)
for i in range(N-1):
    F[i+1]+=F[i]+(1 if S[i:i+2]=='AC' else 0)
    #print(i,F,S[i:i+2])
for l,r in LR:
    print(F[r-1]-F[l-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin
import numpy as np
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()
a_list = []
for i in range(N):
    temp = _li_()
    temp.append(i-N)  # 番兵
    a_list.append(temp)
a_list = np.array(a_list)

n_index = np.arange(N)
a_index = np.zeros(N, dtype=int)
ans = 0

first = a_list[:, 0]
target = n_index[first[first] == n_index].tolist()
a_index[target] += 1
for i in range(N * (N-1) // 2):
    next_target = set()
    for t in target:
        if t in next_target:
            continue
        cand = a_list[t, a_index[t]]
        if a_list[cand, a_index[cand]] == t:
            next_target.add(t)
            next_target.add(cand)

    target = list(next_target)
    a_index[target] += 1
    ans += 1
    if len(target) == 0:
        break

if a_index.sum() == (N-1) * N:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

from sys import stdin
# import numpy as np
from collections import deque
# import sys
# sys.setrecursionlimit(10**4)

def _li(): return list(map(int, stdin.readline().split()))
def _li_(): return list(map(lambda x: int(x)-1, stdin.readline().split()))
def _lf(): return list(map(float, stdin.readline().split()))
def _ls(): return stdin.readline().split()
def _i(): return int(stdin.readline())
def _f(): return float(stdin.readline())
def _s(): return stdin.readline()[:-1]


N = _i()

move_in = [[[] for i in range(N)] for j in range(N)]
move_out = [[[] for i in range(N)] for j in range(N)]
cost = [[0] * N for _ in range(N)]
start_pair = []
for i in range(N):
    a_list = _li_()
    start_pair.append(a_list[0])
    for j in range(N-2):
        start = [min(i, a_list[j]), max(i, a_list[j])]
        end = [min(i, a_list[j+1]), max(i, a_list[j+1])]
        move_in[end[0]][end[1]].append((start[0], start[1]))
        move_out[start[0]][start[1]].append((end[0], end[1]))

count = 0
stack = deque([])
for i in range(N):
    pair = start_pair[i]
    if i < pair and i == start_pair[pair]:
        stack.append((i, start_pair[i]))
        cost[i][start_pair[i]] = 1
        count += 1


ans = 0
while stack:
    cand = stack.pop()
    for dest in move_out[cand[0]][cand[1]]:
        cost[dest[0]][dest[1]] = max(cost[dest[0]][dest[1]],
                                     cost[cand[0]][cand[1]] + 1)
        in_list = move_in[dest[0]][dest[1]]
        if in_list[0] == cand:
            del in_list[0]
        else:
            del in_list[1]
        if len(in_list) == 0:
            count += 1
            if len(move_out[dest[0]][dest[1]]) == 0:
                ans = max(ans, cost[dest[0]][dest[1]])
            else:
                stack.append(dest)

if count == (N * (N-1) // 2):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

N,Q = map(int,input().split())
if N == 1:
    for i in range(Q):
        print(min(map(int,input().split())))
    exit()

src = [tuple(map(int,input().split())) for i in range(Q)]
for a,b in src:
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    print(a)


### FIXED CODE ###

N,Q = map(int,input().split())
if N == 1:
    for i in range(Q):
        print(min(map(int,input().split())))
    exit()

def solve(s):
    a,b = map(int,s.split())
    while a != b:
        if a < b: a,b = b,a
        a = (a+N-2) // N
    return str(a)

print('\n'.join(map(solve, [input() for i in range(Q)])))
### BUGGY CODE ###

# -*- coding:utf8 -*-

n = int(input())
l = [int(input()) for _ in range(n)]
for i in range(n):
    print(max(l[:i] + l[i+1:]))

### FIXED CODE ###

# -*- coding:utf8 -*-

n = int(input())
l = [int(input()) for _ in range(n)]
m = max(l)
n = sorted(l)[-2]
for i in l:
    if i != m:
        print(m)
    else:
        print(n)
### BUGGY CODE ###

import sys
buf = sys.stdin.buffer
input = buf.readline
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    def add(self, i, x):
        n, tree = self.n, self.tree
        while i <= n:
            tree[i] += x
            i += i & -i
    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
def main():
    n, q = map(int, input().split())
    res = [0] * q
    *c, = map(int, input().split())
    q = [(r, l, i) for i, (l, r) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
    q.sort()
    bit = BIT(n + 2)
    add, sum = bit.add, bit.sum
    b = [1] * (n + 1)
    j = 1
    for r, l, i in q:
        while j <= r:
            d = c[j - 1]
            j += 1
            k = b[d]
            b[d] = j
            add(k + 1, 1)
            add(j + 1, -1)
        res[i] = sum(l + 1)
    print(' '.join(map(str, res)))
main()

### FIXED CODE ###

import sys
from operator import itemgetter
buf = sys.stdin.buffer
input = buf.readline
class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    def add(self, i, x):
        n, tree = self.n, self.tree
        while i <= n:
            tree[i] += x
            i += i & -i
    def sum(self, i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
def main():
    n, q = map(int, input().split())
    res = [0] * q
    *c, = map(int, input().split())
    q = [(i, l, r) for i, (l, r) in enumerate(zip(*[map(int, buf.read().split())] * 2))]
    q.sort(key=itemgetter(2))
    bit = BIT(n + 2)
    add, sum = bit.add, bit.sum
    b = [1] * (n + 1)
    j = 1
    for i, l, r in q:
        while j <= r:
            d = c[j - 1]
            j += 1
            k = b[d]
            b[d] = j
            add(k + 1, 1)
            add(j + 1, -1)
        res[i] = sum(l + 1)
    print(' '.join(map(str, res)))
main()
### BUGGY CODE ###

import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))

MOD = 10**9 + 7


def main():
	# ans_ = []
	# ans_.append(ans)
	# print(("\n").join(map(str, ans_)))
	n = int(input())
	s = 0
	while n:
		s += n%10
		s %= 9
		n //= 10
	print("YNeos"[s!=0::2])






if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
from math import sqrt, gcd, ceil, log, floor
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
input = sys.stdin.readline
read = lambda: list(map(int, input().strip().split()))

MOD = 10**9 + 7


def main():
	# ans_ = []
	# ans_.append(ans)
	# print(("\n").join(map(str, ans_)))
	n = input().strip()#10**200000 - 1#int(input())
	i = 0
	s = 0
	while i < len(n):
		# print(n)
		s += int(n[i])
		s %= 9
		i += 1
	print("YNeos"[s!=0::2])






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

a, b, c, k = map(int, input().split())
s = 0
while(0 < a and 0 < k):
    s += 1
    k -= 1
    a -= 1
while(0 < b and 0 < k):
    k -= 1
    b -= 1
while(0 < c and 0 < k):
    s -= 1
    k -= 1
    c -= 1
print(s)


### FIXED CODE ###

a, b, c, k = map(int, input().split())
s = 0
if a >= k:
    s = k
elif  a + b >= k:
    s = a
else:
    s = a - (k - a - b) 
print(s)
### BUGGY CODE ###

#
import sys
import math
import numpy as np
import itertools

# いくつか入力
n,p = (int(i) for i in input().split())
# 空白区切りの数列をリストに代入
s = [int(i) for i in list(input())] 

answer = 0
#print(s)
for i in range(n):
    q=0
    for j in range(i,n):
        q=q*10+s[j]
        if q%p==0:
            answer += 1
print(answer)



### FIXED CODE ###

#
import sys
import math
#import numpy as np
import itertools
from collections import Counter
# いくつか入力
n,p = (int(i) for i in input().split())
# 空白区切りの数列をリストに代入
s = [int(i) for i in list(input())] 

answer = 0
#print(s)
q=0
x=[]
if p == 2 or p == 5:
    for i in range(n-1,-1,-1):
        if s[i]%p == 0:
            answer += i+1
else:
    d=1
    for i in range(n-1,-1,-1):
        q = (d*s[i]+q)%p
        x.append(q)
        d = (d * 10)%p
    #print(x)
    counter = Counter(x)
    #print(counter)

    for k in counter:
    #    print(k)
        if k==0:
            answer += counter[k] * (counter[k]+1) // 2
        else:
            answer += counter[k] * (counter[k]-1) // 2

print(answer)
### BUGGY CODE ###

N=int(input())
x=1
if(N>1):
 for i in range(N+1):
  for j in range(int(i/2)):
   if(i==j*j):
    x=i
if(4<=N<=8):
 x=4
print(x)


### FIXED CODE ###

import math
N=int(input())
n=math.sqrt(N)
m=math.floor(n)
print(m*m)
### BUGGY CODE ###

N=int(input())
g=[[] for i in range(N)] 
cnt=0
for i in range(N):
  s=input()
  for j in range(N):
    if s[j]=='1':
      g[i].append(j)
      cnt+=1
w=cnt//2

color=[0]*N #color[i]:点iの色(1 or -1)。但し塗られていないときは0とする

def f(v,c):
    #頂点vに隣接する頂点全てを塗るあるいは判定する
    color[v] = c
    for i in range(len(g[v])):
        if color[g[v][i]]==c:
            return False
        elif color[g[v][i]]==0 and not f(g[v][i],-c):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True

def warshall(d,n):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

k=1
for i in range(N):
  if color[i]==0:
    if not f(i,1):
      k=-1

if k==-1:
  print(-1)
else:
  d=[[float('inf')]*N for i in range(N)]
  for i in range(N):
    for j in g[i]:
      d[i][j]=1
  for i in range(N):
    d[i][i]=0
  A=warshall(d,N)
  ans=0
  for i in range(N):
    for j in range(N):
      ans=max(ans,d[i][j])
  print(ans+1)

### FIXED CODE ###

N=int(input())
g=[[] for i in range(N)] 
cnt=0
for i in range(N):
  s=input()
  for j in range(N):
    if s[j]=='1':
      g[i].append(j)
      cnt+=1
w=cnt//2

color=[0]*N #color[i]:点iの色(1 or -1)。但し塗られていないときは0とする

def f(v,c):
    #頂点vに隣接する頂点全てを塗るあるいは判定する
    color[v] = c
    for i in range(len(g[v])):
        if color[g[v][i]]==c:
            return False
        elif color[g[v][i]]==0 and not f(g[v][i],-c):
            #(g[v][i]がまだ塗られていない　かつ　そこを-cで塗っても問題ない) ではないなら
            return False
    return True

def warshall(d,n):
  for k in range(n):
    for i in range(n):
      for j in range(n):
        d[i][j]=min(d[i][j],d[i][k]+d[k][j])
  return d

k=1
for i in range(N):
  if color[i]==0:
    if not f(i,1):
      k=-1

if k==-1:
  print(-1)
else:
  d=[[float('inf')]*N for i in range(N)]
  for i in range(N):
    for j in g[i]:
      d[i][j]=1
  for i in range(N):
    d[i][i]=0
  A=warshall(d,N)
  ans=0
  for i in range(N):
    for j in range(N):
      ans=max(ans,d[i][j])
  print(ans+1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
for i in range(1, N + 1):
  print(A.count(i))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0 for i in range(N)]
for a in A:
  ans[a - 1] += 1
for a in ans:
  print(a)
### BUGGY CODE ###

from collections import deque
S = deque(input())
Q = int(input())
#W, H, N = map(int, input().split())
lst = []
for i in range(Q):
    lst.append(list(input().split()))
#print(lst)

for i in range(Q):
    if lst[i][0] == '1':
        S.reverse()
    else:
        if lst[i][1] == '1':
            S.appendleft(lst[i][2])
        else:
            S.append(lst[i][2])

print(''.join(S))

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
#W, H, N = map(int, input().split())
lst = []
for i in range(Q):
    lst.append(list(input().split()))
#print(lst)

flag = 'left' #文字列が左向き
for i in range(Q):
    if flag == 'left':
        if lst[i][0] == '1':
            flag = 'right'
        else:
            if lst[i][1] == '1':
                S.appendleft(lst[i][2])
            else:
                S.append(lst[i][2])
    else: #flag == right
        if lst[i][0] == '1':
            flag = 'left'
        else:
            if lst[i][1] == '1':
                S.append(lst[i][2])
            else:
                S.appendleft(lst[i][2])
if flag == 'left':
    print(''.join(S))
else:
    S.reverse()
    print(''.join(S))
### BUGGY CODE ###

#import math
N = int(input())
N_C = []
ans = 0

for i in range(1,N):
    N_C.append(N-i)
#print(N_C)

for i in N_C:
    for j in range(1,i+i):
        k=i//j
        if j*k == i:
            ans +=1

print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
for a in range(1,N):
    ans += (N-1)//a
print(ans)
### BUGGY CODE ###

n = int(input())
# 文字列内の文字を辞書順ソート
strings = [''.join(sorted(list(input()))) for i in range(n)]
# 重複文字列（＝元の文字列はアナグラムで一致する）と重複度の辞書
dictionaries = [[e, strings.count(e)] for e in set(strings)]
sum = 0
for d in dictionaries :
    q = d[1]
    sum += int(q * (q-1) / 2)
print(sum)

### FIXED CODE ###

n = int(input())
# 文字列内の文字を辞書順ソートしたリストを辞書順ソート
strings = sorted([''.join(sorted(list(input()))) for i in range(n)])
strings.append('XXXXXXXXXX')

ans = 0
s = 0
for i in range(1,n+1) :
    if strings[i] == strings[i-1] :
        s += 1
    else:
        s += 1
        ans += s * (s - 1)
        s = 0
print(int(ans/2))
### BUGGY CODE ###

n, w = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

# 最大化問題なので0で初期化
dp = [[0] * (w + 1) for _ in range(n + 1)]

# 品物iを選べる場合、前の行からsum_wから品物iの重さを引いた要素を参照する
for i in range(1, n + 1):
    for j in range(1, w + 1):
        if j - arr[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i - 1][0]] + arr[i - 1][1])
        else:
            dp[i][j] = dp[i - 1][j]

print(max(max(dp)))

### FIXED CODE ###

n, w = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

# 最大化問題なので0で初期化
dp = [[0] * (w + 1) for _ in range(n + 1)]

# 品物iを選ばない場合で更新してから、選べる場合は再更新
for i in range(1, n + 1):
    for j in range(w + 1):
        dp[i][j] = dp[i - 1][j]
        if j - arr[i - 1][0] >= 0:
            dp[i][j] = max(dp[i][j], dp[i - 1][j - arr[i - 1][0]] + arr[i - 1][1])

print(dp[n][w])
### BUGGY CODE ###

import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = LIST()
c = Counter(a)
a = sorted(a)

isprime = {a[i]:True for i in range(n)}

for i in range(n):
    if a[i] > a[-1]//2: break 
    if not isprime[a[i]]: continue
    for j in range(2, a[-1]//a[i]+1):
        if a[i]*j in a:
            isprime[a[i]*j] = False

diff = len([i for i in range(len(c)) if list(c.values())[i] != 1 and isprime[list(c.keys())[i]]])
print(list(isprime.values()).count(True)-diff)


### FIXED CODE ###

import sys
from math import factorial
from collections import Counter
from fractions import Fraction
import heapq, bisect, fractions
import math
import itertools
sys.setrecursionlimit(10 ** 5 + 10)
INF = 10**15 +5
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
MOD = 10**9 + 7

n = INT()
a = LIST()
c = Counter(a)
a = sorted(a)
M = max(a)
isprime = [0]*(M+1)

for i in range(n):
    if isprime[a[i]]==0:
        isprime[a[i]] = 1
        tmp = 2
        while a[i]*tmp < M+1:
            isprime[a[i]*tmp] = 2
            tmp += 1
    elif isprime[a[i]] == 1:
        isprime[a[i]] = 2

ans = 0
for ele in a:
    if isprime[ele] != 2:
        ans += 1
print(ans)
### BUGGY CODE ###

mod = 10**9 + 7

K = input()
D = int(input())

N = len(K)

dp = [[[0]*2 for _ in range(D)] for _ in range(N+1)]
dp[0][0][0] = 1

for i in range(1,N+1):
    for j in range(D):
        dp[i][(j+int(K[i-1])) % D][0] += dp[i-1][j][0]
        for k in range(int(K[i-1])):
            dp[i][(j+k) % D][1] += dp[i-1][j][0]
        for k in range(10):
            dp[i][(j+k) % D][1] += dp[i-1][j][1]
        
        dp[i][j][0] %= mod
        dp[i][j][1] %= mod

ans = (dp[N][0][0] + dp[N][0][1] - 1) % mod
print(ans)

### FIXED CODE ###

mod = 10**9 + 7

K = input()
D = int(input())

N = len(K)

dp = [[[0]*2 for _ in range(D)] for _ in range(N+1)]
dp[0][0][0] = 1

for i in range(1,N+1):
    for j in range(D):
        dp[i][(j+int(K[i-1])) % D][0] += dp[i-1][j][0]
        for k in range(int(K[i-1])):
            dp[i][(j+k) % D][1] += dp[i-1][j][0]
        for k in range(10):
            dp[i][(j+k) % D][1] += dp[i-1][j][1]
        
        dp[i][j][0] %= mod
        dp[i][j][1] %= mod

ans = (dp[N][0][0] + dp[N][0][1] - 1) % mod
print(ans)
### BUGGY CODE ###

X = input()

for i in range(len(X)):
    X = X.replace('ST', '')

print(len(X))

### FIXED CODE ###

X = input()
xlst = []
xlst.append(X[0])
for i in range(1, len(X)):
    if X[i] == 'S':
        xlst.append(X[i])
    else:
        if xlst != [] and xlst[-1] == 'T':
            xlst.append(X[i])
        elif xlst != [] and xlst[-1] == 'S':
            xlst.pop()
        else:
            xlst.append(X[i])

print(len(xlst))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [a[0]]
for i in range(n-1):
    ans.append(a[i+1])
    ans = ans[::-1]
print(*ans)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
print(*(a[::-2]+a[n%2::2]))
### BUGGY CODE ###

a = input().split()
n = int(a[0])
m = int(a[1])
qq = int(a[2])
ll = list()
rr = list()

for _ in range(m):
    a = input().split()
    ll.append(int(a[0]))
    rr.append(int(a[1]))

p = list()
q = list()

for _ in range(qq):
    a = input().split()
    p.append(int(a[0]))
    q.append(int(a[1]))

c = [[0 for _ in range(n)] for _ in range(n)]

for i in range(m):
    c[ll[i] - 1][rr[i] - 1] += 1

for i in range(n):
    for j in range(1, n):
        c[i][j] += c[i][j - 1]

for i in range(qq):
    r = 0

    for j in range(p[i] - 1, q[i]):
        r += c[j][q[i] - 1]
        if 1 < p[i]:
            r -= c[j][p[i] - 2]

    print(r)


### FIXED CODE ###

a = input().split()
n = int(a[0])
m = int(a[1])
qq = int(a[2])

x = [[0] * n for _ in range(n)]

for _ in range(m):
    a = input().split()
    x[int(a[0]) - 1][int(a[1]) - 1] += 1

c = list()

for i in range(n):
    c.append(list())
    for j in range(n):
        a = x[i][j]

        if 0 < j:
            a += c[i][j - 1]

        c[i].append(a)

z = list()

for i in range(n):
    z.append(list())
    for j in range(n):
        a = c[i][j]

        if 0 < i:
            a += z[i - 1][j]

        z[i].append(a)

for _ in range(qq):
    r = 0
    a = input().split()
    p = int(a[0])
    q = int(a[1])

    if 0 < q:
        r += z[q - 1][q - 1]

    if 0 < q and 1 < p:
        r -= z[q - 1][p - 2] + z[p - 2][q - 1]

    if 1 < p:
        r += z[p - 2][p - 2]

    print(r)
### BUGGY CODE ###

MOD = 998244353
FACT_MAX = 2 * 10 ** 5
fact = [(f := 1) if not i else (f := f * i % MOD) for i in range(FACT_MAX)]
def comb(n, r):
    return fact[n] * pow(fact[n - r], MOD - 2, MOD) * pow(fact[r], MOD - 2, MOD) % MOD
N, M, K = map(int, input().split())
total = 0
for k in range(K + 1):
    total = (total + comb(N - 1, k) * M * pow(M - 1, N - k - 1, MOD)) % MOD
print(total)

### FIXED CODE ###

MOD = 998244353
FACT_MAX = 2 * 10 ** 5
fact = [1] * FACT_MAX
for i in range(1, FACT_MAX):
    fact[i] = fact[i - 1] * i % MOD
def comb(n, r):
    return fact[n] * pow(fact[n - r], MOD - 2, MOD) * pow(fact[r], MOD - 2, MOD) % MOD
N, M, K = map(int, input().split())
total = 0
for k in range(K + 1):
    total = (total + comb(N - 1, k) * M * pow(M - 1, N - k - 1, MOD)) % MOD
print(total)
### BUGGY CODE ###

import heapq
N = int(input())
C = [[] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  C[i] = [x, y, i]
Cx = sorted(C, key=lambda c: c[0])
Cy = sorted(C, key=lambda c: c[1])
Q = []
for i in range(N - 1):
  heapq.heappush(Q, [Cx[i + 1][0] - Cx[i][0], Cx[i][2], Cx[i + 1][2]])
  heapq.heappush(Q, [Cy[i + 1][1] - Cy[i][1], Cy[i][2], Cy[i + 1][2]])
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
while cnt < N - 1:
  q = heapq.heappop(Q)
  if root(q[1]) != root(q[2]):
    R[q[2]] = q[1]
    cost += q[0]
    cnt += 1
print(cost)

### FIXED CODE ###

N = int(input())
Cx = [[0, 0] for i in range(N)]
Cy = [[0, 0] for i in range(N)]
for i in range(N):
  x, y = map(int, input().split())
  Cx[i] = [x, i]
  Cy[i] = [y, i]
Cx.sort()
Cy.sort()
Qx = sorted([[Cx[i + 1][0] - Cx[i][0], Cx[i][1], Cx[i + 1][1]] for i in range(N - 1)])
Qy = sorted([[Cy[i + 1][0] - Cy[i][0], Cy[i][1], Cy[i + 1][1]] for i in range(N - 1)])
R = [i for i in range(N)]
def root(n):
  if R[n] == n:
    return n
  else:
    R[n] = root(R[n])
    return R[n]
cnt = 0
cost = 0
x = 0
y = 0
while cnt < N - 1:
  if Qx[x][0] <= Qy[y][0]:
    q = Qx[x]
    x += 1
  else:
    q = Qy[y]
    y += 1
  r1 = root(q[1])
  r2 = root(q[2])
  if r1 != r2:
    R[r2] = q[1]
    cost += q[0]
    cnt += 1
print(cost)
### BUGGY CODE ###

N,K=map(int,input().split())
p=input().split()
def hope(a):
    numbers=[int(b) for b in range(1,a+1)]
    goukei=sum(numbers)
    return goukei/a
P=[int(z) for z in p]
numbers=[]
for y in range(N-K+1):
    w=0
    for x in range(K):
        w+=P[x+y]
    numbers.append(w)
place=numbers.index(max(numbers))
answer=0
for q in range(K):
    answer+=hope(P[place+q])
print(answer)


### FIXED CODE ###

N,K=map(int,input().split())
p=input().split()
P=[int(z) for z in p]
hopes=[(1+a)/2 for a in P]
S=sum(hopes[:K])
answers=[S]
for a in range(1,N-K+1):
    S=S+hopes[a+K-1]-hopes[a-1]
    answers.append(S)
print(max(answers))