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

N = int(input())
#N = 1000000
A = list(map(int, input().split()))
#A = [i+1 for i in range(1000000)]
p = {2*i+1: 1 for i in range(1, 500)}
for i in range(3, 1000, 2):
  for j in p:
    if j != i:
      if j % i == 0:
        p[j] = 0
L = [2]
for i in p:
  if p[i] == 1:
    L.append(i)
def gcd(x, y):
  k, l = x, y
  while l:
    k, l = l, k % l
  return k
g = A[0]
for i in range(1, N):
  g = gcd(g, A[i])
  if g == 1:
    break
if g > 1:
  print("not coprime")
else:
  D = {}
  for i in range(N):
    pnt = 0
    while A[i] != 1:
      cnt = 0
      while A[i] % L[pnt] == 0:
        cnt = 1
        A[i] //= L[pnt]
      if cnt:
        if L[pnt] in D:
          D[L[pnt]] += 1
        else:
          D[L[pnt]] = 1
      pnt += 1
      if pnt == len(L) and A[i] != 1:
        if A[i] in D:
          D[A[i]] += 1
        else:
          D[A[i]] = 1
        break
  if D == {}:
    print("pairwise coprime")
  else:
    if max(D[i] for i in D) > 1:
      print("setwise coprime")
    else:
      print("pairwise coprime")

### FIXED CODE ###

#ABC177E
N = int(input())
#N = 1000000
A = list(map(int, input().split()))
#A = [i+1 for i in range(1000000)]
p = {2*i+1: 1 for i in range(1, 500)}
for i in range(3, 1000, 2):
  for j in p:
    if j != i:
      if j % i == 0:
        p[j] = 0
L = [2]
for i in p:
  if p[i] == 1:
    L.append(i)
def gcd(x, y):
  k, l = x, y
  while l:
    k, l = l, k % l
  return k
g = A[0]
i = 0
nn = len(L)
while i < N:
  g = gcd(g, A[i])
  if g == 1:
    break
  i += 1
if g > 1:
  print("not coprime")
else:
  D = {}
  m = 0
  for i in A:
    pnt = 0
    x = i
    for j in L:
      cnt = False
      while x % j == 0:
        cnt = True
        x //= j
      if cnt:
        if j in D:
          D[j] += 1
          if D[j] == 2:
            m = 2
            break
        else:
          D[j] = 1
      pnt += 1
      if pnt == nn and x != 1:
        if x in D:
          D[x] += 1
          if D[x] == 2:
            m = 2
        else:
          D[x] = 1
        break
      if x == 1:
        break
    if m >= 2:
      break
  if D == {}:
    print("pairwise coprime")
  else:
    if m > 1:
      print("setwise coprime")
    else:
      print("pairwise coprime")
### BUGGY CODE ###

import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

cons = 10 ** 6
is_prime = [True] * (cons + 1)
Ds = [i for i in range(cons + 1)]
is_prime[0] = False
is_prime[1] = False
for i in range(2, int(cons**0.5) + 1):
    if not is_prime[i]:
        continue
    for j in range(i * 2, cons + 1, i):
        is_prime[j] = False
        if Ds[j] == j:
          Ds[j] = i
Ps = [i for i in range(cons + 1) if is_prime[i]]

def factorize(N):  # 素因数分解
    PRIME = set()
    for p in Ps:
        if p * p > N:
            break
        while N % p == 0:
            N //= p
            PRIME.add(p)
    if N > 1:
        PRIME.add(N)
    return PRIME

pairwiseFlag = True

gcd = As[0]
for i in range(1, n):
  gcd = math.gcd(gcd, As[i])
setwiseFlag = (gcd == 1)

target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target = target | primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')


### FIXED CODE ###

import bisect
import math

n = int(input())
As = list(map(int, input().split()))
As.sort()

# cons = 10 ** 6
# is_prime = [True] * (cons + 1)
# is_prime[0] = False
# is_prime[1] = False
# for i in range(2, int(cons**0.5) + 1):
#     if not is_prime[i]:
#         continue
#     for j in range(i * 2, cons + 1, i):
#         is_prime[j] = False
# Ps = [i for i in range(cons + 1) if is_prime[i]]
def eratosthenes(n):
    is_prime = [0, 0] + [1] * (n - 1)
    for i in range(int(n**0.5) + 1):
        if is_prime[i] == 0:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = 0
    return [i for i, pi in enumerate(is_prime) if pi == 1]
Ps = eratosthenes(10 ** 6)

def factorize(n):
    primes = set()
    for p in Ps:
        if p * p > n:
            break
        while n % p == 0:
            n //= p
            primes.add(p)
    if n > 1:
        primes.add(n)
    return primes

gcd = As[0]
for a in As:
  gcd = math.gcd(gcd, a)
setwiseFlag = (gcd == 1)

pairwiseFlag = True
target = set()
for a in As:
  primes = factorize(a)
  if len(primes & target) > 0:
    pairwiseFlag = False
  target |= primes

if pairwiseFlag:
  print('pairwise coprime')
elif setwiseFlag:
  print('setwise coprime')
else:
  print('not coprime')
### BUGGY CODE ###

from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = []
dx = [1,-1,0,0]
dy = [0,0,1,-1]
for _ in range(h):
    maze.append(list(input()))
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
    x,y = dq.popleft()
    if x == d and y == c:
        break
    for i in range(4):
        nx,ny,K = x,y,k
        while K:
            nx += dx[i]
            ny += dy[i]
            if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "@" and depth[ny][nx] > depth[y][x]:
                    depth[ny][nx] = depth[y][x] +1
                    dq.append((nx,ny))
            else:
                break
            K -= 1
print(depth[c][d] if depth[c][d] != float("inf") else -1)

### FIXED CODE ###

from collections import deque
h,w,k = map(int,input().split())
a,b,c,d = map(int,input().split())
a -= 1
b -= 1
c -= 1
d -= 1
maze = [input() for _ in range(h)]
dx = [1,-1,0,0]
dy = [0,0,1,-1]
depth = [[float("inf") for _ in range(w)] for _ in range(h)]
dq = deque([(b,a)])
depth[a][b] = 0
while dq:
    x,y = dq.popleft()
    if x == d and y == c:
        break
    for i in range(4):
        nx,ny,K = x,y,k
        while K:
            K -= 1
            nx += dx[i]
            ny += dy[i]
            if 0<=nx<=w-1 and 0<=ny<=h-1 and maze[ny][nx] != "@" and depth[ny][nx] > depth[y][x]:
                if depth[ny][nx] == depth[y][x]+1:
                    continue
                depth[ny][nx] = depth[y][x] +1
                dq.append((nx,ny))
            else:
                break
print(depth[c][d] if depth[c][d] != float("inf") else -1)
### BUGGY CODE ###

def resolve():
    n,x,m = map(int,input().split())
    ans = x
    y = [x]
    for i in range(n-1):
        x = (x**2)%m
        if x not in y:
            y.append(x)
        else:
            break
    b = y.index(x)
    N = len(y[b:])
    c = sum(y[b:])
    ans = sum(y[:b]) + c*((n-b)//N)+sum(y[b:b+(n-b)%N])
    print(ans)
resolve()

### FIXED CODE ###

def resolve():
    n,x,m = map(int,input().split())
    ans = x
    y = [x]
    for i in range(n-1):
        x = (x**2)%m
        if x not in y:
            y.append(x)
        else:
            break
    b = y.index(x)
    N = len(y[b:])
    c = sum(y[b:])
    ans = sum(y[:b]) + c*((n-b)//N)+sum(y[b:b+(n-b)%N])
    print(ans)
resolve()
### BUGGY CODE ###

import sys
from collections import deque
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split()) 
DBG = True  and False
BIG = 1234567890

def ddprint(x):
  if DBG:
    print(x)

n,m,l = inm()

distance = [ [BIG] * n for i in range(n) ]
hops = [ [(BIG,0)] * n for i in range(n) ]
for i in range(n):
  distance[i][i] = 0
  hops[i][i] = (0,0)

dst = [ [] for i in range(n) ]
for i in range(m):
  a,b,c = inm()
  a -= 1
  b -= 1
  if c>l:
    continue
  distance[a][b] = distance[b][a] = c
  dst[a].append(b)
  dst[b].append(a)

for i in range(n):
  d = (0,0)
  q = deque([ (x,(0,distance[i][x])) for x in dst[i] ])
  while len(q)>0:
    y,e = q.popleft()
    #ddprint("y {} e {} {}".format(y,e[0],e[1]))
    if e>=hops[i][y]:
      continue
    #ddprint("upd i {} y {}".format(i,y))
    hops[i][y] = e
    for f in dst[y]:
      ds = distance[y][f]
      #ddprint("y {} f {} ds {}".format(y,f,ds))
      if e[1]+ds > l:
        newd = (e[0]+1, ds)
      else:
        newd = (e[0], e[1]+ds)
      if newd < hops[i][f]:
        q.append((f,newd))

if DBG:
  for i in range(n):
    print(hops[i])

for i in range(n):
  for j in range(n):
    if hops[i][j][0] > BIG/2:
      hops[i][j] = (-1,0)

p = inn()
for i in range(p):
  s,t = inm()
  #ddprint("q {} s {} t {}".format(i,s,t))
  print(hops[s-1][t-1][0])


### FIXED CODE ###

import sys
printn = lambda x: sys.stdout.write(x)
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
DBG = True # and False
BIG = 9999999999

def ddprint(x):
  if DBG:
    print(x)

def ws(dist):
    for k in range(n):
        for i in range(n):
            for j in range(n):
                dist[i][j] = min(dist[i][j],
                              dist[i][k]+dist[k][j])

n,m,l = inm()
dst = [ [] for i in range(n) ]
for i in range(m):
    a,b,c = inm()
    dst[a-1].append((b-1,c))
    dst[b-1].append((a-1,c))

dist1 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist1[i][i] = 0
    for j,c in dst[i]:
        dist1[i][j] = c

ws(dist1)

dist2 = [ [BIG]*n for i in range(n) ]
for i in range(n):
    dist2[i][i] = 0
    for j in range(n):
        if dist1[i][j] <= l:
            dist2[i][j] = 1

ws(dist2)

q = inn()
for i in range(q):
    s,t = inm()
    d = dist2[s-1][t-1]
    print(d-1 if d<BIG else -1)
### BUGGY CODE ###

def main():
	N = int(input())
	A = list(map(int,input().split()))
	B = list(map(int,input().split()))
	ans = 0
	p = 1
	for k in range(29):
		a_m = sorted([i & (2*p-1) for i in A], reverse=True)
		b_m = sorted([i & (2*p-1) for i in B])
		s = 0
		l1 = 0
		r1 = 0
		l2 = 0
		r2 = 0
		for a in a_m:
			while l1 < N and a + b_m[l1] < p:
				l1 += 1
			while r1 < N and a + b_m[r1] < 2*p:
				r1 += 1
			while l2 < N and a + b_m[l2] < 3*p:
				l2 += 1
			while r2 < N and a + b_m[r2] < 4*p:
				r2 += 1
			s += r2 - l2 + r1 - l1
		if s&1 == 1:
			ans += p
		p *= 2

	print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
	N = int(input())
	A = list(map(int,input().split()))
	B = list(map(int,input().split()))
	ans = 0
	p = 1
	for k in range(29):
		a_m = sorted([i & (2*p-1) for i in A], reverse=True)
		b_m = sorted([i & (2*p-1) for i in B])
		s = 0
		l1 = 0
		r1 = 0
		l2 = 0
		r2 = 0
		for a in a_m:
			while l1 < N and a + b_m[l1] < p:
				l1 += 1
			while r1 < N and a + b_m[r1] < 2*p:
				r1 += 1
			while l2 < N and a + b_m[l2] < 3*p:
				l2 += 1
			while r2 < N and a + b_m[r2] < 4*p:
				r2 += 1
			s += r2 - l2 + r1 - l1
		if s&1 == 1:
			ans += p
		p *= 2

	print(ans)


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

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

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

div.pop(0)
ans=[]
for val in div:
  cnt=0
  for i in range(len(ans)):
    if val%ans[i]==0:
      break
    else:
      cnt+=1
  if cnt==len(ans):
    ans.append(val)
print(len(ans)+1)

### FIXED CODE ###

def gcd(a,b): # 最大公約数を求める
  while b:
    a,b=b,a%b
  return abs(a)
  
def solve(A:int, B:int):
  a=gcd(A,B)
  ap=a
  ct=0
  x=2
  if a%x==0:
    ct+=1
    while a%x==0:
      a=a//x
  
  x=3
  while x*x<ap+1:
    if a%x==0:
      ct+=1
      while a%x==0:
        a=a//x
    x+=2
  
  if a!=1:
    ct+=1
  print(ct+1)
  
  return

def main():
  A,B=map(int,input().split())
  solve(A,B)

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

import heapq
N,M = (int(x) for x in input().split())
pref = [[] for _ in range(N)]
ans = [0] * M
prefnumber = 0
for i in range(M):
    P,Y = (int(x) for x in input().split())
    pref[P-1].append((Y,i))
for p in pref:
    prefnumber += 1
    count = 1
    while p:
        heapq.heapify(p)
        temp = heapq.heappop(p)
        ans[temp[1]] = ''.join([str(prefnumber).zfill(6),str(count).zfill(6)])
        count += 1
for a in ans:
    print(a)

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq
N,M = (int(x) for x in input().split())
pref = [[] for _ in range(N)]
ans = [0] * M
prefnumber = 0
for i in range(M):
    P,Y = (int(x) for x in input().split())
    pref[P-1].append((Y,i))
for p in pref:
    prefnumber += 1
    count = 1
    if p:
        heapq.heapify(p)
        while p:
            temp = heapq.heappop(p)
            ans[temp[1]] = ''.join([str(prefnumber).zfill(6),str(count).zfill(6)])
            count += 1
print('\n'.join(ans))
### BUGGY CODE ###

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

for i in range(n):
    print(A.count(i+1))


### FIXED CODE ###

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

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

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

#　ans = 2**n
n2 = n
ans = 1
rou = 0
while n2 >= 1:
    n2, rem = divmod(n2, 2)
    if rem == 1:
        ans *= 2**(2**rou)
    rou += 1

#　数え過ぎたものを引く
import math
def comb(n, r):
    return math.factorial(n) // (math.factorial(n-r) * math.factorial(r))

ans -= comb(n, a) + comb(n, b) + 1


print(int(ans % (1000000007)))

### FIXED CODE ###

#TLE

#comb_mod(n, r, mod) = nCr % mod
def comb_mod(n, r, mod):
    ans = 1
    if r <= n/2:
        for i in range(n-r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    else:
        for i in range(r+1, n+1):
            ans *= i
            ans %= mod
        for i in range(1, n-r+1):
            ans *= pow(i, mod-2, mod)
            ans %= mod
    return ans

n, a, b = map(int, input().split())
ans = pow(2, n, 10**9+7) - comb_mod(n, a, 10**9+7) - comb_mod(n, b, 10**9+7) - 1
if ans < 0:
    ans += 10**9 + 7
if ans < 0:
    ans += 10**9 + 7

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

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

cnt = 0
tmp = N
while tmp != 0:
  cnt += 1
  tmp //= 2

def binary_search(v, L):
  if max(L) <= v:
    return 0
  elif min(L) > v:
    return N
  else:
    l, r = 0, N
    d = (l + r) // 2
    for _ in range(cnt+2):
      if L[d] <= v:
        l = d + 1
        d = (l + r) // 2
      else:
        r = d
        d = (l + r) // 2
    return N - d

LB = [binary_search(B[_], C) for _ in range(N)]
for i in range(N-1, 0, -1):
  LB[i-1] += LB[i]
S = 0
for i in range(N):
  X = N - binary_search(A[i], B)
  if X != N:
    S += LB[X]
print(S)

### FIXED CODE ###

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

cnt = 0
tmp = N
while tmp != 0:
  cnt += 1
  tmp //= 2

def binary_search(v, L, M, m):
  if M <= v:
    return 0
  elif m > v:
    return N
  else:
    l, r = 0, N
    d = (l + r) // 2
    for _ in range(cnt):
      if L[d] <= v:
        l = d + 1
        d = (l + r) // 2
      else:
        r = d
        d = (l + r) // 2
    return N - d
MB, mB, MC, mC = B[N-1], B[0], C[N-1], C[0]
LB = [binary_search(B[_], C, MC, mC) for _ in range(N)]
for i in range(N-1, 0, -1):
  LB[i-1] += LB[i]
S = 0
for i in range(N):
  X = N - binary_search(A[i], B, MB, mB)
  if X != N:
    S += LB[X]
print(S)
### BUGGY CODE ###

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

h,w = map(int,readline().split())
a = []
for i in range(h):
  s = list(map(int,readline().split()))
  a.append(s)
b = []
for i in range(h):
  t = list(map(int,readline().split()))
  b.append(t)

dp = [[set() for _ in range(w)] for _ in range(h)]
dp[0][0].add(abs(a[0][0]-b[0][0]))

for i in range(h):
  for j in range(w):
    for k in dp[i][j]:
        if i < h-1:
          c = abs(a[i+1][j]-b[i+1][j])
          if k+c < 5000:
            dp[i+1][j].add(k+c)
          dp[i+1][j].add(abs(k-c))
        if j < w-1:
          d = abs(a[i][j+1]-b[i][j+1])
          if k+d < 5000:
            dp[i][j+1].add(k+d)
          dp[i][j+1].add(abs(k-d))

print(min(dp[h-1][w-1]))

### FIXED CODE ###

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines

  h,w = map(int,readline().split())
  a = []
  for i in range(h):
    s = list(map(int,readline().split()))
    a.append(s)
  b = []
  for i in range(h):
    t = list(map(int,readline().split()))
    b.append(t)
  C = [[0]*w for _ in range(h)]
  for i in range(h):
      for j in range(w):
          C[i][j] = abs(a[i][j] - b[i][j])

  dp = [[[0]*6321 for i in range(w)] for _ in range(h)]
  dp[0][0][C[0][0]] = 1

  for i in range(h):
    for j in range(w):
      for k in range(6321):
        if dp[i][j][k]:
          if i < h-1:
            c = C[i+1][j]
            if k+c < 6321:
              dp[i+1][j][k+c] = 1
            dp[i+1][j][abs(k-c)] = 1
          if j < w-1:
            d = C[i][j+1]
            if k+d < 6321:
              dp[i][j+1][k+d] = 1
            dp[i][j+1][abs(k-d)] = 1

  for i in range(6321):
    if dp[h-1][w-1][i]:
      print(i)
      break
      
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
s = list(str(input()))

R = []
G = []
B = []

for i in range(n):
    if s[i] == 'R':
        R.append(i)
    elif s[i] == 'G':
        G.append(i)
    elif s[i] == 'B':
        B.append(i)
c = 0
for r in R:
    for g in G:
        for b in B:
            [i,j,k] = sorted([r,g,b])
            if len(set([i,j,k])) == 3 and j-i != k-j:
                c = c+1
print(c)

### FIXED CODE ###

n = int(input())
s = list(str(input()))


c = 0
for i in range(n):
    for j in range(i+1, n):
        k = 2*j-i
        if k<n and s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            c = c+1
            
        

R = 0
G = 0
B = 0

for i in range(n):
    if s[i] == 'R':
        R = R+1
    elif s[i] == 'G':
        G = G+1
    elif s[i] == 'B':
        B = B+1

print(R*G*B-c)
### BUGGY CODE ###

N, K = list(map(int, input().split()))
h = list(map(int, input().split()))

L = [float("inf") for i in range(N)]
for i in range(min(N, K)):
    L[i] = abs(h[0] - h[i])


for i in range(K, N):
    X = []
    
    for j in range(K):
        x = L[i - j - 1] + abs(h[i] - h[i - j - 1])
        X.append(x)
    
    L[i] = min(X)

print(L[N - 1])

### FIXED CODE ###

import sys; input = sys.stdin.buffer.readline
import numpy as np
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = 2 ** 63 - 1

def getlist():
	return list(map(int, input().split()))

#処理内容
def main():
	N, K = getlist()
	h = np.array(getlist() + [0] * K, dtype = np.int64)
	
	DP = np.full(N + K, INF, dtype = np.int64)
	DP[0] = 0
	for i in range(N):
		DP[i + 1:i + K + 1] = np.minimum(DP[i + 1:i + K + 1],
			DP[i] + np.abs(h[i] - h[i + 1:i + K + 1]))

	print(DP[N - 1])

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

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

h,w = map(int,readline().split())
a = []
A = [list(map(int,readline().split())) for _ in range(h)]
B = [list(map(int,readline().split())) for _ in range(h)]
C = [[False]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        C[i][j] = abs(A[i][j] - B[i][j])

dp = [[set() for _ in range(w)] for _ in range(h)]
dp[0][0].add(C[0][0])

for i in range(h):
  for j in range(w):
    for k in dp[i][j]:
        if i < h-1:
          c = C[i+1][j]
          if k+c < 6321:
            dp[i+1][j].add(k+c)
          dp[i+1][j].add(abs(k-c))
        if j < w-1:
          d = C[i][j+1]
          if k+d < 6321:
            dp[i][j+1].add(k+d)
          dp[i][j+1].add(abs(k-d))

print(min(dp[h-1][w-1]))

### FIXED CODE ###

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines

  h,w = map(int,readline().split())
  a = []
  for i in range(h):
    s = list(map(int,readline().split()))
    a.append(s)
  b = []
  for i in range(h):
    t = list(map(int,readline().split()))
    b.append(t)
  C = [[0]*w for _ in range(h)]
  for i in range(h):
      for j in range(w):
          C[i][j] = abs(a[i][j] - b[i][j])

  dp = [[[0]*6321 for i in range(w)] for _ in range(h)]
  dp[0][0][C[0][0]] = 1

  for i in range(h):
    for j in range(w):
      for k in range(6321):
        if dp[i][j][k]:
          if i < h-1:
            c = C[i+1][j]
            if k+c < 6321:
              dp[i+1][j][k+c] = 1
            dp[i+1][j][abs(k-c)] = 1
          if j < w-1:
            d = C[i][j+1]
            if k+d < 6321:
              dp[i][j+1][k+d] = 1
            dp[i][j+1][abs(k-d)] = 1

  for i in range(6321):
    if dp[h-1][w-1][i]:
      print(i)
      break
      
if __name__ == "__main__":
    main()
### BUGGY CODE ###

def i__j(i, j, N):
    ans = 0
    for k in range(1, N+1):
        str_k = str(k)
        if str_k[0] == str(i) and str_k[-1] == str(j):
            ans += 1

    return ans

N = int(input())

c = [[0 for i in range(9)] for j in range(9)]
for i in range(9):
    for j in range(9):
        c[i][j] = i__j(i+1, j+1, N)

ans = 0
for i in range(9):
    for j in range(9):
        ans += c[i][j]*c[j][i]

print(ans)

### FIXED CODE ###

N = int(input())

c = [[0 for i in range(10)] for j in range(10)]
for i in range(N+1):
    str_i = str(i)
    c[int(str_i[0])][int(str_i[-1])] += 1

ans = 0
for i in range(1, 10):
    for j in range(1, 10):
        ans += c[i][j]*c[j][i]

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

n, k = map(int, input().split())
p = list(map(int,input().split()))
val = 0
atai = 0
for i in range(n-k+1):
    ans = 0
    for j in range(i,i+k):
        ans += p[j]
    if ans > val:
        val = ans
        atai = i

#print(atai)
ans = 0
for i in range(k):
    kitai = 0
    for j in range(1,p[atai]+1):
        kitai += j
    ans += kitai / p[atai]
    atai += 1
    #print(atai)
    #print(kitai)
print(ans)


### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int,input().split()))
val = 0
atai = 0
val2 = 0
for i in range(k):
    val2 += p[i]
#print(val2)
val = val2
for i in range(k,n):
    if val < val2:
        val = val2
        atai = i-k+1
    #print(i,p[i],p[i-k])
    val2 += p[i]
    if i==k:
        val2 == 0
    else:
        val2 -= p[i-k]
    #print(val2)
    if val < val2:
        val = val2

        atai = i-k+1
#print(atai)

#print(atai)
ans = 0
for i in range(k):
    ans += (p[atai]+1)/2
    atai += 1
    #print(atai)
    #print(kitai)
print(ans)