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

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    def prime(n):
        if n<=1: return False
        A = [i for i in range(2, n+1)]
        P = []
        lim = n**.5
        while True:
            prime = A[0]
            if prime > lim: break
            P.append(prime)
            i = 0
            while i < len(A):
                if A[i] % prime == 0:
                    A.pop(i)
                    continue
                i += 1
        for a in A:
            P.append(a)
        return P

    C=5+10**5
    S=[0]*C
    T=[0]*C
    for p in prime(C):
        S[p]=1
    for i in range(C):
        if i%2==0: continue
        if S[i]==1 and S[(i+1)//2]==1:
            T[i]=1
    # cumsum
    for i in range(C-1):
        T[i+1]+=T[i]
    # input
    q=int(input())
    for _ in range(q):
        l,r=map(int,input().split())
        print(T[r]-T[l-1])
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    def prime(n):
        if n<=1: return False
        A = [i for i in range(2, n+1)]
        P = []
        lim = n**.5
        while True:
            prime = A[0]
            if prime > lim: break
            P.append(prime)
            i = 0
            while i < len(A):
                if A[i] % prime == 0:
                    A.pop(i)
                    continue
                i += 1
        for a in A:
            P.append(a)
        return P

    C=5+10**5
    S=[0]*C
    T=[0]*C
    for p in prime(C):
        S[p]=1
    for i in range(C):
        if i%2==0: continue
        if S[i]==1 and S[(i+1)//2]==1:
            T[i]=1
    # cumsum
    for i in range(C-1):
        T[i+1]+=T[i]
    # input
    q=int(input())
    for _ in range(q):
        l,r=map(int,input().split())
        print(T[r]-T[l-1])
resolve()
### BUGGY CODE ###

import math
def combinations_count(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
N=int(input())
s=[]
cnt=0
for i in range(N):
    s.append(input())
s=list(map(sorted,s))
def get_duplicate_list(seq):
    seen = []
    return [x for x in seq if not seen.append(x) and seen.count(x) == 2]
s2=get_duplicate_list(s)
for j in s2:
    cnt+=combinations_count(s.count(j),2)
print(cnt)

### FIXED CODE ###

N=int(input())
dic={}
cnt=0
for i in range(N):
    temp=' '.join(sorted(input()))
    if temp in dic:
        dic[temp]+=1
    else:
        dic[temp]=1
for k,v in dic.items():
    cnt+=v*(v-1)//2
print(cnt)
### BUGGY CODE ###

nk = list(map(int,input().split()))
h = list(map(int,input().split()))
n,k = nk[0], nk[1] #5,3
DP = [0]
for i in range(1, n):#0~3 -> 1~4
  act = float("inf")
  for k_ in range(1, k+1):#0~2 -> 1~3
    if i-k_ < 0 : continue
    act = min(DP[-k_] + abs(h[i-k_]-h[i]), act)#
  DP+= [act]#[0,20,]
print(DP[-1])

### FIXED CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))
 
DP = [0]
for i in range(N-1):
    act = float("inf")
    for k in range(K):
        if i-k < 0 : continue
        act = min(DP[-1-k] + abs(h[i-k]-h[i+1]) , act)
    DP += [act]
 
print(DP[-1])
### BUGGY CODE ###

s = input()
k = int(input())

ans = ''

for i in range(len(s)-1):
    a = 123-ord(s[i])
    if a==26:
        ans += s[i]
    elif a<k:
        ans += 'a'
        k-=a
    else:
        ans += s[i]

ans += chr((ord(s[-1])-97+k)%26+97)

print(ans)

### FIXED CODE ###

s = input()
k = int(input())

ans = ''

for i in range(len(s)-1):
    a = 123-ord(s[i])
    if a==26:
        ans += s[i]
    elif a<=k:
        ans += 'a'
        k-=a
    else:
        ans += s[i]

ans += chr((ord(s[-1])+k%26-97)%26+97)

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

from collections import defaultdict as dd
import sys
sys.setrecursionlimit(6000)
N, M, P = map(int, input().split())
edges = []
revedgedict = dd(dict)
for _ in range(M):
  f, t, c = map(int, input().split())
  edges.append((f-1, t-1, -(c-P)))
  revedgedict[t-1][f-1] = 1

# Nに到達できない頂点を削除
visited = [False] * N
def dfs(f):
  visited[f] = True
  for t in revedgedict[f].keys():
    if not visited[t]:
      dfs(t)
dfs(N-1)

# ベルマンフォード
INF = float('inf')
d = [float('inf')] * N
d[0] = 0
for i in range(N):
  updated = False
  for f, t, c in edges:
    if d[f] != INF and visited[t] and d[t] > d[f] + c:
      d[t] = d[f] + c
      updated = True
  if not updated:
    break
else:
  print(-1)
  exit()
print(max(-d[-1], 0))

### FIXED CODE ###

from collections import defaultdict as dd
import sys
sys.setrecursionlimit(6000)
N, M, P = map(int, input().split())
edges = []
revedgedict = dd(dict)
for _ in range(M):
  f, t, c = map(int, input().split())
  edges.append((f-1, t-1, -(c-P)))
  revedgedict[t-1][f-1] = 1

# Nに到達できない頂点を削除
visited = [False] * N
def dfs(f):
  visited[f] = True
  for t in revedgedict[f].keys():
    if not visited[t]:
      dfs(t)
dfs(N-1)

# ベルマンフォード
INF = float('inf')
d = [float('inf')] * N
d[0] = 0
for i in range(N):
  updated = False
  for f, t, c in edges:
    if d[f] != INF and visited[t] and d[t] > d[f] + c:
      d[t] = d[f] + c
      updated = True
  if not updated:
    break
else:
  print(-1)
  exit()
print(max(-d[-1], 0))
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding:utf-8 -*-


obj = input().strip().split(' ')
N, M = map(int, obj)

obj = input().strip().split(' ')
A_list = map(int, obj)

val_list = sorted(A_list, reverse=True)


for _ in range(M):
    val_list[0] = val_list[0] // 2
    i = 0
    while i < N - 1 and val_list[i] < val_list[i + 1]:
        tmp = val_list[i]
        val_list[i] = val_list[i + 1]
        val_list[i + 1] = tmp
        i += 1

print(sum(val_list))


### FIXED CODE ###

from heapq import heappush, heappop, heapify

obj = input().strip().split(' ')
N, M = map(int, obj)

obj = input().strip().split(' ')
val_list = [-1 * item for item in list(map(int, obj))]

heapify(val_list)

for _ in range(M):
    val = (-1) * ((heappop(val_list) * (-1)) // 2)
    heappush(val_list, val)

print(-1 * sum(val_list))
### BUGGY CODE ###

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

for i in range(a,b+1):
  if abs(a-i)<k or abs(b-i)<k:
    print(i)
    
 

### FIXED CODE ###

a,b,k = [int(i) for i in input().split()]
jougen = a+k-1
kagen = b-k+1

if jougen>=kagen:
  for i in range(a,b+1):
    print(i)
    
else:
  for i in range(a,jougen+1):
    print(i)
  for i in range(kagen,b+1):
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from itertools import chain
H,W = (int(x) for x in input().split())
S = [list(input()) for _ in range(H)]
mem = [[[0,0] for _ in range(W)] for _ in range(H)]
ans = [[0] * W for _ in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            if mem[i][j][0]:
                h = mem[i][j][0]
            else:
                stopped = False
                for k in range(W-j-1):
                    if S[i][j+k+1] == '#':
                        for l in range(k+1):
                            mem[i][j+l][0] = k+1
                        stopped = True
                        break
                if stopped == False:
                    for l in range(W-j):
                        mem[i][j+l][0] = W-j
                h = mem[i][j][0]
            if mem[i][j][1]:
                v = mem[i][j][1]
            else:
                stopped = False
                for k in range(H-i-1):
                    if S[i+k+1][j] == '#':
                        for l in range(k+1):
                            mem[i+l][j][1] = k+1
                        stopped = True
                        break
                if stopped == False:
                    for l in range(H-i):
                        mem[i+l][j][1] = H-i
                v = mem[i][j][1]
            ans[i][j] = h + v - 1
print(max(chain(*ans)))

### FIXED CODE ###

import sys
input = sys.stdin.readline

H,W = (int(x) for x in input().split())
S = [list(input()) for _ in range(H)]
memh = [[0] * W for _ in range(H)]
memv = [[0] * W for _ in range(H)]
ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '.':
            h = memh[i][j]
            if h == 0:
                stopped = False
                for k in range(W-j-1):
                    if S[i][j+k+1] == '#':
                        for l in range(k+1):
                            memh[i][j+l] = k+1
                        stopped = True
                        break
                if stopped == False:
                    for l in range(W-j):
                        memh[i][j+l] = W-j
                h = memh[i][j]
            v = memv[i][j]
            if v == 0:
                stopped = False
                for k in range(H-i-1):
                    if S[i+k+1][j] == '#':
                        for l in range(k+1):
                            memv[i+l][j] = k+1
                        stopped = True
                        break
                if stopped == False:
                    for l in range(H-i):
                        memv[i+l][j] = H-i
                v = memv[i][j]
            ans = max(ans,h+v-1)
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())

a = int(M/N)

for i in range(a,0,-1):
    if M % i == 0:
        c = i
        break

print(c)



### FIXED CODE ###

import math

N,M = map(int,input().split())

a = int(M/N)
q = int(math.sqrt(M))

m = 0
for i in range(1,q+1):
    if M % i == 0:
        if i <= a:
            m = max(m,i)
        b = int(M / i)
        if b <= a:
            m = max(m,b)

print(m)
### BUGGY CODE ###

class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, q = map(int, input().split())
c = list(map(int, input().split()))

rli = []
for i in range(q):
    l, r = map(int, input().split())
    l, r = l, r
    rli.append((r, l, i))
rli.sort()

last = [-1] * (n + 1)

bit = Bit(n)
ans = [0] * q
cur = 1
for r, l, i in rli:
    for j in range(cur, r + 1):
        if last[c[j - 1]] != -1:
            bit.add(last[c[j - 1]], -1)
        last[c[j - 1]] = j
        bit.add(j, 1)
    cur = r + 1
    ans[i] = bit.sum(r) - bit.sum(l - 1)
for i in ans:
    print(i)


### FIXED CODE ###

import sys
input = sys.stdin.readline


class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0 for _ in range(n + 2)]
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & -i


n, q = map(int, input().split())
c = list(map(int, input().split()))

rli = []
for i in range(q):
    l, r = map(int, input().split())
    rli.append((r, l, i))
rli.sort(key=lambda x: x[0])

last = [-1 for _ in range(n + 1)]

bit = Bit(n)
ans = [-1 for _ in range(q)]
cur = 1
for r, l, i in rli:
    for j in range(cur, r + 1):
        if last[c[j - 1]] != -1:
            bit.add(last[c[j - 1]], -1)
        last[c[j - 1]] = j
        bit.add(j, 1)
    cur = r + 1
    ans[i] = bit.sum(r) - bit.sum(l - 1)
print(*ans, sep="\n")
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
aa=0
for i in range(n):
    for j in range(n):
        if i<j:
            aa+=a[i]*a[j]
            aa%=1000000007
print(aa)

### FIXED CODE ###

input()
a = list(map(int, input().split()))
c = 1000000007
print(((sum(a)**2-sum(map(lambda x: x**2, a)))//2)%c)
### BUGGY CODE ###

def bknap(W, wt, val, n): 
 K = [[0 for x in range(W + 1)] for x in range(n + 1)] 
 for i in range(n + 1): 
  for w in range(W + 1): 
   if i == 0 or w == 0: 
    K[i][w] = 0
   elif wt[i-1] <= w: 
    K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]],  K[i-1][w]) 
   else: 
    K[i][w] = K[i-1][w] 
 return K[n][W] 
n,w=map(int,input().split())
wei=[]
val=[]
for i in range(n):
 w1,v1=map(int,input().split())
 wei.append(w1)
 val.append(v1)
print(bknap(w,wei,val,n))

  


### FIXED CODE ###

import sys
input=sys.stdin.readline
def fun(n,w):
 cos=[0]*(w+1)
 for i in range(n):
  w1,v1=map(int,input().split())
  for j in range(w,w1-1,-1):
   f=cos[j-w1]+v1
   if(cos[j]<f):
    cos[j]=f
 print(cos[-1])
n,w=map(int,input().split())
fun(n,w)
### BUGGY CODE ###

import sys
import fractions
input = sys.stdin.readline


mod = 10 ** 9 + 7
N = int(input().strip())
A = list(map(int, input().strip().split(" ")))

lcm = 1
for a in A:
    lcm = a // fractions.gcd(a, lcm) * lcm

ans = 0
for a in A:
    ans += lcm // a
    ans %= mod

print(ans)

### FIXED CODE ###

import sys
import fractions
input = sys.stdin.readline


mod = 10 ** 9 + 7
N = int(input().strip())
A = list(map(int, input().strip().split(" ")))

lcm = 1
for a in A:
    lcm = a // fractions.gcd(a, lcm) * lcm

ans = 0
for a in A:
    ans += lcm // a

print(ans % mod)
### BUGGY CODE ###

n = int(input())
a = [int(i) for i in input().split()]
sa  = sorted(a)

q = int(input())
b = []
for _ in range(q):
    b.append([int(i) for i in input().split()])


for i in range(q):
    idx = -1
    seta = set(sa)
    if b[i][0] in seta:
         idx = sa.index(b[i][0])
    # print(idx)

    if idx != -1:
        while (True):
            if idx < n and sa[idx] == b[i][0]:
                sa[idx] = b[i][1]
                idx += 1
            else:
                break
    # print(sa)
    print(sum(sa))



### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]


q = int(input())
b = []
for _ in range(q):
    b.append([int(i) for i in input().split()])

al = {}
suma = sum(a)

for i in a:
    if i not in al:
        al[i] = 1
    else:
        al[i] += 1

for i in range(q):
    if b[i][0] in al:
        suma += (b[i][1] - b[i][0]) * al[b[i][0]]
        
        if b[i][1] in al:
            
            al[b[i][1]] += al[b[i][0]]
            al[b[i][0]] = 0
        else:
            al[b[i][1]] = al[b[i][0]]
            al[b[i][0]] = 0
    print(suma)
### BUGGY CODE ###

N=int(input())
X=[]
places=[]
for i in range(N):
    inp=input()
    X.append(inp)
    places.append(X.count(inp))
ans=[]
mode=max(places)
for j in range(N):
    if places[j]==mode:
        ans.append(X[j])
ans.sort()
for a in ans:
    print(a)


### FIXED CODE ###

import collections
N=int(input())
X=[input().strip() for i in range(N)]

cc=collections.Counter(X)
maximum=max(cc.values())

ans=sorted([ss[0] for ss in cc.items() if ss[1]==maximum])
print(*ans)
### BUGGY CODE ###

n = int(input())
power = 1

for i in range(n):
    power *= (i + 1)

ans = power % (pow(10, 9) + 7)
print(ans)

### FIXED CODE ###

import math

n = int(input())
ans = math.factorial(n) % (pow(10, 9) + 7)
print(ans)
### BUGGY CODE ###

import collections
N, Q = map(int, input().split())
C = list(map(int, input().split()))

D_origin = {C[i]:0 for i in range(N)}

D = dict(D_origin)
E = [{0:0}] * N
for i in range(N):
    D[C[i]] += 1
    D_other = dict(D)
    E[i] = D_other

ANS = []
for i in range(Q):
    l, r = map(int, input().split())
    if l == 1:
        E_dif = dict(E[r - 1].items() - D_origin.items())
    else:
        E_dif = dict(E[r - 1].items() - E[l - 2].items())
    ans = len(E_dif.values())
    ANS.append(ans)
for i in range(Q):
    print(ANS[i])

### FIXED CODE ###

from collections import defaultdict
import sys
def read():
    return sys.stdin.readline().rstrip()
def main():
    N, Q = map(int, read().split())
    C = list(map(int, read().split()))
    E = defaultdict(list)

    D = [-1] * (N + 1)
    for i in range(N):
        D_i = D[C[i]]
        if D_i != -1:
            E[D_i].append((D_i, i))
        D[C[i]] = i

    F = defaultdict(list)
    for i in range(Q):
        l, r = map(int, input().split())
        F[l-1].append((r - 1, i))



    # Binary Indexed Tree (Fenwick Tree)
    class BIT:
        def __init__(self, n):
            self.n = n
            self.data = [0] * (n + 1)
            self.el = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.data[i]
                i -= i & -i
            return s

        def add(self, i, x):
            # assert i > 0
            self.el[i] += x
            while i <= self.n:
                self.data[i] += x
                i += i & -i

        def get(self, i, j=None):
            if j is None:
                return self.el[i]
            return self.sum(j) - self.sum(i)

    ANS = [0] * Q
    d = BIT(N)
    for x in range(N - 1, -1, -1):
        for e in E[x]:
            d.add(e[1], 1)
        for f in F[x]:
            ANS[f[1]] = f[0] - x + 1 - d.sum(f[0])

    for i in range(Q):
        print(ANS[i])

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

s = str(input())
q = int(input())
g = 0
for i in range(q):
  query = input()
  if (query == "1"):
    g = 1-g
  else:
    queries = query.split()
    f = int(queries[1])-1
    c = queries[2]
    if (g == f):
      s = "".join([c,s])
    else:
      s = "".join([s,c])
if (g == 1):
  s = "".join(list(s)[::-1])
print(s)


### FIXED CODE ###

s = str(input())
q = int(input())
g = 0
A = ""
B = ""
for i in range(q):
  query = input()
  if (query == "1"):
    g = 1-g
  else:
    queries = query.split()
    f = int(queries[1])-1
    c = queries[2]
    if (g == f):
      B = "".join([B,c])
    else:
      A = "".join([A,c])
s = "".join(["".join(list(B)[::-1]),s,A])
if (g == 1):
  s = "".join(list(s)[::-1])
print(s)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)

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

g = [[] for i in range(n+1)]

for i in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)
    
check = [0] * (n+1)
count = [0] * (n+1)

for i in range(q):
    p,x = map(int,input().split())
    count[p] += x
    
def dfs(v):
  for u in g[v]:
    if check[u]==1:
      continue
    check[u]=1
    count[u]+=count[v]
    dfs(u)
 

check[1] = 1
dfs(1)

print(*count[1:])

### FIXED CODE ###

import collections

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

g = [[] for i in range(n+1)]

for i in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)

count = [0] * (n+1)
check = [0] * (n+1)

for i in range(q):
    p,x = map(int,input().split())
    count[p] += x

q = collections.deque()  
q.append(1)

while q:
    v = q.pop()
    check[v] = 1
    for u in g[v]:
        if check[u] == 1:
            continue
        count[u] += count[v]
        q.append(u)
        
print(*count[1:])
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
for i in range(k):
    if a==[]:
        break
    a.remove(max(a))
print(sum(a))

### FIXED CODE ###

n,k=map(int,input().split())
a=sorted(list(map(int,input().split())),reverse=True)
if k>=len(a):
    print(0)
else:
    print(sum(a[k:]))
### BUGGY CODE ###

import sys
import itertools

N,K=map(int, sys.stdin.readline().split())
X=[]
Y=[]
XY=[]

for _ in range(N):
	x,y=map(int, sys.stdin.readline().split())
	X.append(x)
	Y.append(y)
	XY.append( (x,y) )
X.sort()
Y.sort()

L=list( itertools.product(X,Y ) )

ans=float("inf")

for x1,y1 in L:
	for x2,y2 in L:
		cnt=0
		for x, y in XY:
			if x1<=x<=x2 and y1<=y<=y2:
				cnt+=1
	
		menseki=abs(x1-x2)*abs(y1-y2)
		if K<=cnt:
			ans=min(ans, menseki)

print ans

### FIXED CODE ###

import itertools

N,K=list(map(int,raw_input().split()))
x=[]
y=[]
pts=[]
for i in range(N):
	a1,a2=map(int,raw_input().split())
	x.append(a1)
	y.append(a2)
	pts.append([a1,a2])

#print "# x,y"
x.sort()
y.sort()
#print x
#print y

#print "# pts"
#print pts
pts.sort(key=lambda x:x[0])
#print pts

ans=10**20


for y1 in y:
	for y2 in y:
		if y1>=y2:
			continue
		for x1 in x:
			cnt=0
			for p in pts:
				if p[0]>=x1 and p[1]>=y1 and p[1]<=y2:
					#print p[0],p[1],x1,y1,y2
					cnt+=1
					if cnt==K:
						x2=p[0]
						#print x1,y1,x2,y2,cnt,abs(x2-x1)*abs(y2-y1)
						ans=min(ans,abs(x2-x1)*abs(y2-y1))
						break

print ans
### BUGGY CODE ###

from collections import deque

s = input()
q = int(input())
query = [input().split() for i in range(q)]

d = deque(['S'])

#d = ['S']

rev = 0

for i in range(q):
    if query[i][0] == '2':
        if query[i][1] == '1':
            d.appendleft(query[i][2])
        else:
            d.append(query[i][2])
    else:
        d.reverse()
        rev += 1

ans = []

if rev % 2 == 1:
    s = ''.join(list(reversed(s)))


for i in range(len(d)):
    if d[i] == 'S':
        ans.append(s)
    else:
        ans.append(d[i])

print(*ans,sep='')

### FIXED CODE ###

from collections import deque

s = input()
q = int(input())
query = [input().split() for i in range(q)]

d = deque(['S'])

#d = ['S']

rev = False

for i in range(q):
    if query[i][0] == '1':
        rev = not rev
        continue
    
    if not rev:
        if query[i][0] == '2':
            if query[i][1] == '1':
                d.appendleft(query[i][2])
            else:
                d.append(query[i][2])
    else:
        if query[i][0] == '2':
            if query[i][1] == '1':
                d.append(query[i][2])
            else:
                d.appendleft(query[i][2])

#ans = deque()
if rev:
    #d = ''.join(list(reversed(d)))
    s = s[::-1]



while len(d):
    if rev:
        tmp = d.pop()
    else:
        tmp = d.popleft()
    if tmp == 'S':
        #ans.append(s)
        print(s,end='')
    else:
        print(tmp,end='')
        #ans.append(tmp)

#print(*ans,sep='')
### BUGGY CODE ###

from collections import deque

h, w = map(int, input().split())

move = (-w, -1, 1, w)
todo = deque([])
done = [1000 for _ in range(w * h)]
for i in range(h):
    s = input()
    for j, k in enumerate(s):
        if k == "#":
            todo.append(j + i * w)
            done[j + i * w] = 0

while todo:
    n = todo.popleft()
    d = done[n]
    for dn in move:
        if n % w == 0 and dn == -1:
            pass
        elif n % w == w - 1 and dn == 1:
            pass
        elif n < w and dn == -w:
            pass
        elif n >= w * h - w and dn == w:
            pass
        elif done[n + dn] <= d + 1:
            pass
        else:
            todo.append(n + dn)
            done[n + dn] = d + 1

print(max(done))

### FIXED CODE ###

import numpy as np

h, w = map(int, input().split())
grid = (np.array([list(input())
                  for _ in range(h)]) == "#")
cost = np.full((h, w), 10 ** 9, dtype=np.int64)
cost[grid[:, :]] = 0

for i in range(1, h):
    cost[i] = np.minimum(cost[i], cost[i - 1] + 1)

for i in range(h - 1)[::-1]:
    cost[i] = np.minimum(cost[i], cost[i + 1] + 1)

for i in range(1, w):
    cost[:, i] = np.minimum(cost[:, i], cost[:, i - 1] + 1)

for i in range(w - 1)[::-1]:
    cost[:, i] = np.minimum(cost[:, i], cost[:, i + 1] + 1)

print(np.max(cost))
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
mod = 10**9+7
rng = 10100
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
for i in range(1,rng):
  finv.append(pow(fctr[i],mod-2,mod))
def cmb(n,k):
  if n<0 or k<0:
    return 0
  else:
    return fctr[n]*finv[n-k]*finv[k]
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
ans = 0
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    for t in range(min(n-j,x)+1):
      dp[i][j+t] = (dp[i][j+t]+dp[i-1][j]*cmb(n-j,t)*cmb(n-t,x-t))%mod
print(dp[k][n])

### FIXED CODE ###

n,k = map(int,input().split())
a = tuple(map(int,input().split()))
mod = 10**9+7
rng = 1001
fctr = [1]
finv = [1]
for i in range(1,rng):
  fctr.append(fctr[-1]*i%mod)
  finv.append(pow(fctr[i],mod-2,mod))
dp = [[0 for i in range(n+1)] for j in range(k+1)]
dp[0][0] = 1
for i in range(1,k+1):
  x = a[i-1]
  for j in range(n+1):
    if dp[i-1][j] == 0:
      continue
    y = dp[i-1][j]*fctr[n-j]*finv[n-x]%mod
    for t in range(min(n-j,x)+1):
      dp[i][j+t]=(dp[i][j+t]+y*fctr[n-t]*finv[n-j-t]*finv[t]*finv[x-t])%mod
print(dp[k][n])