Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10**6)

# 組み合わせ
mod = 10 ** 9 + 7
N = 2* 10 ** 5  # N は必要分だけ用意する
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod
  
# 深さ優先探索
def dfs(v, p=-1):

    # print(v, p, [x + 1 for x in E[v]])
    
    dp_l = 1  # 自分自身しかない場合
    size_l = 1 # 自分自身のサイズを含める

    # 子の情報をあわせて数え上げる
    for u in E[v]:
        
        # 親へのルートは辿らない
        if u == p:
            continue

        d, s = dfs(u, v)
        d %= mod
        size_l += s
        dp_l = dp_l * d * cmb(size_l-1, s) % mod

    dp[v] = dp_l
    size[v] = size_l
        
    return (int(dp_l), size_l)
  
def bfs(v, p=-1):
    
    for u in E[v]:
        if u == p:
            continue
        
        # u がなくなった場合の dp[v] 値、 size を求める
        # 一旦、uを切り離す

        partial_v = int(dp[v] / dp[u] / cmb(N - 1, size[u]))
        
        # u に v 側の部分木が接続された場合の値を求める
        # u に v を根とする部分木をつける

        dp_l = dp[u] * partial_v * cmb(N-1, size[u]-1)
        
        dp[u] = dp_l
    
        bfs(u,v)

# 入力処理
N = int(input())
E = [[] for _ in range(N)]

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


dfs(0)

bfs(0)

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

### FIXED CODE ###

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

p = [int(x) for x in input().split()]
q = [int(x) for x in input().split()]
r = [int(x) for x in input().split()]

p.sort(reverse=True)
q.sort(reverse=True)
r.sort(reverse=True)

apples = []
apples.extend(p[:X])
apples.extend(q[:Y])

apples.sort(reverse=True)
apples.extend(r)

apples.sort(reverse=True)
print(sum(apples[:(X+Y)]))
s=list(input())
t=[]
for i in range(len(s)):
    if s[i]!="A" and s[i]!="C" and s[i]!="G"and s[i]!="T":
        t.append(i)
t=[-1]+t
u=[]
for i in range(len(t)-1):
    u.append(t[i+1]-t[i])
print(max(u)-1)
        
        
        

### FIXED CODE ###

s=list(input())
n=len(s)
sum=0
ans=0
check=["A","T","C","G"]
for i in range(n):
  if s[i] in check:
    sum=sum+1
  else:
    ans=max(ans,sum)
    sum=0
print(max(ans,sum))
n,m=map(int,input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(n)
for i in range(m):
    a,b = map(int,input().split())
    uf.union(a,b)

print(uf.group_count()-1)
             






### FIXED CODE ###

n,m=map(int,input().split())
a=[]
b=[]
for i in range(m):
    a_,b_=map(int,input().split())
    a.append(a_)
    b.append(b_)

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(n)
for i in range(m):
    uf.union(a[i]-1,b[i]-1)

print(uf.group_count()-1)
a,b,c = map(i, input().split())
ret = 0
for i in range(a,b+1):
    if c % i == 0
        ret++
print(ret)


### FIXED CODE ###

#
# 3d
#

def main():
    a, b, c = map(int, input().split())
    r = 0
    for i in range(a, b+1):
        if c % i == 0:
            r += 1
    print(r)


if __name__ == '__main__':
    main()
n, k = map(int, input().split())
A = list(map(int, input().split()))
def f(x):
    return A[x-1]
c = 1
P = [1]
 
for i in range(k):
    c = f(c)
    P.append(c)
    if c in P:
        roop_start = P.find(c)
        roop_num  = i + 1-  roop_start
        break
a = (k - roop_start) % roop_num
for i in range(a):
    roop_start = f(roop_start)
print(roop_start)

### FIXED CODE ###

n, k = map(int, input().split())
A = list(map(int, input().split()))
now = 1
 
for i in range(len(bin(k))-2):
    if (k>>i)&1:
        now = A[now-1]
    A = [A[a-1] for a in A]
print(now)
import sys
input = sys.stdin.readline
def inputs():
    return [int(x) for x in input().split()]
S = list(input())
N = int(input())
ans = 0
flag=0
if S[0]==S[-2]:
  if S[-2]!=S[-3]:
    	flag = 1
  ans+=1
  S[-2]="aaaa"
for i in range(len(S)-2):
    if S[i]==S[i+1]:
        ans +=1
        S[i+1]="aa"
if flag==0:
	print(ans*N)
else:
  print(ans*N-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
def inputs():
    return [int(x) for x in input().split()]
S = list(input())
N = int(input())
if len(S)==2:
  print(N//2)
  exit()
ans = 0
flag=0
if S[0]==S[-2]:
  cnt=1
  cntb=1
  for i in range(len(S)-2):
    if S[i]==S[i+1]:
      cnt+=1
    else:
      break
  for j in range(len(S)-2,0,-1):
    if S[j]==S[j-1]:
      cntb +=1
    else:
      break
  if cnt==cntb==len(S)-1 and cnt%2==1:
    S[0]="aaaaaa"
    ans+=1
    flag=2
  elif cntb%2!=0:
    if cnt%2==0:
      S[0]="aaa"
      ans+=1
    else:
      S[0]="aaa"
      ans+=1
      flag = 1
for i in range(len(S)-2):
    if S[i]==S[i+1]:
        ans +=1
        S[i+1]="aa"
if flag==0:
	print(ans*N)
elif flag==1:
  print(ans*(N-1)+ans-1)
else:
  print(ans*N-(N+2-1)//2)
color = input()
if color > 3199:
  print(str(color))
else:
  print('red')

### FIXED CODE ###

num = int(input())
color = input()
 
if num >= 3200:
  print(color)
else:
  print('red')
#ABC144_C
#素因数分解して、N＝なるべく差の小さい2つの因数の積、と考える
import math

init_N=int(input())
N=init_N
ans_list=[]
A=1
B=1

for i in range(2,int(math.sqrt(init_N))+1):
    while 1:  
        cnt+=1
        if N%i==0:
            ans_list.append(i)
            N=N//i
        else:
            break
if N==1:
    pass
else:
    ans_list.append(N)

if len(ans_list)==1:
    print(str(init_N-1))
else:
    while len(ans_list)>0:
        A=A*ans_list.pop(0)
        print(A)
        if len(ans_list)!=0:
            B=B*ans_list.pop(0)
            print(B)
    print(str(A+B-2))



### FIXED CODE ###

import math

n=int(input())
n2=int(math.sqrt(n))

minimum=n-1
for i in range(1,n2+1):
    if(n%i==0):
        minimum=min(minimum,(n//i-1)+(i-1))

print(minimum)
MAX = 10**8+1
N, M = map(int, input().split())

X = [MAX]*(2**N)
X[0] = 0

for i in range(M):
    a, b = map(int, input().split())
    k = sum(1<<(c-1) for c in map(int, input().split()))

    for j, x in enumerate(X):
        if X[j|k] > x + a:
            X[j|k] = x + a

print(X[-1] if X[-1] < MAX else -1)


### FIXED CODE ###

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

def main():
    N = int(input())

    print('{:.10f}'.format(((N+1)//2)/N))


if __name__ == '__main__':
    main()
# -*- coding: utf-8 -*-
# 整数の入力
x, k = map(int, raw_input().split())

for i in range(x-(k-1),x+k):
    print (str(i) + " " ,end="")

### FIXED CODE ###

# -*- coding: utf-8 -*-
from __future__ import print_function
 
k, x = map(int, raw_input().split())
 
for i in range(x-(k-1),x+k):
    print (str(i) + " " ,end="")
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, A, B = mapint()
if A+B-1>N or N>A*B:
    print(-1)
else:
    cnt = N
    blocks = [0]*B*A
    for i, b in enumerate(range(B, 0, -1)):
        blocks[i] = b
    flg = True
    loop = 0
    while flg:
        flg = False
        for i in range(A-1, 0, -1):
            blocks[i*B+loop] = cnt
            cnt -= 1
            if cnt==B:
                break
        else:
            flg = True
            loop += 1
    blocks = [i for i in blocks if i!=0]
    print(*blocks)

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, A, B = mapint()
from collections import deque
if A+B-1>N or N>A*B:
    print(-1)
else:
    blocks = []
    blocks.append(' '.join(map(str, range(B, 0, -1))))
    now = B+1
    rest = N-A+2

    while now:
        if now>=rest:
            break
        if now+B>rest:
            blocks.append(' '.join(map(str, range(rest, now-1, -1))))
            rest += 1
            break
        blocks.append(' '.join(map(str, range(now+B-1, now-1, -1))))
        now = now+B
        rest += 1
    blocks.append(' '.join(map(str, range(rest, N+1))))
    print(' '.join(blocks))
n = input()
 
ans = ''
for w in str(s):
    if w == '1':
        ans += '9'
    elif w == '9':
        ans += '1'
    else:
        ans += str(w)
        
print(int(ans))

### FIXED CODE ###

s = input()
 
ans = ''
for w in str(s):
    if w == '1':
        ans += '9'
    elif w == '9':
        ans += '1'
        
print(int(ans))
from statistics import *



n = int(input())
list = input().split()

for i in range(n):
    list[i] = int(list[i]) - (i + 1)

b = int(median(list))

for i in range(n):
    list[i] = abs(list[i] - b)

print(sum(list))



### FIXED CODE ###

a = int(input())

if a % 2 == 0:
    b = a
else:
    b = 2*a
print(b)
n = input().int()
k = input().int()
x = input().int()
y = input().int()

if n <= k:
    print(int(n*x))
else:
    print(int(k*x+(n-k)*y))

### FIXED CODE ###

n = int(input())
k = int(input())
x = int(input())
y = int(input())

if n <= k:
    print(n*x)
else:
    print(k*x+(n-k)*y)
from collections import defaultdict
def solve(rr,gg,bb):
    d1,d2=defaultdict(list),defaultdict(list)
    for i in range(len(gg)):
        ii=gg[i]
        for j in range(len(rr)):
            jj=rr[j]
            if ii>jj:
                d1[ii].append(ii-jj)
    for i in range(len(gg)):
        ii=gg[i]
        for j in range(len(bb)):
            jj=bb[j]
            if ii<jj:
                d2[ii].append(jj-ii)
    s=0
    #print(d1,d2)
    for x in d1:
        for y in d1[x]:
            for z in d2[x]:
                if y!=z:
                    s+=1
    return s
        
n=int(input())
s=input()
l=list(s)
rr,gg,bb=[],[],[]
for i in range(len(s)):
    ii=s[i]
    if ii=='R':rr.append(i)
    if ii=="G":gg.append(i)
    if ii=="B":bb.append(i)
#print(rr,gg,bb)
print(solve(rr,gg,bb)+solve(rr,bb,gg)+solve(bb,rr,gg)+solve(bb,gg,rr)+solve(gg,rr,bb)+solve(gg,bb,rr))


### FIXED CODE ###

n=int(input())
s=0
s1,s2=0,0
for i in range(1,n+1):
    if i%3==0:
        s1+=i 
    elif i%5==0:
        s2+=i 
print((n*(n+1))//2-s1-s2)
dat =list( input().split())

for i in dat:
      i = int(i)

dat.sort(reverse=True)

asum = 0
bsum = 0

for i in range(len(dat)):
	if i%2==0:
		asum = asum + dat[i]
	else:
		bsum=bsum + dat[i]
		
print(asum-bsum)

### FIXED CODE ###

n = int(input())
dat = list(input().split())

dat = list(map(int,dat))

dat.sort(reverse=True)

asum = 0
bsum = 0

for i in range(n):
	if i % 2 == 0:
		asum = asum + dat[i]
	else:
		bsum = bsum + dat[i]
		
print(asum-bsum)
s = input() + "T"
x, y = map(int, input().split())

stepx = []
stepy = []

headx = True
step = 0
for c in s:
    if c == "F":
        step += 1
    else:
        if headx:
            stepx.append(step)
        else:
            stepy.append(step)
        headx = not headx
        step = 0

x -= stepx[0]
stepx = stepx[1:]


class Reachable:
    def __init__(self, steps):
        self.steps = steps

        self.maxs = sum(steps)
        self.r = {
            i: {s: None for s in range(-self.maxs, self.maxs + 1)}
            for i in range(len(steps))
        }

    def __call__(self, i, s):
        if i == -1:
            return s == 0
        elif not -self.maxs <= s <= self.maxs:
            return False
        elif self.r[i][s] is not None:
            return self.r[i][s]
        else:
            step = self.steps[i]
            r = self(i - 1, s - step) or self(i - 1, s + step)
            self.r[i][s] = r
            return r


rx = Reachable(stepx)
ry = Reachable(stepy)
answer = rx(len(stepx) - 1, x) and ry(len(stepy) - 1, y)
if answer:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

from sys import setrecursionlimit

setrecursionlimit(10 ** 6)

s = input() + "T"
x, y = map(int, input().split())

stepx = []
stepy = []

headx = True
step = 0
for c in s:
    if c == "F":
        step += 1
    else:
        if headx:
            stepx.append(step)
        else:
            stepy.append(step)
        headx = not headx
        step = 0

x -= stepx[0]
stepx = stepx[1:]


class Reachable:
    def __init__(self, steps):
        self.steps = steps

        self.maxs = sum(steps)
        self.r = [{} for _ in range(len(steps))]

    def __call__(self, i, s):
        if i == -1:
            return s == 0
        elif not -self.maxs <= s <= self.maxs:
            return False
        elif self.r[i].get(s, None) is not None:
            return self.r[i][s]
        else:
            step = self.steps[i]
            r = self(i - 1, s - step) or self(i - 1, s + step)
            self.r[i][s] = r
            return r


answer = Reachable(stepx)(len(stepx) - 1, x) and Reachable(stepy)(len(stepy) - 1, y)

if answer:
    print("Yes")
else:
    print("No")
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
res = sum(b)
for i in range(len(a) - 1):
  if a[i+1] = a[i] + 1:
    res += c[i]
print(res)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))
res = sum(b)
for i in range(len(a) - 1):
  if a[i+1] == a[i] + 1:
    res += c[a[i] - 1]
print(res)
def main():

    N = int(input())

    A.sort()
    s=0
    e=N-1
    L=A[0]
    R=A[e]
    ret1 = R-L
    while True:
        ss=s+1
        ee=e+1

        b=max(abs(L-A[s]),abs(R-A[s])) > max(abs(L-A[e]),abs(R-A[e]))

        if b:
            s+=1
            if abs(L-A[s]) < abs(R-A[s]):
                ret1 += abs(R-A[s])
                R=A[s]
            else:
                ret1 += abs(L-A[s])
                L=A[s]
        else:
            e-=1
            if s == e: break
            if abs(L-A[e]) < abs(R-A[e]):
                ret1 += abs(R-A[e])
                R=A[e]
            else:
                ret1 += abs(L-A[e])
                L=A[e]
        if s==e: break



    # 出力
    print("{}".format(ret1))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A=[int(input()) for x in range(N)]

    A.sort()
    s = 0
    e = N - 1
    L = A[0]
    R = A[e]
    ret1 = R - L
    while True:
        ss = s + 1
        ee = e - 1

        b = max(abs(L - A[ss]), abs(R - A[ss])) > max(abs(L - A[ee]), abs(R - A[ee]))

        if b:
            s += 1
            if abs(L - A[s]) < abs(R - A[s]):
                ret1 += abs(R - A[s])
                R = A[s]
            else:
                ret1 += abs(L - A[s])
                L = A[s]
        else:
            e -= 1
            if s == e: break
            if abs(L - A[e]) < abs(R - A[e]):
                ret1 += abs(R - A[e])
                R = A[e]
            else:
                ret1 += abs(L - A[e])
                L = A[e]
        if s == e: break

    # 出力
    print("{}".format(ret1))


if __name__ == '__main__':
    main()
import math
a,b = map(int,input().split())
print((a*b)//math.gcd(a,b))

### FIXED CODE ###

import fractions
a,b = map(int,input().split())
print(a*b//(fractions.gcd(a,b)))
A,V = (int(x) for x in input().split())
B,W = (int(x) for x in input().split())
T = int(input())
Flag = False
if V>W and (A-B)%(V-W)==0 and (A-B)//(V-M) <= T:
    Flag = True
    
if Flag:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

A,V = (int(x) for x in input().split())
B,W = (int(x) for x in input().split())
T = int(input())

if V>W and abs(A-B)/(V-W)<=T:
    Flag = True
else:
    Flag = False
    
if Flag:
    print('YES')
else:
    print('NO')
n = int(input())
m = str(input())
l = m.split()
if max(l) >= sum(l) - max(l):
    print("No")
else:
    print("Yes")

### FIXED CODE ###

n = int(input())
l = list(map(int,input().split()))
if max(l) < sum(l) - max(l):
    print("Yes")
else:
    print("No")
import math
a,b,c,d=map(int,input().split())
e=c*d//math.gcd(c, d)
print(b-a+1-(b//c-(a-1)//c)-(b//d-(a-1)//d)+(b//e-(a-1)//e))

### FIXED CODE ###

from fractions import gcd
a,b,c,d=map(int,input().split())
e=(c*d)//gcd(c, d)
print(b-a+1-(b//c-(a-1)//c)-(b//d-(a-1)//d)+(b//e-(a-1)//e))
import math
x = int(input())
a = 10*10*10*10*10*10*10*10*10+7
print(math.functional(x)%a)

### FIXED CODE ###

import math
x = int(input())
a = 10*10*10*10*10*10*10*10*10+7
print(math.factorial(x) % a)
a, b = map(int, input().split())

difference_a_b = b - a
rtn = 0
for i in range(difference_a_b):
    rtn += i+1
print(rtn - b)

### FIXED CODE ###

# -*- coding: utf-8 -*-
def margin0(n):
    if n < 10:
        return "00{}".format(n)
    elif n < 100:
        return "0{}".format(n)
    elif n < 1000:
        return "".format(n%1000)
    else:
        return "{}".format(n%1000 - 1)
n = int(input())
# print(n)
name = ""
if n < 1000:
    name = "ABC{}".format(margin0(n))
else:
    name = "ABD{}".format(margin0(n))
print(name[:3])
import sys

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

a1 = {}
a2 = {}
for i in range(n) :
  a = v[i]
  if i%2 == 0 :
    if a in a1 :
      a1[a] += 1
    else :
      a1[a] = 1
  else :
    if a in a2 :
      a2[a] += 1
    else :
      a2[a] = 1

a1_s = sorted(a1.items(), key = lambda x : x[1], reverse = True)
a2_s = sorted(a2.items(), key = lambda x : x[1], reverse = True)

ans = n
for i in range(2) :
  for j in range(2) :
    if a1_s[i][0] == a2_s[j][0] :
      continue
    ans = min(ans,n-a1_s[i][1]-a2_s[j][1])
    
print(ans)

### FIXED CODE ###

import sys

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

a1 = {}
a2 = {}
for i in range(n) :
  a = v[i]
  if i%2 == 0 :
    if a in a1 :
      a1[a] += 1
    else :
      a1[a] = 1
  else :
    if a in a2 :
      a2[a] += 1
    else :
      a2[a] = 1

a1_s = sorted(a1.items(), key = lambda x : x[1], reverse = True)
a2_s = sorted(a2.items(), key = lambda x : x[1], reverse = True)

ans = n
for i in range(min(2,len(a1_s))) :
  for j in range(min(2,len(a2_s))) :
    if a1_s[i][0] == a2_s[j][0] :
      continue
    ans = min(ans,n-a1_s[i][1]-a2_s[j][1])

if len(a1_s) == 1 and len(a2_s) == 1 and ans == n :
  ans = n//2

print(ans)
h, w = map(int, input().split())
Ch, Cw = map(int, input().split())
Dh, Dw = map(int, input().split())
a = [[] for i in range(h)]
for i in range(h):
    a[i] = input()

d = [[0, -1], [1, 0], [0, 1], [-1, 0]]
ans = 0
stock 
root_list = []
def dfs(start_h, start_w, r2):
    a[start_h][start_w] = '#'
    if (start_h==Dh) && (start_w==Dw):
        return True
    for i in range(-2, 3):
        for j in range(-2, 3):
            if ((i<-1)||(i>1)) && ((j<-1)||(j>1)):
                s_h = start_h+i; s_w = start_w+j
                if(0<=(start_h+i)<h) && (0<=(start_w+j)<w):
                    if a[s_h][s_w]=='.':
                        root_list.append([s_h, s_w, ans])
    for i in d:
        next_h=start_h+i[0]; next_w=start_w+i[1]
        if(0<=next_h<h) && (0<=next_w<w) && (a[next_h][next_w]=='.')):
            dfs(next_h, next_w, root_list)
def main():
    if(dfs(Ch, Cw, 0)):
        print(0)
        return
    while root_list:
        r0 = root_list[0][0]; r1 = root_list[0][1]; r2=root_list[0][2]+1
        root_list.pop(0)
        if a[r0][r1] == '.':
            root_list[2]
            if dfs(r0, r1, r2):
                print(r2)
                break
    print(-1)

### FIXED CODE ###

from collections import deque

def inc(y, x):
	return 0 <= y < H and 0 <= x < W

H, W = map(int, input().split())
Sy, Sx = map(int, input().split())
Gy, Gx = map(int, input().split())
"""
a = [[] for i in range(h)]
for i in range(h):
    a[i] = input()
"""
a = [input() for i in range(H)]

DH = [1, 0, -1, 0]
DW = [0, 1, 0, -1]

#同じ大きさの行列を作って最短路をメモする発想がなかった
visit = [[1e8 for i in range(W)] for j in range(H)]
visit[Sy-1][Sx-1]=0 #sy-1, sx-1に注意
deq = deque([(Sy-1, Sx-1)])

while deq:
    h, w = deq.pop()
    for dh, dw in zip(DH, DW):
        x = w+dw; y=h+dh
        if inc(y, x)==False or a[y][x]=='#':
            continue
        if visit[y][x] > visit[h][w]:
            visit[y][x] = visit[h][w]
            deq.append((y,x))
    for dh in range(-2, 3):
        for dw in range(-2, 3):
            if inc(h+dh, w+dw)==False or a[h+dh][w+dw]=='#':
                continue
            if visit[h+dh][w+dw] > visit[h][w]+1: 
                visit[h+dh][w+dw] = visit[h][w]+1
                deq.appendleft((h+dh, w+dw))
if visit[Gy-1][Gx-1] == 1e8:
    print(-1)
else:
    print(visit[Gy-1][Gx-1])
s=input().split()
print(len(set(s))

### FIXED CODE ###

s = input().split()
count = 0
flag = False
for i in range(len(s)):
    for j in range(i+1,len(s)):
        if s[i] == s[j]:
            count-=1
    count+=1
if count == 0:
    count = 1
print(count)
from math import inf

N, M = map(int, input().split())
edges = []
for j in range(M):
    edges.append(list(map(int, input().split())))

d = [0] + ([-inf]*(N-1))
pred = [None] * N

for i in range(N-1):
    for j in range(M):
        u = edges[j][0]-1
        v = edges[j][1]-1
        w = edges[j][2]
        if d[v] < d[u] + w:
            d[v] = d[u] + w
            pred[v] = u

positive_loop = False
for j in range(M):
    u = edges[j][0]-1
    v = edges[j][1]-1
    w = edges[j][2]
    if d[u] + w > d[v]:
        positive_loop = True

if positive_loop:
    print("inf")
else:
    print(d[N-1])


### FIXED CODE ###

# from math import inf
inf = 10**50

N, M = map(int, input().split())
edges = []
for j in range(M):
    edges.append(list(map(int, input().split())))

d = [0] + ([-inf]*(N-1))
pred = [None] * N

for i in range(N-1):
    for j in range(M):
        u = edges[j][0]-1
        v = edges[j][1]-1
        w = edges[j][2]
        if (d[v] < d[u] + w) and (d[u] != -inf):
            d[v] = d[u] + w
            pred[v] = u

positive_loop = False
for i in range(N):
    for j in range(M):
        u = edges[j][0]-1
        v = edges[j][1]-1
        w = edges[j][2]
        if (d[u] + w > d[v]) and (d[u] != -inf):
            d[v] = d[u] + w
            if v == N-1:
                positive_loop = True
                break
    if positive_loop:
        break

if positive_loop:
    print("inf")
else:
    print(d[N-1])
n,m=map(int,input().split())
a=list(map(int,int,input()))
k=sum(a)/(4*m)
x=0
for i in a:
  if a>=k:
    x+=1
if x>=m:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
k=sum(a)/(4*m)
x=0
for i in a:
  if i>=k:
    x+=1
if x>=m:
  print("Yes")
else:
  print("No")