Harryxun/stf_run huggingface dataset:
import random
N, K = map(int, input().split())
A = [int(x) for x in input().split()]


def solve(N, K, A):
    A.sort()
    res = 0
    MOD = 10**9+7

    def fact(n, k=1):
        ans = 1
        for i in range(n):
            ans *= i
        return ans

    def comb(n, k):
        return (fact(n)//(fact(n-k)*fact(k))) % MOD

    s = [1, -1]
    for m in range(2):
        for i in range(K-1, N):
            res = (res + s[m]*int((A[i])*comb(i, K-1))) % MOD
        A = sorted(A, reverse=True)
    return res


print(solve(N, K, A))

### FIXED CODE ###

N, K = map(int, input().split())
A = [int(x) for x in input().split()]


def solve(N, K, A):
    A.sort()
    res = 0
    MOD = 10**9 + 7
    fact_table = [1] * (N + 1)
    inv_fact_table = [1] * (N + 1)
    for i in range(1, N + 1):
        fact_table[i] = fact_table[i - 1] * i % MOD

    def inverse(n):
        if n == 1:
            return 1
        q = MOD // n
        r = MOD % n
        return (MOD - q * inverse(r) % MOD) % MOD

    inv_fact_table[N] = inverse(fact_table[N])
    for i in range(N - 1, 0, -1):
        inv_fact_table[i] = inv_fact_table[i + 1] * (i + 1) % MOD

    def comb(n, k):
        return fact_table[n] * inv_fact_table[n - k] % MOD * inv_fact_table[k] % MOD

    s = [1, -1]
    for m in range(2):
        for i in range(K - 1, N):
            res = (res + s[m] * A[i] * comb(i, K - 1)) % MOD
        A = sorted(A, reverse=True)
    return (res + MOD) % MOD


print(solve(N, K, A))
n = int(input())
lst = [list(map(int, input().split())) for _ in range(n)]

ans = 'Yes'

for line in lst:
    t, x, y = line
    c1 = t < x + y
    c2 = t % 2 == 0 and (x + y) % 2 != 0:
    c3 = t % 2 != 0 and (x + y) % 2 == 0:
    
    if c1 or c2 or c3:
        ans = 'No'
        break

print(ans)

### FIXED CODE ###

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

ans = 'Yes'

for line in lst:
    t, x, y = line
    c1 = t < x + y
    c2 = t % 2 == 0 and (x + y) % 2 != 0
    c3 = t % 2 != 0 and (x + y) % 2 == 0
    
    if c1 or c2 or c3:
        ans = 'No'
        break

print(ans)
x,n = list(map(int,input().split()))
if n == 0:
  print(x)
  exit()

p = list(map(int,input().split()))

import bisect
p.sort()
i = bisect.bisect_left(p,x)

for h in range(1, p[-1]-p[0]+2):
  if p[i-h] != x-h:
    print(x-h)
    exit()
  elif p[i+h] != x+h:
    print(x+h)
    exit()    


### FIXED CODE ###

x,n = list(map(int,input().split()))
if n == 0:
  print(x)
  exit()

p = list(map(int,input().split()))
p = [-1] + p + [102]
import bisect
p.sort()
i = bisect.bisect_left(p,x)
if p[i] != x:
    print(x)
    exit()

for h in range(102):
  if p[i-h] != x-h:
    print(x-h)
    exit()
  elif p[i+h] != x+h:
    print(x+h)
    exit()
for _ in range(int(input())):
    n = int(input())
    d = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
    a = ''
    while n:
        n -= 1
        a = d[n % 26] + a
        n //= 26
    print(a)

### FIXED CODE ###

n = int(input())
d = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']
a = ''
while n:
  n -= 1
  a = d[n % 26] + a
  n //= 26
print(a)
i = list(map(int, input().split()))
A = i[0]
B = i[1]

count = 0
for i in range (A,B+1,1):
    I = str(i)
    if int(I[-1]) == int(I[-5]) and int(I[-2]) == int(I[-4]):
        count = count + 1
    else :
        pass

print(count)

### FIXED CODE ###

s  = input()
t  = input()
u = input()

slice1 = s[0:1]
slice2 = t[1:2]
slice3 = u[2:3]

ans = slice1 + slice2 + slice3

print(ans)
import math
array1 = [int(input()) for i in range(6)]
array2 = array1[1:6]
num = array1[0]
minimum = min(array2)
print(math.ceil(num / minimum + 4)

### FIXED CODE ###

import math
array1 = [int(input()) for i in range(6)]
array2 = array1[1:6]
num = array1[0]
minimum = min(array2)
print(math.ceil(num / minimum) + 4)
import math


def main():
    N = int(input())
    A = [int(arg) for arg in input().split()]
    ans = 1
    for i in range(N+1):
        ans *= A[i]
        if ans > pow(10, 18) and i == N:
            ans = "-1"
            break

    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    N = int(input())
    A = [int(arg) for arg in input().split()]
    ans = 1

    for i in range(N):
        if A[i] == 0:
            print(0)
            return

    for i in range(N):
        ans *= A[i]
        if ans > 10**18:
            print(-1)
            return

    print(ans)


if __name__ == '__main__':
    main()
N = int(input())
A = list(map(int,input().split()))
summary = sum(A)
d = {}
for a in A:
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
    
Q = int(input())
for _ in range(Q):
  B, C = list(map(int,input().split()))
  if b in d:
    b = 0
  else:
    b = d[B]
  	d[B] = 0
  if C in d:
    d[C] += b
  else:
    d[C] = b
  summary = summary + b * (C - B)
  print(summary)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
summary = sum(A)
d = {}
for a in A:
  if a in d:
    d[a] += 1
  else:
    d[a] = 1
    
Q = int(input())
for _ in range(Q):
  B, C = list(map(int,input().split()))
  if B not in d:
    b = 0
  else:
    b = d[B]
    d[B] = 0
  if C in d:
    d[C] += b
  else:
    d[C] = b
  summary = summary + b * (C - B)
  print(summary)
if A+B>C+D:
  print('Left')
elif A+B==C+D:
  print('Balanced')
elif A+B<C+D:
  print('Right')

### FIXED CODE ###

A,B,C,D = map(int, input().split())
if A+B>C+D:
  print('Left')
elif A+B==C+D:
  print('Balanced')
elif A+B<C+D:
  print('Right')
N,A,B=map(int,input().split())
i=N//(A+B)*A
if N%(A+B)>A:
    i=i+A
else:
    i=i+(N%(A+B))
print(i)

### FIXED CODE ###

S=input()
if (S[0]==S[1]==S[2]):
    print('No')
else:
    print('Yes')
from math import gcd
A, B = map(int, input().split())

def lcm(x, y):
    return x // gcd(x, y) * y

print(lcm(A, B))

### FIXED CODE ###

from fractions import gcd

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

print(A * B // gcd(A, B))
x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

d = []
for i in range(x):
    for j in range(y):
        d.append(a[i] + b[j])
d.sort(reverse=True)

e = []
for i in range(k):
    for j in range(z):
        e.append(d[i] + c[j])
e.sort(reverse=True)

for i in range(k):
    print(e[i])


### FIXED CODE ###

x, y, z, k = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

d = []
for i in range(x):
    for j in range(y):
        d.append(a[i] + b[j])
d.sort(reverse=True)

e = []
for i in range(min(len(d), k)):
    for j in range(z):
        e.append(d[i] + c[j])
e.sort(reverse=True)

for i in range(k):
    print(e[i])
A=input()
B=input()
a=int(A)
b=int(B)
x=a*b
print(x)


### FIXED CODE ###

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

x=a*b
print(x)
import pandas as pd
import sys

n = int(input())

jobs = pd.DataFrame(columns=["cost", "deadline"])

for i in range(n):
    a, b = map(int, input().split(' '))
    jobs.loc[len(jobs)] = [a, b]

jobs = jobs.sort_values("deadline")

sum = 0
for i in range(n):
    sum += jobs.iat[i, 0]
    if sum > jobs.iat[i, 1]:
        print('No')
        sys.exit()

print('Yes')

### FIXED CODE ###

import numpy as np
import sys

n = int(input())

# jobs = pd.DataFrame(columns=["cost", "deadline"])

a = []
b = []

for i in range(n):
    aa, bb = map(int, input().split(' '))
    a.append(aa)
    b.append(bb)

a = np.array(a)
b = np.array(b)

sortIndex = np.argsort(b)

a = a[sortIndex]
b = b[sortIndex]

sum = 0
for i in range(n):
    sum += a[i]
    if sum > b[i]:
        print('No')
        sys.exit()

print('Yes')
s = input()
t= input()
# s = "abracadabra"
# t = "avadakedavra"

dp=[[0]*len(t) for i in range(len(s))]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])
            
i, j, dp_len = len(s),len(t), dp[-1][-1]
ans = ""

while dp_len:
#     print("現在精査している文字は{}と{}です。もとのsは{}で、tは{}です。sの長さは{}, tの長さは{}です".format(s[i-1],t[j-1],s[:i-1], t[:j-1], i,j))
    if s[i-1] == t[j-1]:
        ans += s[i-1]
        i -= 1
        j -= 1
        dp_len -= 1
#         print("一致")
    elif dp[i][j] == dp[i-1][j]:
        i -= 1
    else:
        j -= 1
        
# print(dp)
print(ans[::-1])

### FIXED CODE ###

S = input()
T = input()
 
# dp[i][j] := Sのi文字目, Tのj文字目まで見た場合のLCS
dp = [[0] * (len(T) + 1) for i in range(len(S) + 1)]
 
for i in range(1, len(S) + 1):
    for j in range(1, len(T) + 1):
        if S[i - 1] == T[j - 1]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
 
ans = ''
i, j = len(S), len(T)
while i > 0 and j > 0:
    if S[i - 1] == T[j - 1]:
        ans += S[i - 1]
        i, j = i - 1, j - 1
    elif dp[i][j - 1] > dp[i - 1][j]:
        j -= 1
    else:
        i -= 1
 
print(ans[::-1])
n, k = map(int, input().split())
a = sorted(map(int, input().split()))
f = sorted(map(int, input().split()))
time = [f[i] * a[-i-1] for i in range(n)]

sup = max([time[i] - f[i] * k // n for i in range(n)] + [0])
inf = 0
while sup > inf:
  x = (sup + inf) // 2
  train = sum([(max([0, time[i] - x]) + f[i] - 1) // f[i] for i in range(n)])
  if k < train:
    inf = x + 1
  else:
    sup = x
print(sup)


### FIXED CODE ###

a, b = map(int, input().split())
if a < 10 and b < 10:
  print(a * b)
else:
  print(-1)
W,H,x,y,r = int(input())
if r <= x <= W - r and r <= y <= H - r:
print "Yes"
else:
print "No"

### FIXED CODE ###

W,H,x,y,r = map(int, input().split())
if r <= x <= W-r and r <= y <= H-r:
    print ('Yes')
else:
    print ('No')
S = input()
b = list(S)
a = b[0::2]
c = b[1::2]
d = len(b)
e = len(c)
cnt = 0
f = a.count('R' or 'U' or 'D')
g = c.count('L' or 'U' or 'D')
if f == d and e == g:
    print(Yes)
else:
    print(No)

### FIXED CODE ###

S = input()
b = list(S)
a = b[0::2]
c = b[1::2]
d = len(a)
e = len(c)
cnt = 0
f = a.count('R')
g = a.count('U')
h = a.count('D')
i = f + g + h



j = c.count('L')
k = c.count('U')
l = c.count('D')
m = j + k + l



if i == d and m == e:
    print('Yes')
else:
    print('No')
# -*- coding:utf-8 -*-
import sys
N=int(input())
List_1=[map(int,input()split())]
List_2=[map(int,input()split())]

answer=[]
for i in range(N):
  score+=sum(List_1[:i])
  score+=sum(List_2[i:])
  answer.append(score)
  score=0

print(max(answer))

### FIXED CODE ###

# -*- coding:utf-8 -*-
import sys
N=int(input())
List_1=list(map(int,input().split()))
List_2=list(map(int,input().split()))

answer=[]
score=0
for i in range(N):
  score+=sum(List_1[:i+1])
  score+=sum(List_2[i:])
  answer.append(score)
  score=0

print(max(answer))
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(m):
    u,v=map(int,input().split())
    branch[u-1]|={v-1}
s,t=map(int,input().split())
s-=1
t-=1
dist=[[float('inf')]*3 for i in range(n)]
check={(s,0)}
dist[s][0]=0
while len(check)>0:
    now,nowd=check.pop()
    for nex in branch[now]:
        if dist[nex][(nowd+1)%3]>dist[now][nowd]+1:
            ans[nex][(nowd+1)%3]=ans[now][nowd]+1
            check|={(nex,(nowd+1)%3)}
if dist[t][0]>10**18:
    print(-1)
else:
    print(dist[t][0]//3)

### FIXED CODE ###

import sys
input=sys.stdin.readline
n,m=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(m):
    u,v=map(int,input().split())
    branch[u-1]|={v-1}
s,t=map(int,input().split())
s-=1
t-=1
dist=[[float('inf')]*3 for i in range(n)]
check={(s,0)}
dist[s][0]=0
while len(check)>0:
    now,nowd=check.pop()
    for nex in branch[now]:
        if dist[nex][(nowd+1)%3]>dist[now][nowd]+1:
            dist[nex][(nowd+1)%3]=dist[now][nowd]+1
            check|={(nex,(nowd+1)%3)}
if dist[t][0]>10**18:
    print(-1)
else:
    print(dist[t][0]//3)
a = input()
	if a%2 == 0:
  		print("0.5")
      else
      print(1-a/2)
 
    

### FIXED CODE ###

N = int(input())
 
ans = 0
for i in range(1, N+1):
    if i % 2 == 1:
        ans += 1
print(ans/N)
def com():
????x = raw_input()
????a = len(x)
  y = raw_input()
????b = len(y)

????k1 = [0 for i in range(b+1)]
????
????for i in range(a):
????????k2 = k1 + [ ]
????????for j in range(b):
????????????if k1[j+1] < k1[j]:
????????????????k1[j+1] = k1[j]
????    elif x[i] == y[j]:
?????????????? k1[j+1] = k2[j] + 1
  
  return k1[-1]

n = input()
for l in range(n):
????print com()

### FIXED CODE ###

def common():
  X = raw_input()
  Y = raw_input()
  a = len(X)
  b = len(Y)
  k1 = [0 for i in range(b+1)]
 
  for i in range(a):
     k2 = k1 + []
     for j in range(b):
       if X[i] == Y[j]:
          k1[j+1] = k2[j] + 1
       elif k1[j+1] < k1[j]:
          k1[j+1] = k1[j]
 
  return k1[-1]
 
n = input()
for l in range(n):
  print common()
alphabet = "abcdefghijklmnopqrstuvwxyz"
dictionary = {}
for character in alphabet:
    dictionary[character] = 0

for character in raw_input():
    if character.lower() in dictionary:
        dictionary[character.lower()] += 1

for character in alphabet:
    print(character + ' ' + dictionary[character])

### FIXED CODE ###

import sys
alphabet = "abcdefghijklmnopqrstuvwxyz"
dictionary = {}
for character in alphabet:
    dictionary[character] = 0

for line in sys.stdin:
    for character in line.strip():
        if character.lower() in dictionary:
            dictionary[character.lower()] += 1

for character in alphabet:
    print(character + ' : ' + str(dictionary[character]))
# ABC 079 D


class WarshallFloyd:

    def __init__(self, adj):
        """
        ワーシャル・フロイド法によって全頂点間の最短距離を O(|V|^3) で計算する。

        :param adj: 隣接行列 adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        """
        self._dist = adj  # 各頂点間の最短距離 初期値として隣接行列をそのまま用い、[i, i]要素を0に初期化する
        for i in range(len(adj)):
            self._dist[i][i] = 0

        self._solve()

    def _solve(self):
        v_len = len(self._adj)
        for i in range(v_len):  # 経由する頂点
            for j in range(v_len):  # 開始頂点
                for k in range(v_len):  # 終端
                    self._dist[j][k] = min(self._dist[j][k], self._dist[j][i] + self._dist[i][k])

    def distance(self, start, goal):
        return self._dist[start][goal]

    def path(self, start, goal):
        pass


H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]

wf = WarshallFloyd(C)

cost = 0
for ln in A:
    for a in ln:
        if a == -1:
            continue
        cost += wf.distance(a, 1)
print(cost)


### FIXED CODE ###

class WarshallFloyd(object):

    def __init__(self, adj):
        """
        ワーシャル・フロイド法によって全頂点間の最短距離を O(|V|^3) で計算する。

        :param adj: 隣接行列 adj[i][j] でi番目の頂点からj番目の頂点へのコストを示す パスがなければINF
        """
        self._dist = adj  # 各頂点間の最短距離 初期値として隣接行列をそのまま用い、[i, i]要素を0に初期化する
        for i in range(len(adj)):
            self._dist[i][i] = 0

        self._solve()

    def _solve(self):
        v_len = len(self._dist)
        for i in range(v_len):  # 経由する頂点
            for j in range(v_len):  # 開始頂点
                for k in range(v_len):  # 終端
                    self._dist[j][k] = min(self._dist[j][k], self._dist[j][i] + self._dist[i][k])

    def distance(self, start, goal):
        return self._dist[start][goal]

    def path(self, start, goal):
        pass


H, W = map(int, input().split())
C = [list(map(int, input().split())) for _ in range(10)]
A = [list(map(int, input().split())) for _ in range(H)]

wf = WarshallFloyd(C)

ans = 0
for row in A:
    for cell in row:
        if cell == -1:
            continue
        ans += wf.distance(cell, 1)
print(ans)
a1 = a * c
a2 = a * d
a3 = b * c
a4 = b * d

list = [a1,a2,a3,a4]
print(max(list))

### FIXED CODE ###

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

a1 = A * C
a2 = A * D
a3 = B * C
a4 = B * D

list = (a1,a2,a3,a4)

print(max(list))
n=input()
for i in range(2)
if n[i]=1:
  n[i]=9
else:
  n[i]=1
print(n)

### FIXED CODE ###

for i in input():
    print(9 if i == '1' else 1, end='')
s,t = input().split()
a=0
for i in range(len(s)):
  if s[i]==t[i]:
      a=a+1
  else:
      a=a+0
print(a)

### FIXED CODE ###

s,t = input(), input()
a = 0
for i in range(len(s)):
    if s[i]!=t[i]:
        a = a + 1
print(a)
b = input()
if b ='A':
  print('T')
elif b = 'T':
  print('A')
elif b = 'C':
  print('G')
else:
  print('C')

### FIXED CODE ###

b = input()
if b =='A':
  print('T')
elif b == 'T':
  print('A')
elif b == 'C':
  print('G')
else:
  print('C')
n = int(input())

if n == 1:
  print('Hello World')
else:
  a = int(input()
  b = int(input()
  print(a+b)

### FIXED CODE ###

n = int(input())

if n == 1:
  print('Hello World')
else:
  a = int(input())
  b = int(input())
  print(a+b)
N, M = int(input().split())
A = list(map(int, input().split()))
S = sum(A)
ans = -1
if N >= S:
  ans = N-S
print (ans)

### FIXED CODE ###

N, M = list(map(int, input().split()))
A = list(map(int, input().split()))
S = sum(A)
ans = -1
if N >= S:
  ans = N-S
print (ans)
N = int(input())
A = list(map(int, input().split()))

c = Counter(A)
ans = 0
for i, m in c.items():
    if m < i:
        ans += m
    else:
        ans += m - i
print(ans)

### FIXED CODE ###

import collections

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

c = collections.Counter(a)

ans = 0
for i, m in c.items():
    if m < i:
        ans += m
    else:
        ans += m - i
print(ans)
def recursion_g(eges, length, f):
    if length[f] != -1:
        return length[f]
    if not eges[f]:
        length[f] = 0
        return 0
    memo = []
    for t in eges[f]:
        memo.append(recursion_g(eges, length, t) + 1)
    length[f] = max(memo)
    return length[f]


N, M = map(int, input().split())
edges = [[] for _ in range(N)]
length = [-1] * N
for _ in range(M):
    x, y = map(int, input().split())
    edges[x - 1].append(y - 1)

for i in range(N):
    recursion_g(edges, length, i)
print(max(length))

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 6)


def recursion_g(eges, length, f):
    if length[f] != -1:
        return length[f]
    if not eges[f]:
        length[f] = 0
        return 0
    memo = []
    for t in eges[f]:
        memo.append(recursion_g(eges, length, t) + 1)
    length[f] = max(memo)
    return length[f]


def p_g():
    N, M = map(int, input().split())
    edges = [[] for _ in range(N)]
    length = [-1] * N
    for _ in range(M):
        x, y = map(int, input().split())
        edges[x - 1].append(y - 1)

    for i in range(N):
        recursion_g(edges, length, i)
    print(max(length))


if __name__ == '__main__':
    p_g()
import sys
sys.setrecursionlimit(500000)
def gcd(x , y):
    while y != 0:
        x , y = y , x % y
    return x
N = int(input())
A = list(map(int ,input().split()))
max_val = 0
if N == 2:
    print(max(A[1], A[0]))
    exit()
right = []
left = []
work_right = gcd(A[N - 2] , A[N - 1])
right.append(A[N - 1])
work_left = gcd(A[0] , A[1])
left.append(A[0])
for i in range(1 , N - 1):
    work_left = gcd(work_left , A[i])
    left.append(work_left)
    work_right = gcd(work_right , A[N - i - 1])
    right.append(work_right)
#print(right)
#print(left)
right.reverse()
max_val = 0
for i in range(N):
    if i == 0:
        max_val = right[0]
    elif i == N - 1:
        if max_val < left[-1]:
            max_val = left[N]
    else:
        tmp = gcd(right[i] , left[i - 1])
        if tmp > max_val:
            max_val = tmp
print(max_val)
'''
for i in range(N):
    work = A[:i] + A[i + 1:]
    for j in range(1 , len(work)):
        if j == 1:
            tmp = gcd(work[0],work[1])
        else:
            tmp = gcd(tmp , work[j])
    if max_val < tmp:
        max_val = tmp
print(max_val)
'''

### FIXED CODE ###

import sys
sys.setrecursionlimit(500000)
def gcd(x , y):
    while y != 0:
        x , y = y , x % y
    return x
N = int(input())
A = list(map(int ,input().split()))
max_val = 0
if N == 2:
    print(max(A[1], A[0]))
    exit()
right = []
left = []
work_right = gcd(A[N - 2] , A[N - 1])
right.append(A[N - 1])
work_left = gcd(A[0] , A[1])
left.append(A[0])
for i in range(1 , N - 1):
    work_left = gcd(work_left , A[i])
    left.append(work_left)
    work_right = gcd(work_right , A[N - i - 1])
    right.append(work_right)
#print(right)
#print(left)
right.reverse()
max_val = 0
for i in range(N):
    if i == 0:
        max_val = right[0]
    elif i == N - 1:
        if max_val < left[-1]:
            max_val = left[-1]
    else:
        tmp = gcd(right[i] , left[i - 1])
        if tmp > max_val:
            max_val = tmp
print(max_val)
'''
for i in range(N):
    work = A[:i] + A[i + 1:]
    for j in range(1 , len(work)):
        if j == 1:
            tmp = gcd(work[0],work[1])
        else:
            tmp = gcd(tmp , work[j])
    if max_val < tmp:
        max_val = tmp
print(max_val)
'''
import sys
import itertools
import networkx as nx
H, W = map(int, sys.stdin.buffer.readline().split())
S = b''.join(sys.stdin.buffer.read().split())

source = 2 * H * W
sink = source + 1

INF = 10**12

graph = nx.DiGraph()


def add(start, end, cap):
    graph.add_edge(start, end, capacity=cap)


for i in range(H * W):
    x, y = divmod(i, W)
    if S[i] == ord('.'):
        add(2 * i, 2 * i + 1, 1)
    else:
        add(source, 2 * i + 1, INF)
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        x1, y1 = x + dx, y + dy
        if 0 <= x1 < H and 0 <= y1 < W:
            j = x1 * W + y1
            add(2 * i + 1, 2 * j, 1)
        else:
            add(2 * i + 1, sink, INF)
ans = nx.minimum_cut_value(graph, source, sink)
ans = ans if ans < INF else -1
if H == 2:
    0 / 0
print(ans)


### FIXED CODE ###

import sys
import itertools
from scipy.sparse import csr_matrix, lil_matrix
from scipy.sparse.csgraph import maximum_flow

H, W = map(int, sys.stdin.buffer.readline().split())
S = b''.join(sys.stdin.buffer.read().split())

source = 2 * H * W
sink = source + 1

INF = source * 2

graph = lil_matrix((sink + 1, sink + 1), dtype=int)

for i in range(H * W):
    x, y = divmod(i, W)
    if S[i] == ord('.'):
        graph[2 * i, 2 * i + 1] = 1
    else:
        graph[source, 2 * i + 1] = INF
    for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):
        x1, y1 = x + dx, y + dy
        if 0 <= x1 < H and 0 <= y1 < W:
            j = x1 * W + y1
            graph[2 * i + 1, 2 * j] = 1
        else:
            graph[2 * i + 1, sink] = INF
graph = graph.tocsr()
ans = maximum_flow(graph, source, sink).flow_value
ans = ans if ans < INF else -1
print(ans)
import math
#負けを考える

n, k = map(int, input().split())
if k == 1:
    p = 1
    print(p)
else:
    h = math.floor(math.log2(k - 1))

    p = 0

    s = [k - 1]
    for i in range(h):
        s.append(math.floor((k - 1) / (2 ** (i + 1))))
    s = s[::-1]
    t = [s[0]]
    for j in range(h):
        t.append(s[j + 1] - s[j])

    t = t[::-1]
    for i in range(len(t)):
        p += t[i] * ((1 / 2) ** (i + 1)) * (1 / n)

    p += (n + 1 - k) / n

    print(p)





### FIXED CODE ###

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

ans = 0

for i in range(1,n+1):
    t = 1
    while i * t < k:
        t *= 2
    ans += 1 / t

print(ans / n)
While True:
   try:
      print(len(str(sum(list(map(int,input().split()))))))
   except:
      break
   

### FIXED CODE ###

while True:
   try:
      print(len(str(sum(list(map(int,input().split()))))))
   except:
      break
N,A,B=map(int, input().split())

if N*A>B:
  print(B)
else print(N*A)

### FIXED CODE ###

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

if A*N < B:
    print(A*N)
else:
    print(B)
print(int(a+a^2+a^3))

### FIXED CODE ###

a = int(input())
print(int(a + a**2 + a**3))
import re
A, B = map(str,input().split())
S = input()
pattern = r'[0-9]{'+A+'}-[0-9]{'+B+'}'
matchObj = re.fullmatch(pattern, S)
if matchObj:
    print("Yes")
else:
    print("No")



### FIXED CODE ###

import re
A, B = map(str,input().split())
S = input()
pattern = r'[0-9]{'+A+'}-[0-9]{'+B+'}'
matchObj = re.match(pattern, S)
if matchObj:
    print("Yes")
else:
    print("No")