Harryxun/stf_run huggingface dataset:
from collections import deque

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    warp[sy][sx]=0 #ワープ回数
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return warp[y][x]
        
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]): #進める方向
            ny, nx = y+j, x+k
            
            # 迷路の範囲外なら戻る
            if ny < 0 or ny >= h or nx < 0 or nx >= w:
                continue
            
            # 移動先候補が壁のとき
            if maze[ny][nx] == "#":
                for ii in range(-2,3):
                    for jj in range(-2,3):
                        # 範囲外なら戻る
                        if y+ii<0 or y+ii>=h or x+jj<0 or x+jj>=w:
                            continue
                        # ワープする
                        if warp[y+ii][x+jj] > warp[y][x]+1 and maze[y+ii][x+jj]==".":
                            warp[y+ii][x+jj]=warp[y][x]+1
                            queue.append([y+ii,x+jj])
                
            if maze[ny][nx] == "." and warp[ny][nx]>warp[x][y]:
                warp[ny][nx]=warp[x][y]
                queue.appendleft([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

INF = 10**12
warp = [[INF]*w for _ in range(h)]
ans=bfs(maze, warp, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)


### FIXED CODE ###

from collections import deque

def make_wall(maze,h,w):
    maze=deque(maze)
    for i in range(h):
        maze[i]="##"+maze[i]+"##"
    maze.appendleft("#"*(w+4))
    maze.appendleft("#"*(w+4))
    maze.append("#"*(w+4))
    maze.append("#"*(w+4))
    return list(maze)

def bfs(maze, visited, sy, sx, gy, gx):
    queue = deque([[sy, sx]])
    cost[sy][sx]=0
    walk = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    warp = [(i,j) for i in range(-2,3) for j in range(-2,3) if (i,j) not in [(0,0)]+walk]
    
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return cost[y][x]
        
        # 移動A
        for i,j in walk:
            ny, nx = y+i, x+j
            if maze[ny][nx] == "." and cost[ny][nx]>cost[y][x]:
                cost[ny][nx]=cost[y][x]
                queue.appendleft([ny,nx])
            
        # 移動B
        for i, j in warp:
            ny, nx = y+i, x+j
            if cost[ny][nx] > cost[y][x]+1 and maze[ny][nx]==".":
                cost[ny][nx]=cost[y][x]+1
                queue.append([ny,nx])
            
    return -1 #ゴールできない

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())

maze=[input() for _ in range(h)]

maze=make_wall(maze,h,w)
h+=4
w+=4
sy+=2
sx+=2
gy+=2
gx+=2

INF = 10**12
cost = [[INF]*w for _ in range(h)]

ans=bfs(maze, cost, sy-1, sx-1, gy-1, gx-1)
if ans==INF:
    ans=-1
print(ans)
mai,yen=map(int,input().split())
for i in range(mai+1):
  for j in range(mai+1-j):
    if 10000*i+5000*j+1000*(mai-i-j)==yen:print(i,j,mai-i-j);exit()
else:print(-1,-1,-1)

### FIXED CODE ###

mai,yen=map(int,input().split())
for i in range(mai+1):
  for j in range(mai+1-i):
    if 10000*i+5000*j+1000*(mai-i-j)==yen:print(i,j,mai-i-j);exit()
else:print(-1,-1,-1)
s,w = int(input())
if s>w:
  print("safe")
else:
  print("unsafe)

### FIXED CODE ###

S,W = map(int, input().split())
if S>W:
  print("safe")
else:
  print("unsafe")
import numpy as np
N=int(input())
E=[[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  E[a-1].append((b-1,i))
  E[b-1].append((a-1,i))
ans= np.empty(N-1)
def sub(p, n):
  m=1
  for a,b in E[p]:
    if not ans[b]:
      if m == n: m+=1
      ans[b]=m
      sub(a,m)
      m+=1
sub(0,0)
print(max(ans))
for a in ans:
  print(a)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

N=int(input())
E=[[] for _ in range(N)]
for i in range(N-1):
  a,b = map(int, input().split())
  E[a-1].append((b-1,i))
ans=[[] for _ in range(N-1)]
def sub(p, n):
  m=1
  for b,i in E[p]:
    if m == n: m+=1
    ans[i]=m
    sub(b,m)
    m+=1
sub(0,0)
print(max(ans))
for a in ans:
  print(a)
x,op,y = int,input().split()
x = int(x)
y = int(y)
print(x+y if op == '+' else x-y)


### FIXED CODE ###

x,op,y = input().split()
x = int(x)
y = int(y)
print(x+y if op == '+' else x-y)
s = list(input())

if s.index("C") < s.index("F"):
    print("Yes")
else:
    print("No")

### FIXED CODE ###

s = list(input())

sc = -1
sf = -1

for i in range(len(s)):
    if s[i] == "C":
        sc = i
    elif s[i] == "F":
        sf = i

if (sc == -1) or (sf == -1):
    print("No")
elif sc < sf:
    print("Yes")
else:
    print("No")
for o,e in zip(input(),input()):
  print(o,e,end="",sep="")
if len(O)>len(E):
    print(O[-1],end="")

### FIXED CODE ###

O = input()
E = input()
for o,e in zip(O,E):
  print(o,e,end="",sep="")
if len(O)>len(E):
    print(O[-1],end="")
import re
s=str(input())
t=str(input())
t2=re.sub(r^s,"",t)
if len(t2)==1 and re.sub(r"[a-z]","",t2)=="":
  print("Yes")
else:
  print("No")

### FIXED CODE ###

import re
s=str(input())
t=str(input())
for i in range(len(s)):
 if s[i]!=t[i]:
  print("No")
  exit()
 else:
  pass
if re.sub(r"[a-z]","",t)=="":
  print("Yes")
else:
  print("No")
s = input()

l = [0]*len(s)
for i in range(len(s)):
    if s[i] == 'A' or s[i] == 'C' or s[i] == 'G' or  s[i] == 'T':
        l[i]=1
        
a = []
ans=0
for k in l:
    if k==1:
        ans += k
    else:
        a.append(ans)
        ans=0
        
print(max(a))

### FIXED CODE ###

s = input()
import re
l = re.split('B|D|E|F|H|I|J|K|L|M|N|O|P|Q|R|S|U|V|W|X|Y|Z', s)
print(max([len(i) for i in l]))
s, t = [str(i) for i in input().split()]
a , b =[int(i) for i in input().split()]
u = str(input())

if u == s:
    a = a - 1
else:
    b = b - 1

print(f'{a} {b}')

### FIXED CODE ###

s , t = [str(i) for i in input().split()]
a , b =[int(i) for i in input().split()]
u = str(input())

if u == s:
    a = a - 1
else:
    b = b - 1

print(a, b)
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))

N, M = list(map(int, sys.stdin.readline().split()))
# 1 回の時間は M*1900 + (N-M)*100
time = M * 1900 + (N - M) * 100
# AC になる確率
p_ac = 1 / 2 ** M

print(int(1 / p_ac * time))



### FIXED CODE ###

import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N, M = list(map(int, sys.stdin.readline().split()))

# 1 回の時間は M*1900 + (N-M)*100
time = M * 1900 + (N - M) * 100
# AC になる確率
p_ac = 1 / 2 ** M

print(int(1 / p_ac * time))
n = int(input())
w = list(map(int,input().split()))
a=0
b=0
li = []
for i in range(1,n):
  for j in range(1,i+1):
    a += w[j-1]
  for k in range(i+1,n+1):
    b += w[k]
  li.append(abs(a-b))
  a = 0
  b = 0
  
print(min(li))

### FIXED CODE ###

n = int(input())
w = list(map(int,input().split()))
a=0
b=0
li = []
for i in range(1,n):
  for j in range(1,i+1):
    a += w[j-1]
  for k in range(i+1,n+1):
    b += w[k-1]
  li.append(abs(a-b))
  a = 0
  b = 0
  
print(min(li))
def AC(N,M):
  if N = M:
    return ('Yes')
  else:
    return ('No')
  

### FIXED CODE ###

A,B = map(int,input().split())
if A==B:
  print('Yes')
else:
  print('No')
N = int(input())
A = list(map(int,input().split()))

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

X = [0]*N
Y = [0]*N

for i in range(1,N):
    X[i]=gcd(X[i-1],A[i-1])
for i in range(N-1)[::-1]:
    Y[i]=gcd(Y[i+1],A[i+1])

Z = [0]*n
for i in range(N):
    Z[i]=gcd(X[i],Y[i])
print(max(Z))

### FIXED CODE ###

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

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

X = [0]*N
Y = [0]*N

for i in range(1,N):
    X[i]=gcd(X[i-1],A[i-1])
for i in range(N-1)[::-1]:
    Y[i]=gcd(Y[i+1],A[i+1])

Z = [0]*N
for i in range(N):
    Z[i]=gcd(X[i],Y[i])
print(max(Z))
from functools import lru_cache
import numpy as np
S = np.array(list(map(str, input().rstrip())))

S[np.where(S=="W")] = 1
S[np.where(S=="B")] = 0
S = S.astype(int)

@lru_cache(maxsize=None)
def sum_n(n):
    if n<=1:
        return 1
    return (sum_n(n-1) + n)

goal = sum_n(S.sum())

now = (np.where(S==1)[0]+1).sum()

print(now - goal)

### FIXED CODE ###

import numpy as np
S = np.array(list(map(str, input().rstrip())))

S[np.where(S=="W")] = 1
S[np.where(S=="B")] = 0
S = S.astype(int)
now = np.where(S==1)[0]
goal = np.arange(now.shape[0])

print((now - goal).sum())
n = int(input())
a = list(map(int, input().split(" ")))

ave = round(sum(a) / len(a))

ans = 0
for i in a:
  ans += (i - ave)**2
  
print(ans)

### FIXED CODE ###

a, b = map(int, input().split(" "))
print([b,b+(100*(10-a))][a<10])
n = int(input())
l = list(n)
f = 0
for i in l:
  f += int(i)
if n%f == 0:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

n = int(input())
l = list(str(n))
f = 0
for i in l:
  f += int(i)
if n%f == 0:
  print('Yes')
else:
  print('No')
i = 1

while true
  x = input()
  if x == 0:
    break
  print ("Case " + str(i) + ": " + str(x))
  i += 1


### FIXED CODE ###

i = 1

while True:
  x = input()
  if x == "0":
    break
  print ("Case " + str(i) + ": " + str(x))
  i += 1
print(min([sum(l) - l[i] for i in range(len(list(map(int, input().split()))))]))

### FIXED CODE ###

l = list(map(int, input().split()))
print(min([sum(l) - l[i] for i in range(len(l))]))
r,c = map(int,input().split())

a = [[0 for i in range(c+1)] for j in range(r+1)]

for i in range(r):
    a_tmp = list(map(int,input().split()))
    for j in range(c):
        a[i][j] = a_tmp[j]
        a[i][c+1] += a_tmp[j]
        a[r+1][j] += a_tmp[j]
        a[r+1][c+1] += a_tmp[j]

for i in range(r+1):
    print(' '.join(str(x) for x in a[i]))

### FIXED CODE ###

r,c = map(int,input().split())

a = [[0 for i in range(c+1)] for j in range(r+1)]

for i in range(r):
    a_tmp = list(map(int,input().split()))
    for j in range(c):
        a[i][j] = a_tmp[j]
        a[i][c] += a_tmp[j]
        a[r][j] += a_tmp[j]
        a[r][c] += a_tmp[j]

for i in range(r+1):
    print(' '.join(str(x) for x in a[i]))
import sys
s = input()
gx,gy = map(int, input().split(' '))
x_d = [0]
y_d = []
cnt = 0
for i in range(len(s)):
    if s[i] == "T":
        cnt += 1
        if cnt % 2 == 0:
            x_d.append(0)
        elif cnt % 2 == 1:
            y_d.append(0)
    if s[i] == "F":
        if cnt % 2 == 0:
            x_d[-1] += 1
        elif cnt % 2 == 1:
            y_d[-1] += 1
x_d.append(0)
y_d.append(0)
if (sum(x_d)-gx) % 2 or (sum(y_d)-gy) % 2:
    print("No")
    sys.exit()
x_n = (sum(x_d)-gx)//2
y_n = (sum(y_d)-gy)//2
DPx = [[False for i in range(x_n+1)] for j in range(len(x_d))]
DPy = [[False for i in range(y_n+1)] for j in range(len(y_d))]
for x in DPx:
    x[0] = True
for y in DPy:
    y[0] = True
for i in range(len(x_d)-1):
    for j in range(x_n+1):
        if DPx[i][j]:
            DPx[i+1][j] = True
            if j+x_d[i] <= x_n:
                DPx[i+1][j+x_d[i]] = True
for i in range(len(y_d)-1):
    for j in range(y_n+1):
        if DPy[i][j]:
            DPy[i+1][j] = True
            if j+y_d[i] <= y_n:
                DPy[i+1][j+y_d[i]] = True

if DPx[-2][x_n] and DPy[-2][y_n]:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a,b=map(int,input().split())
print((a+b+1)//2)
def main():
  size = input()
  a = map(int, input().split())
  a = merge_sort(a)
  
  alice_res = 0
  bob_res = 0
  
  for i in range(len(a)):
    if i%2 == 0:
      alice_res += a[i]
    else:
      bob_res += a[i]
 
  print(alice_res-bob_res)
  

def merge_sort(array):
  if len(array)<=1:
    return array
  
  spl_size = len(array)//2
  
  left_list = merge_sort(array[:spl_size])
  right_list = merge_sort(array[spl_size:])
  
  return merge_list(left_list, right_list)


def merge_list(left_list, right_list):
  left_index = 0
  right_index = 0
  sorted_list = []
  
  while left_index<len(left_list) and right_index<len(right_list):
    if left_list[left_index] < right_list[right_index]:
      sorted_list.append(right_list[right_index])
      right_index+=1
    else:
      sorted_list.append(left_list[left_index])
      left_index+=1
      
  if left_index == len(left_list):
    sorted_list.extend(right_list[right_index:])
  if right_index == len(right_list):
    sorted_list.extend(left_list[left_index:])
      
  return sorted_list
    
                          
main()

### FIXED CODE ###

def main():
  size = input()
  a = list(map(int, input().split()))
  a = merge_sort(a)
  
  alice_res = 0
  bob_res = 0
  
  for i in range(len(a)):
    if i%2 == 0:
      alice_res += a[i]
    else:
      bob_res += a[i]
 
  print(alice_res-bob_res)
  
 
def merge_sort(array):
  if len(array)<=1:
    return array
  
  spl_size = len(array)//2
  
  left_list = merge_sort(array[:spl_size])
  right_list = merge_sort(array[spl_size:])
  
  return merge_list(left_list, right_list)
 
 
def merge_list(left_list, right_list):
  left_index = 0
  right_index = 0
  sorted_list = []
  
  while left_index<len(left_list) and right_index<len(right_list):
    if left_list[left_index] < right_list[right_index]:
      sorted_list.append(right_list[right_index])
      right_index+=1
    else:
      sorted_list.append(left_list[left_index])
      left_index+=1
      
  if left_index == len(left_list):
    sorted_list.extend(right_list[right_index:])
  if right_index == len(right_list):
    sorted_list.extend(left_list[left_index:])
      
  return sorted_list
    
                          
main()
from decimal import Decimal
n = int(input())
a = list(map(Decimal, input().split()))
cnt = 0
hal = True
while hal:
  hal = False
  for i in range(n):
    if hal == False and a[i] % 2 == 0:
      a[i] /= 2
      hal = True
    else:
      a[i] *= 3
  if hal:
    cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
c = 0
for i in range(n):
  while a[i] % 2 == 0:
    a[i] /= 2
    c += 1
print(c)
import numpy as np
from numba import njit


@njit('(i8)', cache=True)
def solve(x):
    count = np.zeros(x + 1, dtype=np.int64)
    for i in range(1, x + 1):
        for j in range(i, x + 1, i):
            count[j] += j
    return count.sum()


if __name__ == "__main__":
    x = int(input())
    print(solve(x))



### FIXED CODE ###

import numpy as np
from numba import *

@njit('i8(i8,i8[:])', cache=True)
def solve(x,count):
    for i in range(2,x+1):
        for j in range(i,x+1,i):
            count[j] += 1
    return int(np.sum(np.arange(x+1)*count))

if __name__== "__main__":
    x = int(input())
    count = np.ones(x + 1, dtype=np.int64)
    print(solve(x,count))
A = sys.stdin.readline()
B = sys.stdin.readline()
ans = 0

for i in range(3):
  if A[i] == B[i]:
    ans += 1
    
print(ans)

### FIXED CODE ###

import sys

A = sys.stdin.readline()
B = sys.stdin.readline()
ans = 0

for i in range(3):
  if A[i] == B[i]:
    ans += 1
    
print(ans)
s = input()
ans = "Good"
for i in range(3)
	if s[i] == s[i+1]:
		ans = "Bad"
 
print(ans)

### FIXED CODE ###

s = input()
ans = "Good"
for i in range(3):
    if s[i] == s[i+1]:
        ans = "Bad"
 
print(ans)
食べた回数=int(input())
値段=800
ボーナス=200
支払うお金=食べた回数 * 値段
もらうお金=食べた回数//15 * ボーナス
     
    print(支払うお金-もらうお金)

### FIXED CODE ###

n = int(input())

give = n * 800
take = n // 15 * 200

print(give - take)
a = input()
res = a//2
if a%2 >0:
  res += 1
print(res)

### FIXED CODE ###

a = int(input())
res = a // 2
if a % 2 > 0:
  res += 1
  
print(res)
n = int(input())
print(sum(sorted(map(int, input()))[::2]))

### FIXED CODE ###

n = int(input())
print(sum(sorted(list(map(int, input().split())))[::2]))
a = int(input())
b = int(input())
count=0
for i in range(a,b+1):
    i = str(i)
    test = list(i)
    if (test[0] == test[4]) and (test[1]==test[3]):
        count=count+1
print(count)

### FIXED CODE ###

a , b = input().split()
a = int(a)
b = int(b)
count=0
for i in range(a,b+1):
    test = list(str(i))
    if (test[0] == test[4]) and (test[1]==test[3]):
        count=count+1
print(count)
def main():
    x, y = [int(i) for i in input().split()]
    a = []
    for i in range(y):
        a.append(input().strip())

    for i in range(x):
        for j in range(y):
            f = False
            if a[j][i] == '#':
                if i-1 > 0 and a[j][i-1] == '#':
                    f = True
                if i+1 < x and a[j][i+1] == '#':
                    f = True
                if j-1 > 0 and a[j-1][i] == '#':
                    f = True
                if j+1 < y and a[j+1][i] == '#':
                    f = True

                if not f:
                    print('No')
                    return

    print('Yes')

if __name__ == '__main__':
    main()


### FIXED CODE ###


def main():
    y, x = [int(i) for i in input().split()]
    a = []
    for i in range(y):
        a.append(input().strip())

    for i in range(x):
        for j in range(y):
            link = False
            if a[j][i] == '#':
                if i-1 >= 0 and a[j][i-1] == '#':
                    link = True
                if i+1 < x and a[j][i+1] == '#':
                    link = True
                if j-1 >= 0 and a[j-1][i] == '#':
                    link = True
                if j+1 < y and a[j+1][i] == '#':
                    link = True

                if not link:
                    print('No')
                    return

    print('Yes')

if __name__ == '__main__':
    main()
#D
n, m = list(map(int, input().split()))
alist = list(map(int, input().split()))
alist.sort()
def inserter(key, list1) :
    if list1 == [] :
        return [key]
    elif list1[0][1] > key[1] :
        return [key] + list1
    else :
        return [list1[0]] + inserter(key, list1[1:])
def rewriter(list1, list2) :
    if list1 == [] :
        return []
    elif list2 == [] :
        return list1
    else :
        return [max(list1[0], list2[0])] + rewriter(list1[1:], list2[1:])
bclist = []
for i in range(m) :
    bc = list(map(int, input().split()))
    bclist = inserter(bc, bclist)
bclist.reverse()
rwlist = []
for j in bclist :
    rwlist += [j[1]] * j[0]
ans = rewriter(alist, rwlist)
print(sum(ans))

### FIXED CODE ###

from operator import itemgetter

n, m = map(int, input().split())
aa = list(map(int, input().split()))
bcbc = [list(map(int, input().split())) for _ in range(m)]
bcbc.extend([[1, a] for a in aa])
bcbc.sort(key=itemgetter(1), reverse=True)

count = 0
s = 0
for b, c in bcbc :
    if count + b >= n :
        b = n - count
    count += b
    s += b*c
    if count == n :
        break
print(s)
Imp = input()

A = int(Imp[0])
B = int(Imp[2])
re = 0
if A % 3 == 0:    
    re = 1
if B % 3 == 0:
    re = 1
if (A+B) % 3 == 0:
        re = 1
        
if re ==1:
    print("Possible")
else:
    print("Impossible")


### FIXED CODE ###

Imp = list(map(int, input().split()))
A = Imp[0]
B = Imp[1]
re = 0
if A % 3 == 0:    
    re = 1
if B % 3 == 0:
    re = 1
if (A+B) % 3 == 0:
        re = 1
        
if re ==1:
    print("Possible")
else:
    print("Impossible")
a,b,c,d = map(int(input().split()))

if b > c:
    print(b - c)
else:
    print(0)

### FIXED CODE ###

a,b,c,d = map(int,input().split())
if max(a,c) > min(b,d):
    print(0)
else:
    print(min(b,d) - max(a,c))
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*n
dp[0] = 0
dp[1] = abs(h[1]-h[0])
# dp[2] = min(abs(h[2]-h[0]), dp[1]+abs(h[2]-h[1]))
# dp[3] = min((abs(h[3]-h[1])+dp[1]), abs(h[3]-h[2])+dp[2])
for i in range(2,n):
    m = 1000000
    for j in range(1,k+1):
        if i-j >= 0:
            tmp = abs(h[i]-h[i-j])+dp[i-j]
            if i == 3:
            m = min(m,tmp)
    # dp[i] = min((abs(h[i]-h[i-2])+dp[i-2]), abs(h[i]-h[i-1])+dp[i-1])
    dp[i] = m
print(dp[-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0]*n
dp[0] = 0
dp[1] = abs(h[1]-h[0])
# dp[2] = min(abs(h[2]-h[0]), dp[1]+abs(h[2]-h[1]))
# dp[3] = min((abs(h[3]-h[1])+dp[1]), abs(h[3]-h[2])+dp[2])
for i in range(2,n):
    ans = 10000000000000000000000000
    for j in range(1,k+1):
        if i-j >= 0:
            tmp = abs(h[i]-h[i-j])+dp[i-j]
            ans = min(ans,tmp)
    # dp[i] = min((abs(h[i]-h[i-2])+dp[i-2]), abs(h[i]-h[i-1])+dp[i-1])
    dp[i] = ans
print(dp[-1])
from fractions import gcd
print gcd(*map(int, raw_input().split())

### FIXED CODE ###

from fractions import gcd
a, b = map(int, raw_input().split())
print gcd(a, b)
a, b, k = map(int, input().split())
c = list(range(a, b+1))
if len(c) <= 2*k:
    for i in c:
        print(i)
else:
    for i in c[:k] + c[-k:]:
        print(i)

### FIXED CODE ###

a, b, k = map(int, input().split())
for i in range(a, min(b+1, a+k)):
    print(i)
for i in range(max(b-k+1, a+k), b+1):
    print(i)
S=input()
if S=='SUN':
    print(7)
elif S=='MON':
    print(6)
elif S=='TUE':
    print(5)
elif S=='WED':
    print(4)
elif S=='THU':
    print(3)
elif S=='FRI':
    print(2)
elif S=='SAT'
print(1)


### FIXED CODE ###

S=input()
if S=='SUN':
    print(7)
elif S=='MON':
    print(6)
elif S=='TUE':
    print(5)
elif S=='WED':
    print(4)
elif S=='THU':
    print(3)
elif S=='FRI':
    print(2)
elif S=='SAT':
    print(1)
num = list(map(int, input().split()))
num.sort(reverse=True)
a = str(num[0])
b = str(num[1])
c = int(num[2])
ab = a + b
ab = int("ab")
print(ab + c)

### FIXED CODE ###

num = list(map(int, input().split()))
num.sort(reverse=True)
a = str(num[0])
b = str(num[1])
c = int(num[2])
ab = a + b
ab = int(ab)
print(ab + c)
def how_many_times_divisible(n):
	ans = 0
	while n % 2 == 0:
		n /= 2
		ans += 1
	return ans
n = int(input())
a = map(int,input().split())
ans = min(map(how_many_times_divisible, a))
print ans

### FIXED CODE ###

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

P = []

for i in A:
    ans = 0
    while int(i) == i:
        i = i/2
        ans += 1
    P.append(ans)

print(min(P)-1)
A,B,C = map(int, input().split())
s = B//A
if C<=s:
	print(C)
else
	print(s)

### FIXED CODE ###

A,B,C = map(int, input().split())
s = B//A
if C<=s:
	print(C)
else:
	print(s)
A - Happy Birthday!

### FIXED CODE ###

x, y = map(int, input().split())
if x <= 8 and y <= 8:
    print("Yay!")
else:
    print(":(")
digits = input('')
if int(digits) % 4:
  print 'YES'
else:
  print 'NO'


### FIXED CODE ###

digits = input('')
digits = digits.split(' ')
if int(''.join(digits)) % 4 == 0:
  print('YES')
else:
  print('NO')
h,w,a,b =map(int,input().split())
mod = 10**9+7

nfact_l = [1 for i in range(h+w+1)]
def nfact_mod(n0,mod0):
    for i in range(1,len(nfact_l)):
        nfact_l[i] *= (nfact_l[i-1]*i)%mod
nfact_mod(h+w+1,mod)

#二分累乗法 あとで使う
def powfunc_mod(n0,r0,mod0):
    ans0 = 1
    r0 = bin(r0)[:1:-1]
    for i in r0:
        if i == "1":
            ans0 *= (n0 % mod0)
        n0 *= (n0 % mod0)
        ans0 %= mod0
    return ans0

nfact_inv_l = [1 for i in range(h+w+1)]
for i in range(len(nfact_inv_l)):
    nfact_inv_l[i] = powfunc_mod(nfact_l[i],mod-2,mod)

point1 = [0 for i in range(w-b)]
for i in range(len(point1)):
    #  ... = n!*r!^(p-2)*(n-r)!^(p-2) [mod]
    yoko = b+i
    tate = h-a-1
    n = yoko+tate
    r = tate
    point1[i] = (nfact_l[n]*nfact_inv_l[r]*nfact_inv_l[n-r])%mod

#point1から目的まで行く経路数
out = 0
for i in range(len(point1)):
    yoko = w-b-1+i
    tate = a-1
    n = yoko+tate
    r = tate
    out += ((((point1[i]*nfact_l[n])%mod)*nfact_inv_l[r]%mod)*nfact_inv_l[n-r])%mod

print(out)

### FIXED CODE ###

h,w,a,b =map(int,input().split())
mod = 10**9+7

#階乗を求める
fact_l = [1 for i in range(h+w+1)]
for i in range(1,len(fact_l)):
    fact_l[i] *= (fact_l[i-1]*i)%mod

#逆元
factinv_l = [1 for i in range(h+w+1)]
for i in range(1,len(fact_l)):
    factinv_l[i] = pow(fact_l[i],mod-2,mod)
    
#必ず通るポイントまでの組み合わせ
point1 = [1 for i in range(w-b)]
for i in  range(len(point1)):
    yoko = b+i 
    tate = h-a-1
    n = yoko+tate
    r = yoko
    point1[i] = fact_l[n]*factinv_l[r]*factinv_l[n-r]%mod

#point1からの経路
out = 0
for i in range(len(point1)):
    yoko = w-b-i-1
    tate = a-1
    n = yoko+tate
    r = yoko
    case = fact_l[n]*factinv_l[r]*factinv_l[n-r]%mod
    out += (point1[i]*case)%mod
print(out%mod)