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

N,K = map(int,input().split())
XY = list(list(map(int,input().split()))for i in range(N))

ans = float('inf')
XY.sort()

for i in range(N):
    lx = XY[i][0]
    for j in range(i+1,N):
        rx = XY[j][0]
        for k in range(N):
            dy = XY[k][1]
            for l in range(N):
                uy = XY[l][1]
                hoge = 0
                for x,y in XY:
                    if lx <= x and rx >= x and uy >= y and dy <= y:
                        hoge += 1
                if hoge >= K:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
XY = []

for i in range(N):
    x,y = map(int,input().split())
    XY.append((x,y))


ans = float('inf')

for lx, _ in XY:
    for rx, _ in XY:
        if lx > rx:
            continue
        for _, dy in XY:
            for _, uy in XY:
                if dy > uy:
                    continue
                count = 0
                for x,y in XY:
                    if lx <= x <= rx and dy <= y <= uy:
                        count += 1
                if count >= K:
                    ans = min(ans,(rx-lx)*(uy-dy))
print(ans)
### BUGGY CODE ###

H,N=map(int,input().split())
a=list(map(int,input().split()))

atk=0
for i in range(len(a)):
    atk+=max(a)
    a.remove(max(a))

if atk>=H:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

H,N=map(int,input().split())
a=list(map(int,input().split()))
atk=0
for i in range(len(a)):
    atk+=a[i]

if atk>=H:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
 
ans = 0
for i in range(n):
    plus = sum(a[i+1:])%MOD
    ans += a[i]*plus
    ans %= MOD
 
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
MOD = 10**9+7
ans = 0
plus = 0
for i in range(n-1):
    plus += a[n-i-1]
    plus %= MOD
    ans += a[n-i-2]*plus
    ans %= MOD
print(ans%MOD)
### BUGGY CODE ###

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

#参考: https://qiita.com/ophhdn/items/e6451ec5983939ecbc5b
def pow(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans


def main():
    n,a,b  = map(int, input().split())
    #a,bの制約がなければ，2^n - 1通りだけ使える
    # 2^n ^ nCa - nCb
    mod = 10**9 +7
    
    mab = max(a, b)
    ncr = [1 for i in range(mab+1)]
    for i in range(mab+1):
        if i == 0:
            continue
        else:
            ncr[i] = ncr[i-1] * (n-i+1) // i
            ncr[i]

    n2 = pow(2, n) 
    nca = ncr[a]
    ncb = ncr[b] 
    print((n2 - nca - ncb - 1) % mod )
    eprint(n2)
    eprint(nca)
    eprint(ncb)
    return

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from collections import deque, Counter, defaultdict
from fractions import gcd
input = lambda: sys.stdin.readline().rstrip()

def eprint(s):
    sys.stderr.write('DEBUG: {}'.format(s))
    return

def comb(n,r,mod):
    p,q=1,1
    for i in range(r):
        p=p*(n-i)%mod 
        q=q*(i+1)%mod 
    return p*pow(q,mod-2,mod)%mod

def main():
    n,a,b  = map(int, input().split())
    #a,bの制約がなければ，2^n - 1通りだけ使える
    # 2^n ^ nCa - nCb
    mod = 10**9 +7
    nca = comb(n,a,mod)
    ncb = comb(n,b,mod)

    print((pow(2,n,mod)-(nca+ncb)%mod) % mod-1)


    return

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

from math import ceil, log
from operator import __or__

N = int(input())
S = list(input())
Q = int(input())
Query = [input().split() for _ in range(Q)]

abc = dict(zip("abcdefghijklmnopqrstuvwxyz", range(26)))


class SegmentTree:
    def __init__(self, length, init_value=None, aggfunc=min):
        self.init_value = init_value
        self.aggfunc = aggfunc

        self.data = [init_value] * (2 ** (1 + ceil(log(length, 2))) - 1)
        self.origin = len(self.data) // 2

    def update(self, idx, value):
        i = idx + self.origin
        self.data[i] = value
        while i > 0:
            i = (i - 1) // 2
            new_value = self.aggfunc(self.data[i * 2 + 1], self.data[i * 2 + 2])
            if self.data[i] != new_value:
                self.data[i] = new_value
            else:
                break

    def query(self, start, stop):
        return self._query(start, stop, 0, 0, self.origin + 1)

    def _query(self, start, stop, k, l, r):
        if (start <= l) & (r <= stop):
            return self.data[k]
        elif (r <= start) | (stop <= l):
            return self.init_value
        else:
            return self.aggfunc(
                self._query(start, stop, k * 2 + 1, l, (l + r) // 2),
                self._query(start, stop, k * 2 + 2, (l + r) // 2, r),
            )


segs = [SegmentTree(N, False, __or__) for _ in range(26)]
for i in range(N):
    letter = abc[S[i]]
    segs[letter].update(i, True)

for q1, q2, q3 in Query:
    if q1 == "1":
        i = int(q2) - 1
        letter = abc[S[i]]
        segs[letter].update(i, False)
        letter = abc[q3]
        segs[letter].update(i, True)
        S[i] = q3
    else:
        ans = sum(seg.query(int(q2) - 1, int(q3)) for seg in segs)
        print(ans)



### FIXED CODE ###

def main():
    n = int(input())
    s = input()
    Q = int(input())
    t = [input().split() for _ in range(Q)]

    d = [0] * n + [1 << ord(c) - 97 for c in s]
    for i in range(n - 1, 0, -1):
        d[i] = d[i + i] | d[i - ~i]
    for q, a, b in t:
        i, s = int(a) + n - 1, 0
        if q < "2":
            d[i] = 1 << ord(b) - 97
            while i > 1:
                i //= 2
                d[i] = d[i + i] | d[i - ~i]
        else:
            j = int(b) + n
            while i < j:
                if i & 1:
                    s |= d[i]
                    i += 1
                if j & 1:
                    j -= 1
                    s |= d[j]
                i //= 2
                j //= 2
            print(bin(s).count("1"))


main()
### BUGGY CODE ###

# coding: utf-8
L,R = map(int, input().split())
mod_min=2020

for i in range(L,R):
    for j in range(i+1,R+1):
        tmp = (i*j)%2019
        if tmp<mod_min:
            mod_min=tmp
print(mod_min)

### FIXED CODE ###

# coding: utf-8
L,R = map(int, input().split())
mod_min=2020

if R-L>2018:
    mod_min=0
else:
    for i in range(L,R):
        for j in range(i+1,R+1):
            tmp = (i*j)%2019
            if tmp<mod_min:
                mod_min=tmp
print(mod_min)
### BUGGY CODE ###

from bisect import bisect_left

n = int(input())
lst = list(map(int,input().split()))
ans = 0
lst.sort()
for i in range(n):
    for j in range(i+1,n):
        b,c = lst[i],lst[j]
        posr = bisect_left(lst,b+c)
        posl = max(j+1,bisect_left(lst,abs(b-c)))
        ans += (posr - posl)
print(ans)

### FIXED CODE ###

from bisect import bisect_left
n = int(input())
lst = list(map(int,input().split()))
ans = 0

lst.sort()

for i in range(n):
    for j in range(i+1,n):
        b,c = lst[i],lst[j]
        posr = bisect_left(lst,b+c)
        posl = max(j+1,bisect_left(lst,abs(b-c)))
        ans += (posr - posl)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 9)

H,N=map(int,input().split())
L=[]
for i in range(N):
    T=[0,0,0]
    T[1],T[2]=map(int,input().split())
    T[0]=T[2]/T[1]
    L.append(T)
L=sorted(L)
n=1+H//L[0][1]
m=n*L[0][2]
L=sorted(L,key=lambda x: x[2],reverse=True)
def DP(MAX,minM,i,T,M):
    t=T
    m=M
    if(T>=MAX):
        return M
    if(m<minM):        
        tm=DP(MAX,minM,i,t+L[i][1],m+L[i][2])
        if(minM>tm):
            minM=tm
        if(len(L)-1 > i):
            tm=DP(MAX,minM,i+1,t,m)
            if(minM>tm):
                minM=tm
    return minM

tm=DP(H,m,0,0,0)

print(tm)



### FIXED CODE ###

H,N=map(int,input().split())
L=[]
m=0
for i in range(N):
    T=[0,0]
    T[0],T[1]=map(int,input().split())
    L.append(T)
    m=max(m,T[0])
L=sorted(L,reverse=True)
L.insert(0,[0,0])
m+=1
DP=[[10**10 for i in range(H+1+m)] for j in range(N+1)]
DP[0][0]=0

for i in range(1,N+1):
    t=0
    DP[i][0]=0
    for j in range(H+1):
        DP[i][j]=min(DP[i][j],DP[i-1][j])
        t=min(DP[i][j],DP[i-1][j])+L[i][1]
        DP[i][j+L[i][0]]=min(DP[i][j+L[i][0]],t)
    DP[i][H]=min(DP[i][H:-1])
print(min(DP[N][H:-1]))
### BUGGY CODE ###

a=input()
num=len(a)
mod_map={0:1}
moji_int=0
Sn=0
tens=[1]*(num+1)
for i in range(-1,-num-1,-1):
    tens[-i]=tens[-i-1]*10
    tmp=int(a[i])*(tens[-i-1]%2019)
    Sn=(Sn+tmp%2019)%2019
    mod=Sn
    if mod not in mod_map:
        mod_map[mod]=1
    else:
        mod_map[mod]+=1

res=0
for i in mod_map.values():
    res+=int(i*(i-1)/2)
print(res)


### FIXED CODE ###

a=reversed(input())
#num=len(a)
mod_list=[1]+[0]*2019
moji_int=0
Sn=0
tens=1
for i in a:
    tmp=int(i)*(tens)
    Sn=(Sn+tmp)%2019
    mod=Sn
    tens=tens*10%2019
    mod_list[mod]+=1
res=0
for i in mod_list:
    res+=int(i*(i-1)/2)
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,T=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]

def compare(x,y):
    if x==0:
        return (1<<31)+y
    else:
        return (y+1)/x

M.sort(key=lambda x:compare(x[0],x[1]))

k=N
for i in range(N):
    if M[i][0]==0:
        k=i
        break

#print(k)

DP=[[T+1]*(k+1) for i in range(30)]
DP[0][0]=0

def nexttime(x,a,b):
    return x+1+a*(x+1)+b

for i in range(1,30):
    for j in range(k+1):
        a,b=M[j-1]
        for l in range(j):
            nt=nexttime(DP[i-1][l],a,b)
            if nt<DP[i][j]:
                DP[i][j]=nt
ANS=0
for i in range(30):
    TIME=min(DP[i])
    if TIME>T:
        break
    SC=i
    for j in range(k,N):
        if TIME+M[j][1]+1<=T:
            TIME+=M[j][1]+1
            SC+=1
    ANS=max(ANS,SC)

print(ANS)

### FIXED CODE ###

import sys
input = sys.stdin.readline

N,T=map(int,input().split())
M=[list(map(int,input().split())) for i in range(N)]

def compare(x,y):
    if x==0:
        return (1<<31)+y
    else:
        return (y+1)/x

M.sort(key=lambda x:compare(x[0],x[1]))

k=N
for i in range(N):
    if M[i][0]==0:
        k=i
        break

#print(k)

DP=[[T+1]*(k+1) for i in range(30)]
for i in range(k+1):
    DP[0][i]=0

def nexttime(x,a,b):
    return x+1+a*(x+1)+b

for i in range(1,30):
    for j in range(1,k+1):
        nt=nexttime(DP[i-1][j-1],M[j-1][0],M[j-1][1])
        DP[i][j]=min(DP[i][j-1],nt)
ANS=0
for i in range(30):
    TIME=min(DP[i])
    if TIME>T:
        break
    SC=i
    for j in range(k,N):
        if TIME+M[j][1]+1<=T:
            TIME+=M[j][1]+1
            SC+=1
    ANS=max(ANS,SC)

print(ANS)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()

for i in range(q):
  l,r = map(int,input().split())
  print(s[l-1:r].count("AC"))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()

li = [0]*(n+1)
for i in range(1,n+1):
  if s[i-1:i+1] == "AC":
    li[i] = li[i-1] + 1
  else:
    li[i] = li[i-1]
for i in range(q):
  l,r = map(int,input().split())
  print(li[r-1]-li[l-1])
### BUGGY CODE ###

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

def gcd(a, b):
    while a % b:
        a, b = b, a % b
    return b

if len(a)==2:
    print(max(a))
else:
    for i in range(n-1):
        cnt.append(gcd(a[i],a[i+1]))
    cnt.append(gcd(a[0],a[n-1]))
    cnt2 = cnt
    while 1:
        tmp = max(cnt2)
        g = sum(x%tmp==0 for x in cnt)
        if g>=len(cnt)-2:
            print(tmp)
            break
        else:
            cnt2 = [i for i in cnt2 if i != 0]

### FIXED CODE ###

n = int(input())
a = list(map(int ,input().split()))
l = [a[0]]
r = [a[-1]]
def gcd(a, b):
    while a % b:
        a, b = b, a % b
    return b

for i in range(1,n-2):
        l.append(gcd(l[-1],a[i]))
for i in range(2,n-1)[::-1]:
        r.append(gcd(r[-1],a[i]))
r = r[::-1]
ans = []
for i in range(len(l)):
        ans.append(gcd(l[i],r[i]))
ans.append(gcd(l[-1],a[-2]))
ans.append(gcd(r[0],a[1]))

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

n = input()
 
S = [int(x) for x in raw_input().split()]
 
q = input()
 
T = [int(x) for x in raw_input().split()]
 
C = 0

left = 0
right = n

for key in T:
 while left<right:
  mid = (right - left)/2
  if key==S[mid]:
   C += 1
   break
  elif key<S[mid]:
   right = mid
  elif key>S[mid]:
   left = mid

print C

### FIXED CODE ###

n = input()
  
S = [int(x) for x in raw_input().split()]
  
q = input()
  
T = [int(x) for x in raw_input().split()]
  
C = 0

 
for key in T:
  left = 0
  right = n
  while left<right:
    mid = (right + left)/2
    if key==S[mid]:
      C += 1
      break
    elif key<S[mid]:
      right = mid
    elif key>S[mid]:
      left = mid+1
 

print C
### BUGGY CODE ###

import numpy as np

N = int(input())
P = np.array(input().split(' '), dtype = int)

counta = 0
for i in range(N):
    counta += np.all((P >= P[i])[:i+1])
print(counta)

### FIXED CODE ###

N = int(input())
# P = np.array(input().split(' '), dtype = int)
P = list(map(int, input().split(' ')))

p_min = P[0]
ans = 0
for p in P:
    if p <= p_min:
        p_min = p
        ans += 1
print(ans)
### BUGGY CODE ###

s = input()
n = int(input())
cnt = 0
for i in range(n):
    a = input()
    if a == "1":
        cnt +=1
    else:
        if a[2] == "1" and cnt%2 ==0:
            s = a[4] + s
        elif a[2] == "1" and cnt%2 ==1:
            s = s + a[4]
        elif a[2] == "2" and cnt%2 ==0:
            s = s + a[4]
        elif a[2] == "2" and cnt%2 ==1:
            s = a[4] + s

if cnt%2 == 1:
    print(s[::-1])
else:
    print(s)

### FIXED CODE ###

from collections import deque
s = input()
s = deque(s)
n = int(input())
cnt = False
for i in range(n):
  L = input()
  if len(L) == 1:
    cnt  ^=1 
  else:
    a,b,c = L.split()
    if cnt:
      if b == "1":
        s.append(c)
      else:
        s.appendleft(c)
    else:
      if b == "1":
        s.appendleft(c)
      else:
        s.append(c)
if cnt:
    s = reversed(s)
    print("".join(s))
else:
    print("".join(s))
### BUGGY CODE ###

from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
cnt = 0
cur = 0
while cur<N:
    x = X[cur][0]
    if X[cur][1]%A==0:
        n = X[cur][1]//A
    else:
        n = X[cur][1]//A+1
    ind = bisect_right(X,[x+2*D,10**10])
    imin = N
    for i in range(cur,ind):
        X[i][1] -= n*A
        if X[i][1]>0:
            imin = min(imin,i)
    cnt += n
    if imin<N:
        cur = imin
    else:
        flag = 0
        for i in range(ind,N):
            if X[i][1]>0:
                cur = i
                flag = 1
                break
        if flag==0:cur=N
print(cnt)    

### FIXED CODE ###

from bisect import bisect_right
N,D,A = map(int,input().split())
X = sorted([list(map(int,input().split())) for _ in range(N)],key=lambda x:x[0])
B = [0 for _ in range(N+1)]
cnt = 0
cur = 0
delta = 0
flag = 0
while cur<N:
    x = X[cur][0]
    h = X[cur][1]+delta
    if h%A==0:
        n = h//A
    else:
        n = h//A+1
    ind = bisect_right(X,[x+2*D,10**9+1])
    B[cur] += -n*A
    B[ind] += n*A
    cnt += n
    flag = 0
    for i in range(cur,N):
        delta += B[i]
        B[i] = 0
        if X[i][1]+delta>0:
            cur = i
            flag = 1
            break
    if flag==0:
        cur = N
print(cnt)
### BUGGY CODE ###

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

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


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

print(L[N - 1])

### FIXED CODE ###

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

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

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

	print(DP[N - 1])

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

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

n = int(input())
s = n - 1

ans = 0
for i in range(s+1):
    ans += i
print(ans)

### FIXED CODE ###

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

n = int(input())
s = n - 1

print(s*(s+1)//2)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
inf = 10**15
n,m = map(int, input().split())
edge = []
for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    edge.append((a,b,c))

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    update = False
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[b]<inf:
                if d[b]<d[a]+c:
                    d[b] = d[a]+c
                    update = True
            else:
                update = True
                d[b] = d[a] + c
    if not update:
        break

ans = d[n-1]
updated = [False for _ in range(n)]
for _ in range(n):
    update = False
    for i in range(m):
        a,b,c = edge[i]
        if d[a]<inf:
            if d[a]+c>d[b]:
                d[b] = d[a] + c
                update = True
                updated[b] = True
        if updated[a]:
            update = True
            updated[b] = True
    if not update:
        break

if updated[n-1]:
    print("inf")
else:
    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
inf = 10**50
n,m = map(int, input().split())

ea = []
eb = []
cost = []

for _ in range(m):
    a,b,c = map(int, input().split())
    a -= 1
    b -= 1
    ea.append(a)
    eb.append(b)
    cost.append(-c)

d = [inf for _ in range(n)]
d[0] = 0
for _ in range(n):
    update = False
    for i in range(m):
        a = ea[i]
        b = eb[i]
        c = cost[i]
        if d[a]!=inf and d[b]>d[a]+c:
            d[b] = d[a]+c
            update = True
    if not update:
        break

ans = d[n-1]
negative = [False for _ in range(n)]
for _ in range(n):
    update = False
    for i in range(m):
        a = ea[i]
        b = eb[i]
        c = cost[i]
        if d[a]!=inf and d[b]>d[a]+c:
            d[b] = d[a]+c
            if not negative[b]:
                update = True
            negative[b] = True
        if negative[a] and not negative[b]:
            negative[b] = True
            update = True
    if not update:
        break
# print(d)
if negative[n-1]:
    print("inf")
else:
    print(-ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
for v in A:
    ans = ans * v
if ans > 10 ** 18:
        ans = -1    
print(ans)       

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 1
if 0 in A:
    ans = 0
else:
    for v in A:
        ans = ans * v
        if ans > 10 ** 18:
            ans = -1
            break;
print(ans)
### BUGGY CODE ###

from collections import Counter
MOD = 10**9+7
n = int(input())
A = ['{:060b}'.format(a)[::-1] for a in map(int, input().split())]
A_d = []
for col in zip(*A):
    c = Counter(map(int, col))
    A_d.append(c[0]*c[1])

ans = 0
for d in range(60):
    ans = ans + A_d[d]*pow(2, d, MOD) % MOD
print(ans % MOD)


### FIXED CODE ###

MOD = 10**9+7
n = int(input())
A = ['{:060b}'.format(a)[::-1] for a in map(int, input().split())]
A_d = []
for col in zip(*A):
    zero_cnt = col.count('0')
    A_d.append(zero_cnt*(n-zero_cnt))

ans = 0
for d in range(60):
    ans = ans + A_d[d]*pow(2, d, MOD) % MOD
print(ans % MOD)
### BUGGY CODE ###

from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
inf=10**10
dist=[[inf if c=='.' else 0 for c in r] for r in a]
dq=deque()
for i in range(h):
    for j in range(w):
        if dist[i][j]==0:
            dq.append([i,j])
diff=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
while(dq):
    y,x=dq.popleft()
    for dy,dx in diff:
        y2=y+dy
        x2=x+dx
        if 0<=y2<h and 0<=x2<w and dist[y2][x2]>dist[y][x]+1:
            dq.append([y2,x2])
            dist[y2][x2]=dist[y][x]+1
            ans=max(ans,dist[y2][x2])
print(ans)

### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
a=[input() for _ in range(h)]
inf=10**10
dist=[[inf if c=='.' else 0 for c in r] for r in a]
dq=deque()
for i in range(h):
    for j in range(w):
        if dist[i][j]==0:
            dq.append([i,j])
diff=[[1,0],[0,1],[-1,0],[0,-1]]
ans=0
while(dq):
    y,x=dq.popleft()
    for dy,dx in diff:
        y2=y+dy
        x2=x+dx
        if 0<=y2<h and 0<=x2<w and dist[y2][x2]>dist[y][x]+1:
            dq.append([y2,x2])
            dist[y2][x2]=dist[y][x]+1
            ans=max(ans,dist[y2][x2])
print(ans)
### BUGGY CODE ###

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

ans=99999999999

def dfs(i,j,right,down,obst):
#    print(i,j,right,down,obst)
    global ans
    obst_ij=obst
    if(s[i][j]=='#'):
        obst_ij+=1

    if(right+down>=h+w-2):
        ans=min(ans,obst_ij)

    if(right<w-1):
        #→
        dfs(i,j+1,right+1,down,obst_ij)

    if(down<h-1):
        #↓
        dfs(i+1,j,right,down+1,obst_ij)

dfs(0,0,0,0,0)
print(ans)

### FIXED CODE ###

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

dp=[[99999999 for i in range(w)] for i in range(h)]


if(s[0][0]=='#'):
    dp[0][0]=1
else:
    dp[0][0]=0

for i in range(h):
    for j in range(w):

        if(s[i][j-1] != s[i][j]):
            left = dp[i][j-1]+1
        else:
            left = dp[i][j-1]

        if(s[i-1][j] != s[i][j]):
            top = dp[i-1][j]+1
        else:
            top = dp[i-1][j]

        dp[i][j] = min(dp[i][j],left,top)

print((dp[h-1][w-1]+1)//2)
### BUGGY CODE ###

import sys
import math

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

array1 = list()
for b in B:
    count = 0
    for c in C:
        if b < c:
            count += 1
    array1.append(count)
ans = 0
for i in range(N):
    count = 0
    for a in A:
        if B[i] > a:
            count += 1
    ans += count * array1[i]
print(ans)

### FIXED CODE ###

import sys
import math

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

A.sort()
B.sort()
C.sort()

array1 = list()
count = 0
f = 0
for j in range(N):
    for i in range(f, N):
        if B[N-1-j] < C[N-1-i]:
            count += 1
            if i == N-1:
                f = N
        else:
            f = i
            break
    array1.append(count)
ans = 0
f = 0
count = 0
for i in range(N):
    for j in range(f, N):
        if B[i] > A[j]:
            count += 1
            if j == N-1:
                f = N
        else:
            f = j
            break
    ans += count * array1[N-1-i]
print(ans)
### BUGGY CODE ###

N, M = map(int, input().split())  # N段の階段, 壊れている床の個数M

# A = []

# flag = True
# for i in range(M):
#     A.append(int(input()))
#     if len(A) > 1:
#         if A[i] == A[i-1]+1:
#             print(0)
#             flag = False
#             break

# if flag:

A = [int(input()) for _ in range(M)]

dp = [0, 1]

for i in range(1, N+1):
    if i in A:
        dp.append(0)
    else:
        dp.append((dp[-2] + dp[-1]) % 1000000007)

print(dp[-1] % 1000000007)


### FIXED CODE ###

N, M = map(int, input().split())  # N段の階段, 壊れている床の個数M

A = set([int(input()) for _ in range(M)])

dp = [0, 1]

for i in range(1, N+1):
    if i in A:
        dp.append(0)
    else:
        dp.append((dp[-2] + dp[-1]) % 1000000007)

print(dp[-1] % 1000000007)