Harryxun/stf_run huggingface dataset:
class UnionFind:
    Parents = None

    def __init__(self, N):
        self.Parents = [-1 for i in range(N + 1)]

    # Aがどのグループにいるのか調べる
    def root(self, A):
        if self.Parents[A] < 0:
            return A
        else:
            self.Parents[A] = self.root(self.Parents[A])
            return self.Parents[A]

    # Aが所属しているグループのサイズを返す
    def size(self, A):
        return -self.Parents[self.root(A)]

    # AとBをくっつける
    def Connect(self, A, B):
        if self.root(A) == self.root(B):
            return False
        if self.size(A) < self.size(B):
            self.Parents[self.root(B)] += self.Parents[A]
            self.Parents[self.root(A)] = B
        else:
            self.Parents[self.root(A)] += self.Parents[self.root(B)]
            self.Parents[self.root(B)] = A
        return True


n, m = map(int, input().split())
a = [input().split() for i in range(m)]
a = [(int(i[0]), int(i[1])) for i in a]
ans = [int(n * (n - 1) / 2) for i in range(m)]
uni = UnionFind(n)

for i in range(m):
    if i == 0:
        continue
    A = a[-i][0]
    B = a[-i][1]

    if uni.root(A) != uni.root(B):
        ans[i] = ans[i-1] - uni.size(A) * uni.size(B)
        uni.Connect(A, B)
    else:
        ans[i] = ans[i-1]


for i in range(1, m+1):
    print(ans[-i])


### FIXED CODE ###

class UnionFind:
    Parents = None

    def __init__(self, N):
        self.Parents = [-1 for i in range(N + 1)]

    # Aがどのグループにいるのか調べる
    def root(self, A):
        if self.Parents[A] < 0:
            return A
        else:
            self.Parents[A] = self.root(self.Parents[A])
            return self.Parents[A]

    # Aが所属しているグループのサイズを返す
    def size(self, A):
        return -self.Parents[self.root(A)]

    # AとBをくっつける
    def Connect(self, A, B):
        if self.root(A) == self.root(B):
            return False
        if self.size(A) < self.size(B):
            self.Parents[self.root(B)] += self.Parents[self.root(A)]
            self.Parents[self.root(A)] = B
        else:
            self.Parents[self.root(A)] += self.Parents[self.root(B)]
            self.Parents[self.root(B)] = A
        return True


n, m = map(int, input().split())
a = [input().split() for i in range(m)]
a = [(int(i[0]), int(i[1])) for i in a]
ans = [int(n * (n - 1) / 2) for i in range(m)]
uni = UnionFind(n)

for i in range(m):
    if i == 0:
        continue
    A = a[-i][0]
    B = a[-i][1]

    if uni.root(A) != uni.root(B):
        ans[i] = ans[i-1] - uni.size(A) * uni.size(B)
        uni.Connect(A, B)
    else:
        ans[i] = ans[i-1]


for i in range(1, m+1):
    print(ans[-i])
a , av =  map(int, raw_input().split())
print 2*av - a

### FIXED CODE ###

a,av =  int(raw_input()), int(raw_input())
print 2*av - a
# -*- coding: utf-8 -*-

def my_sort(word):
    sorted_word_list = sorted(word)
    sorted_word = ""
    for letter in sorted_word_list:
        sorted_word += letter
    return sorted_word

def func(x):
    if x < 1:
        return x
    return x + func(x-1)

n = int(input())
words = {}
for i in range(n):
    word = my_sort(input())
    if word in words.keys():
        words[word] += 1
    else:
        words[word] = 0

for key in words.keys():
    words[key] = func(words[key])

print(sum(words.values()))

### FIXED CODE ###

# -*- coding: utf-8 -*-

def my_sort(word):
    sorted_word_list = sorted(word)
    sorted_word = ""
    for letter in sorted_word_list:
        sorted_word += letter
    return sorted_word

n = int(input())
words = {}
for i in range(n):
    word = my_sort(input())
    if word in words.keys():
        words[word] += 1
    else:
        words[word] = 1

for key in words.keys():
    words[key] = max(words[key]*(words[key]-1)//2, 0)

print(sum(words.values()))
def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]

m,k=MI()

if k>=2**m:
    print(-1)
    exit()

a=[]
for i in range(2**m):
    if i!=k: a.append(i)

print(k,*a,k,*a[::-1])
        
                


### FIXED CODE ###

def MI():
    return map(int,input().split())
def I():
    return int(input())
def LI():
    return [int(i) for i in input().split()]

m,k=MI()

if k>=2**m or (m,k)==(1,1):
    print(-1)
elif (m,k)==(1,0):
    print('0 0 1 1')
else:
    a=[]
    for i in range(2**m):
        if i!=k: a.append(i)
    ans=[k]+a+[k]+a[::-1]
    print(*ans)
N = int(input())
S = list(input())
K = int(input())

for i in range(N):
    if S[i] != S[K]:
        S[i] = "*"

print("".join(S))

### FIXED CODE ###

N = int(input())
S = list(input())
K = int(input())

for i in range(N):
    if S[i] != S[K-1]:
        S[i] = "*"

print("".join(S))
N,D = map(int,input().split())
a = 0
for num in N :
  X,Y = map(int,input().split())
  if X*X + Y*Y <= D*D :
    a = 1
print(a)

### FIXED CODE ###

N,D = map(int,input().split())
a = 0
for num in range(1,N+1) :
  X,Y = map(int,input().split())
  if X*X + Y*Y <= D*D :
    a += 1
print(a)
import numpy as np

n, k, q = map(int, input().split())
a = [int(input()) for i in range(q)]

players_score = np.array([k for i in range(n)])
for item in a:
    players_score -= 1
    players_score[item-1] += 1

indict = ['No' if i <= 0 else 'Yes' for i in players_score ]

for i in indict:
    print(i)


### FIXED CODE ###

import numpy as np

n, k, q = map(int, input().split())
a = np.array([int(input()) for i in range(q)])

players_score = np.full(n, k-q)

for item in a:
    players_score[item-1] += 1

for i in players_score:
    if i <= 0:
        print("No")
    else:
        print("Yes")
n,l=(int,input().split())
if(n>2*l):
    print(n-2*l)
else:
    print(0)

### FIXED CODE ###

n,p=map(int,input().split())
if(n>2*p):
    print(n-2*p)
else:
    print(0)
def solve():
  n = int(input())
  a = list(map(int, input().split()))
  g, z = 0, 0
  cut = 1
  for i in range(n-1):
    if a[i+1] > a[i]:
      g += 1
    elif a[i+1] < a[i]:
      z += 1
    if g != 0 and z != 0:
      ans += 1
      g, z = 0, 0
  print(ans)
  return 0
 
if __name__ == "__main__":
  solve()


### FIXED CODE ###

def solve():
  n = int(input())
  a = list(map(int, input().split()))
  g, z = 0, 0
  cut = 1
  for i in range(n-1):
    if a[i+1] > a[i]:
      g += 1
    elif a[i+1] < a[i]:
      z += 1
    if g != 0 and z != 0:
      cut += 1
      g, z = 0, 0
  print(cut)
  return 0
 
if __name__ == "__main__":
  solve()
import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n = ri()
ans = 0
for _ in range(n):
  a, b = rs()
  if b == 'JPY':
    ans += float(a)
  else:
    ans += float(a)*380000
pritn(ans)
  
    










### FIXED CODE ###

import sys
import math
import itertools
import collections
import heapq
import re
import numpy as np

rr = lambda: sys.stdin.readline().rstrip()
rs = lambda: sys.stdin.readline().split()
ri = lambda: int(sys.stdin.readline())
rm = lambda: map(int, sys.stdin.readline().split())
rl = lambda: list(map(int, sys.stdin.readline().split()))
inf = float('inf')
mod = 10**9 + 7

n = ri()
ans = 0
for _ in range(n):
  a, b = rs()
  if b == 'JPY':
    ans += float(a)
  else:
    ans += float(a)*380000
print(ans)
n,m = map(int,input().split())
A = list(map(int,input().split()))
B = [ [] for _ in range(n + 1) ]
for _ in range(m):
    s,e = map(int,input().split())
    B[s].append(e)
    B[e].append(s)
ans = 0
for i in range(1,n+1):
    if max(B[i]) < i:
        ans += 1
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
A = [0] + list(map(int,input().split()))
B = [ [] for _ in range(n + 1) ]
for _ in range(m):
    s,e = map(int,input().split())
    B[s].append(A[e])
    B[e].append(A[s])
ans = 0
for i in range(1,n+1):
    if len(B[i]) == 0:
        ans += 1
    elif max(B[i]) < A[i]:
        ans += 1
print(ans)
def main():
    n, m, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]

    a_sum = [0 for x in range(n)]
    b_sum = [0 for x in range(m)]

    a_sum[0] = a[0]
    b_sum[0] = b[0]

    max_counter = 0

    for i in range(1, n):
        a_sum[i] = a[i] + a_sum[i - 1]

    for i in range(1, n):
        b_sum[i] = b[i] + b_sum[i - 1]

    for i in range(n):
        for j in range(m):
            if k >= a_sum[i] + b_sum[j] and max_counter < i + j + 2:
                max_counter = i + j + 2
        
    print(max_counter)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, m, k = map(int, input().split())
    a = [int(x) for x in input().split()]
    b = [int(x) for x in input().split()]

    a_sum = [0]
    b_sum = [0] 

    max_counter = 0

    j = m

    for i in range(n):
        a_sum.append(a_sum[i] + a[i])

    for i in range(m):
        b_sum.append(b_sum[i] + b[i])

    for i in range(n + 1):
        if a_sum[i] > k:
            break

        while k < a_sum[i] + b_sum[j]:
            j -= 1
        
        max_counter = max(max_counter, i + j)

    print(max_counter)

if __name__ == '__main__':
    main()
k = int(input())
a = '7' * (k - 1)
if int(a) % k == 0:
    for i in range(1, 50):
        a = '7' * i
        if int(a) % k == 0:
            print(i)
            exit()
    print(k-1)
    exit()
print(-1)


### FIXED CODE ###

k = int(input())
if k % 2 == 0 or k % 5 == 0:
    print(-1)
    exit()
i = 0
ai = 0
while True:
    ai = (ai * 10 + 7) % k
    i += 1
    if ai == 0:
        break
print(i)
x, y = map(int, input().split())
mod = 10**9+7 
def check(x, y):
  if (2*y-x)/3 < 0 or (2*x -y)/3 < 0:
    return False
  if (x+y)%3 != 0:
    return False
  return True

def comb(n, r, mod):
    r = min(r, n-r)
    x, y  = 1, 1
    for i in range(1, r+1):
      y =  y* i % mod
      x =  x* (n+1-i) % mod
    return int(x * pow(y, mod-2, mod) % mod)
  
if check(x, y):
  print(comb((2*y-x)//3+(2*x -y)/3, (2*y-x)//3, mod))
else:
  print(0)

### FIXED CODE ###

x, y = map(int, input().split())
mod = 10**9+7 
def check(x, y):
  if (2*y-x)/3 < 0 or (2*x -y)/3 < 0:
    return False
  if (x+y)%3 != 0:
    return False
  return True

def comb(n, r, mod):
    r = min(r, n-r)
    x, y  = 1, 1
    for i in range(1, r+1):
      y =  y* i % mod
      x =  x* (n+1-i) % mod
    return x * pow(y, mod-2, mod) % mod
  
if check(x, y):
  print(comb((2*y-x)//3+(2*x -y)//3, (2*y-x)//3, mod))
else:
  print(0)
bb = [0] * len(aa)
bb[0] = aa[0]
bb[1] = aa[1]
for i in range(2,len(aa)):
    bb[i] = bb[i-2] + aa[i]

sum0 = bb[len(aa)-2]
sum1 = bb[len(aa)-1]
ret = sum1
if len(aa)%2 == 0:
    ret = max(ret, sum0)
if len(aa)%2:
    sum0 = bb[len(aa)-1]
    sum1 = bb[len(aa)-2]
    for i in range(len(aa)//2):
        ret = max(ret, sum0 - aa[2*i])

# 0 -> 1
for i in range(0,len(aa)//2):
    try:
#        print(i, bb[2*i] - bb[2*i+3] + sum1 + aa[2*i+3])
        ret = max(ret, bb[i] - bb[i+3] + sum1 + aa[i+3] )
    except:
        0
# 1 -> 0
for i in range(0,len(aa)//2):
    try:
#        print(i, bb[2*i+1] - bb[2*i+4] + sum0 + aa[2*i+4])
        ret = max(ret, bb[2*i+1] - bb[2*i+4] + sum0 + aa[2*i+4] )
    except:
        0
print(ret)

### FIXED CODE ###

input()
aa = list(map(int, input().split()))
state = {(0,False)}
skipmax = len(aa)%2 + 1
state_all = {(i, True) for i in range(skipmax+1)}.union({(j, False) for j in range(skipmax+1)})
dp_0 = {a:None for a in state_all }
dp_0[(0,False)] = 0
skipcount = 0

def getmax(a, b):
    if a is None:
        return b
    if b is None:
        return a
    return max(a,b)

for i,a in enumerate(aa):
    dp_1 = {}
    for s in state_all:
        if s[1] & (dp_0[(s[0], False)] is not None):
            dp_1[s] = dp_0[(s[0], False)] + a
            continue
        dp_1[s] = getmax(dp_0[(s[0], True)], dp_0.get((s[0]-1, False), None))
    dp_0 = dp_1.copy()
if len(aa)%2:
    print(getmax(dp_0[(2,True)], dp_0[(1,False)]))
else:
    print(getmax(dp_0[(1,True)], dp_0[(0,False)]))
a, b, c, d, e, f= (int(i) for i in input().split()) 

waterlist=[]
for i in range(int(f/100/a)+1):
  for j in range(int(f/100/b)+1):
    if 100*a*i+100*b*j <=f:
      waterlist+=[100*a*i+100*b*j]
waterlist=list(set(waterlist))
#print(x)

sugarlist=[]
for i in range(int(f/c)+1):
  for j in range(int(f/d)+1):
    if c*i+d*j <=f:
      sugarlist+=[c*i+d*j]
sugarlist=list(set(sugarlist))
#print(y)

density=0
ans1=101
ans=1
for i in range(len(waterlist)):
  for j in range(len(sugarlist)):
    if 0 < waterlist[i]+sugarlist[j] <= f and sugarlist[j]<=waterlist[i]/100*e:
      tmp=sugarlist[j]/(waterlist[i]+sugarlist[j])
      if density < tmp:
        density = tmp
        ans1=waterlist[i]+sugarlist[j]
        ans2=sugarlist[j]
        
print(ans1,ans2)

### FIXED CODE ###

a, b, c, d, e, f= (int(i) for i in input().split()) 

waterlist=[]
for i in range(0,f+100*a,100*a):
  for j in range(0,f+100*b,100*b):
    if i+j <=f:
      waterlist+=[i+j]
waterlist=list(set(waterlist))
#print(x)

sugarlist=[]
for i in range(int(f/c)+1):
  for j in range(int(f/d)+1):
    if c*i+d*j <=f:
      sugarlist+=[c*i+d*j]
sugarlist=list(set(sugarlist))
#print(y)

density=0

for i in range(len(waterlist)):
  for j in range(len(sugarlist)):
    if 0 < waterlist[i]+sugarlist[j] <= f and sugarlist[j]<=waterlist[i]/100*e:
      tmp=sugarlist[j]/(waterlist[i]+sugarlist[j])
      if density <= tmp:
        density = tmp
        ans1=waterlist[i]+sugarlist[j]
        ans2=sugarlist[j]
        
print(ans1,ans2)
N, Ma, Mb = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(N)]

N_max = 40
a_max = 10
b_max = 10
c_max = 100

inf = N_max * c_max + 1
dp = [[[inf for _ in range(N_max * b_max + 1)] for _ in range(N_max * a_max + 1)] for _ in range(N_max + 1)]
dp[0][0][0] = 0

# print(dp[N])

for i, (aa, bb, cc) in enumerate(e, 1):
    for a in range(a_max * i + 1):
        for b in range(b_max * i + 1):
            dp[i][a][b] = min(dp[i][a][b], dp[i - 1][a][b])
            dp[i][a + aa][b + bb] = min(dp[i][a + aa][b + bb], dp[i - 1][a][b] + cc)

# print(dp[N])

ans = inf
for a in range(N_max * a_max + 1):
    for b in range(N_max * b_max + 1):
        # a:b=Ma:Mb
        # b*Ma=a*Mb
        if b * Ma == a * Mb and a * b > 0:
            ans = min(ans, dp[N][a][b])

print(ans if ans < inf else -1)


### FIXED CODE ###

N, Ma, Mb = map(int, input().split())
e = [tuple(map(int, input().split())) for _ in range(N)]

N_max = 40
a_max = 10
b_max = 10
c_max = 100

inf = N_max * c_max + 1
dp = [[[inf for _ in range(N_max * b_max + 1)] for _ in range(N_max * a_max + 1)] for _ in range(N_max + 1)]
dp[0][0][0] = 0

# print(dp[N])

for i, (aa, bb, cc) in enumerate(e, 1):
    for a in range(a_max * i + 1):
        for b in range(b_max * i + 1):
            dp[i][a][b] = min(dp[i][a][b], dp[i - 1][a][b])
            if a + aa < N_max * a_max + 1 and b + bb < N_max * b_max + 1:
                dp[i][a + aa][b + bb] = min(dp[i][a + aa][b + bb], dp[i - 1][a][b] + cc)

# print(dp[N])

ans = inf
for a in range(N_max * a_max + 1):
    for b in range(N_max * b_max + 1):
        # a:b=Ma:Mb
        # b*Ma=a*Mb
        if b * Ma == a * Mb and a * b > 0:
            ans = min(ans, dp[N][a][b])

print(ans if ans < inf else -1)
n = int(input())
a = list(map(int, input().split()))
if n == 1:
    print(1)
    exit()

a.sort()
li = []
count = 1
for i in range(n-1):
    if a[i] == a[i+1]:
        count += 1
    else:
        li.append(count)
        count = 1

li.sort()
count2 = 0

if len(li) == 1:
    print(li[0])
    exit()
elif len(li) == 2:
    if abs(a[0] - a[-1]) <= 2:
        print(li[0] + li[1])
    else:
        print(max(li[0], li[1]))
else:

    for i in range(len(li)-2):
        x = li[i] + li[i+1] + li[i+2]
        if x >= count2:
            count2 = x

    print(x)



### FIXED CODE ###

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

t = max(a)
num_list = [0] * (t + 2)

for i in range(n):
    num_list[a[i]] += 1
    if a[i] == 0:
        continue
    else:
        num_list[a[i]-1] += 1
    if a[i] == t:
        continue
    else:
        num_list[a[i]+1] += 1

print(max(num_list))
A = [list(map(int, input().split())) for _ in range(3)]
N = int(input())
B = [int(input()) for _ in range(N)]

l = [[(a_i in B) for a_i in a] for a in A]

# print(l)

flag = 0
for y in range(3):
    flag |= all(l[y])

for x in range(3):
    flag |= all([l[x][y] for y in range(3)])

flag |= all([l[y][x] for x, y in [(0, 0), (1, 1), (2, 2)]])

flag |= all([l[y][x] for x, y in [(0, 2), (1, 1), (2, 0)]])

print("Yes" if flag else "No")

### FIXED CODE ###

N = int(input())

print(-(-N//2))
#sを最高のパターンにして，tを最悪のパターンにすればいい
#continueで強制的に次のループへ
s = list(input())
t = list(input())
condition = 0

s.sort()
t.sort()
t.reverse()

if len(s)  == len(t):
    pattern == -1
elif len(s) < len(t):
    length = len(s)
    pattern = 0
else:#sのほうが長い時 pattern = 1
    length = len(t)
    pattern = 1

if pattern == -1:
    for i in range(length):
        if s[i] == t[i]:
            continue
        elif s[i] > t[i]:
            print("Yes")
            condition =1
            break
        else:
            print("No")
            condition =1
            break
    if condition == 0:
        print("No")
elif pattern == 0:
    for i in range(length):
        if s[i] == t[i]:
            continue
        elif s[i] < t[i]:
            print("Yes")
            condition =1
            break
        else:
            print("No")
            condition =1
            break
    
    if condition == 0:
        print("Yes")
elif pattern == 1:
    for i in range(length):
        if s[i] == t[i]:
            continue
        elif s[i] < t[i]:
            print("Yes")
            ccondition =1
            break
        else:
            print("No")
            condition =1
            break
    if condition == 0:
        print("No")
        
    



### FIXED CODE ###

#sを最高のパターンにして，tを最悪のパターンにすればいい
#continueで強制的に次のループへ
s = list(input())
t = list(input())
condition = 0

s.sort()
t.sort()
t.reverse()

if len(s)  == len(t):
    length = len(s)
    pattern = -1
elif len(s) < len(t):
    length = len(s)
    pattern = 0
else:#sのほうが長い時 pattern = 1
    length = len(t)
    pattern = 1

if pattern == -1:
    for i in range(length):
        if s[i] == t[i]:
            continue
        elif s[i] < t[i]:
            print("Yes")
            condition =1
            break
        else:
            print("No")
            condition =1
            break
    if condition == 0:
        print("No")
elif pattern == 0:
    for i in range(length):
        if s[i] == t[i]:
            continue
        elif s[i] < t[i]:
            print("Yes")
            condition =1
            break
        else:
            print("No")
            condition =1
            break
    
    if condition == 0:
        print("Yes")
elif pattern == 1:
    for i in range(length):
        if s[i] == t[i]:
            continue
        elif s[i] < t[i]:
            print("Yes")
            condition =1
            break
        else:
            print("No")
            condition =1
            break
            
    if condition == 0:
        print("No")
import argparse

parser = argparse.ArgumentParser()
parser.add_argument('integers', metavar='N', type=int, nargs='+',
               help='an integer for the accumulator')

args = parser.parse_args()
int_list = args.integers

if int_list[0] == int_list[1]: 
    print(-1)
elif int_list[0] < 0 or int_list[1] < 0: 
    print (-1)
else:
    for i in range(1, int(10 ** 10 / int_list[0])):
        if int_list[0] * i % int_list[1] != 0:
            print(int_list[0] * i)
            exit()
        else:
            continue
    print(-1)



### FIXED CODE ###

a, b = (int(i) for i in input().split())  

if a == b: 
    print(-1)
elif a < 0 or b < 0: 
    print (-1)
else:
    for i in range(1, int(10 ** 10 / a)):
        if a * i % b != 0:
            print(a * i)
            exit()
        else:
            continue
    print(-1)
a,b = map(int,input().split())

print('Even' if a*b % == 0 else 'Odd')

### FIXED CODE ###

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

print('Even' if a*b %2 == 0 else 'Odd')
S = input()
N = len(S)
A = [int(S[i]) for i in range(N)]
dp = [0] * 2019
cnt = [0] * 2019
cnt[0] = 1
p = 1

for i in reversed(range(N)):
    dp[i] = (dp[i+1] + A[i]*p) % 2019
    cnt[dp[i]] += 1
    p = 10 * p % 2019 

ans = 0
for i in cnt:
    ans += i*(i-1)//2

print(ans)

### FIXED CODE ###

S = input()
N = len(S)
A = [int(S[i]) for i in range(N)]
cnt = [0] * 2019
cnt[0] = 1
p = 1
dp = 0

for i in reversed(range(N)):
    dp = (dp + A[i]*p) % 2019
    cnt[dp] += 1
    p = 10 * p % 2019
ans = 0

for i in cnt:
    ans += i*(i-1)//2

print(ans)
# A

n = int(input())
a_l = [int(float(input()) * 10**9) for x in range(n)]

list = [[0] * 18 for x in range(18)]
b_l = [0, 0] * n

for i in range(n):
    _t2 = 0
    _t5 = 0
    _a = a_l[i]
    while _a % 2 == 0 and _t2 < 18:
        _t2 += 1
        _a /= 2

    _a = a_l[i]
    while _a % 5 == 0 and _t5 < 18:
        _t5 += 1
        _a /= 5
    
    list[_t2][_t5] += 1
    b_l[i] = [_t2, _t5]
    
ans = 0
for i in range(n):
    _t,_f = b_l[i]
    for j in range(18-_t,19):
        for k in range(18-_f,19):
            ans += list[j][k]
    if _t >= 9 and _f >= 9:
        ans -= 1
        
print(ans // 2)


### FIXED CODE ###

# A

from decimal import *

n = int(input())
a_l = [int(Decimal(input()) * 10**9) for x in range(n)]

list = [[0] * 19 for _ in range(19)]
cs_list = [[0] * 19 for _ in range(19)]
b_l = [0, 0] * n

for i in range(n):
    _t2 = 0
    _t5 = 0
    _a = a_l[i]
    while _a % 2 == 0 and _t2 < 18:
        _t2 += 1
        _a /= 2

    _a = a_l[i]
    while _a % 5 == 0 and _t5 < 18:
        _t5 += 1
        _a /= 5
    
    list[_t2][_t5] += 1
    b_l[i] = [_t2, _t5]

for i in range(19):
    for j in range(19):
        for k in range(i+1):
            for l in range(j+1):
                cs_list[k][l] += list[i][j]

ans = 0
for i in range(n):
    _t,_f = b_l[i]
    if _t >= 9 and _f >= 9:
        ans -= 1
    ans += cs_list[18-_t][18-_f]
        
print(ans // 2)
N = input()
S = input()
count = 0
for i in range(1, int(N)-1):
  if s[i-1] + s[i] + s[i+1] == "ABC":
    count += 1
print(count)

### FIXED CODE ###

n = int(input())
s = str(input())
print(s.count("ABC"))
from math import floor
 
a,b = list(map(float,input().split()))
print(floor(a*b))

### FIXED CODE ###

import sys

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

if 0 in l:
	print(0)
	sys.exit()

flg=False
a = 1
for i in l:
	a *= i
	if a>10e17:
		flg=True
		break
 
if flg:
	print(-1)
else:
	print(a)
n = int(input())
array = [sorted(input()) for x in range(n)]
set_array = set()
for i in array:
  set_array.add(i)
print(len(array) - len(set_array))


### FIXED CODE ###

from collections import Counter

n = int(input())
array = sorted(["".join(sorted(input())) for x in range(n)])
counter = Counter(array)

res = 0
for key, value in counter.items():
    res += value*(value-1)//2
print(res)
count = int(input())
line = input().split()
n = line[0]
m = line[1]
lis = []
for i in range(2):
    lis.append(n[i])
    lis.append(m[i])

for j in lis:
    print(j,end = "")

### FIXED CODE ###

# coding: utf-8
# Your code here!
count = int(input())
line = input().split()
n = line[0]
m = line[1]
lis = []
for i in range(len(n)):
    lis.append(n[i])
    lis.append(m[i])

for j in lis:
    print(j,end = "")
import sys
from itertools import accumulate


def solve():
    N, K = map(int, sys.stdin.readline().split())
    cusum_p = list(accumulate(map(int, sys.stdin.read().split()), initial=0))
    return (max(i - j for i, j in zip(cusum_p[K:], cusum_p[:-K])) + K) / 2


if __name__ == "__main__":
    answer = solve()
    print(answer)


### FIXED CODE ###

import sys
from itertools import accumulate


def solve():
    N, K = map(int, sys.stdin.readline().split())
    cusum_p = (0,) + tuple(accumulate(map(int, sys.stdin.read().split())))
    return (max(i - j for i, j in zip(cusum_p[K:], cusum_p[:-K])) + K) / 2


if __name__ == "__main__":
    answer = solve()
    print(answer)
N=list(map(int,input().split()))
S=list(input())
k=N[1]
S[k]=S[k].lower()
print(S)

### FIXED CODE ###

N=list(map(int,input().split()))
S=list(input())
k=N[1]
S[k-1]=S[k-1].lower()
j = ' '
 
for x in S:
    j += x
print(j)