Harryxun/stf_run huggingface dataset:
N, M = list(map(int, input().split()))

class mod_pack:

    def __init__(self, MOD, MAX):
        self.MOD = MOD
        self.MAX = MAX
        self.fac, self.ifac = [1]*(MAX+1), [1]*(MAX+1)
        for i in range(1, MAX+1):
            self.fac[i] = self.fac[i-1]*i % MOD
            self.ifac[i] = self.ifac[i-1] * self.mpow(i, MOD-2) % MOD
    
    def mpow(self, x, n):
        ans = 1
        while n!=0:
            if n&1: ans = ans*x % self.MOD
            x = x*x % self.MOD
            n = n >> 1
        return ans

    def mcomb(self, m, n):
        if (m==0 and n==0): return 1
        return (self.ifac[m-n] * self.ifac[n] % self.MOD) * self.fac[m] % self.MOD

    def mperm(self, m, n):
        if (m < n): return 0
        return self.ifac[m-n] * self.fac[m] % MOD
    

mp = mod_pack(10**9+7, M)

tot = mp.mperm(M, N)
ans = 0
for k in range(1, N+1):
#    print(k, mp.mcomb(N, k), mp.mperm(M-k, N-k))
    ans = (ans + (-1)**(k-1) * mp.mcomb(N, k) * mp.mperm(M-k, N-k)) % MOD


print((tot * (tot - ans))%MOD)



### FIXED CODE ###

N, M = list(map(int, input().split()))
MOD = 10 ** 9 + 7

class mod_pack:

    def __init__(self, MOD, MAX):
        self.MOD = MOD
        self.MAX = MAX
        self.fac, self.ifac = [1]*(MAX+1), [1]*(MAX+1)
        for i in range(1, MAX+1):
            self.fac[i] = self.fac[i-1]*i % MOD
            self.ifac[i] = self.ifac[i-1] * self.mpow(i, MOD-2) % MOD
    
    def mpow(self, x, n):
        ans = 1
        while n!=0:
            if n&1: ans = ans*x % self.MOD
            x = x*x % self.MOD
            n = n >> 1
        return ans

    def mcomb(self, m, n):
        if (m==0 and n==0): return 1
        return (self.ifac[m-n] * self.ifac[n] % self.MOD) * self.fac[m] % self.MOD

    def mperm(self, m, n):
        if (m < n): return 0
        return self.ifac[m-n] * self.fac[m] % MOD
    

mp = mod_pack(10**9+7, M)

tot = mp.mperm(M, N)
ans = 0
for k in range(1, N+1):
#    print(k, mp.mcomb(N, k), mp.mperm(M-k, N-k))
    ans = (ans + (-1)**(k-1) * mp.mcomb(N, k) * mp.mperm(M-k, N-k)) % MOD


print((tot * (tot - ans))%MOD)
import sys
input = sys.stdin.readline
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except SyntaxError:
                flag = True
                return 0




m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)
"""
if N == 9999:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
dfs(neigh,nn)
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(1000000)
N = int(input())


node = [0 for i in range(N)]
neigh = [[] for j in range(N)]
ans = [0 for i in range(N)]
visited = [0 for i in range(N)]
k = 1

for i in range(N-1):
    ai,bi = map(int,input().split())
    node[ai-1] += 1
    node[bi-1] += 1
    neigh[ai-1].append(bi-1)
    neigh[bi-1].append(ai-1)
c = list(map(int,input().split()))
c.sort(reverse=True)
flag = False
def dfs(neighbor,start):
    global flag
    global k
    if sum(visited) == N:
        return 0

    for i in neighbor[start]:
        
        if visited[i] == 0:
            ans[i] = c[k]
            k += 1
            visited[i] = 1
            try:
                dfs(neighbor,i)
            except RuntimeError:
                flag = True
                return 0




m = max(node)
nn = node.index(m)
#nn = [node[i] for i in range(N) if node[i] == m][0]
visited[nn] = 1
ans[nn] = max(c)

dfs(neigh,nn)
"""
if flag:
    print(100)
    print(' '.join([str(i) for i in range(N)]))
    exit()
"""
ans2 = ' '.join([str(ans[i]) for i in range(N)])


print(sum(c)-max(c))
print(ans2)
import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    ab[a].append(-b)
h = []
s=0
for i in range(m,-1,-1):
    for v in ab[i]:
        heapq.heappush(h,v)
    if len(h)!=0:
        s-=heapq.heappop(h)
print(s)

### FIXED CODE ###

import heapq
n,m=map(int,input().split())
ab=[]
for i in range(m+1):
    ab.append([])
for i in range(n):
    a,b=map(int,input().split())
    if a<=m:
        ab[a].append(b)
h = []
s=0
for i in range(1,m+1):
    for v in ab[i]:
        heapq.heappush(h,-1*v)
    if len(h)>0:
        s+=-1*heapq.heappop(h)
print(s)
import numpy as np

n, k = map(int, input().split())
a = tuple(map(int, input().split()))
i = 1
prev = np.prod(a[:k])

while i+k <= n:
  tmp = np.prod(a[i:i+k])
  if tmp > prev:
    print('Yes')
  else:
    print('No')
  prev = tmp
  i += 1


### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
ans = [0]*(n-k)
for i in range(k, n):
  ans[i-k] = (a[i]>a[i-k])
for i in range(0, n-k):
  print('Yes' if ans[i] else 'No')
n = int(input())
a = list(map(int, input().split()))

sum_reverse = 0
for i in range(1,n):
	sum_reverse += 1/a[i]

print(1/sum_reverse)

### FIXED CODE ###

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

sum_reverse = 0
for i in range(n):
	sum_reverse += 1/float(a[i])

print(1/sum_reverse)
n = int(input())
A = list(map(int, input().split()))
num = 1
ans = 0
for i in range(n):
  if A[i] == num:
    num += 1
    ans += 1
if ans == 0:
  print("-1")
else:
print(n-ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
num = 1
ans = 0
for i in range(n):
  if A[i] == num:
    num += 1
    ans += 1
if ans == 0:
  print("-1")
else:
  print(n-ans)
import numpy as np
import heapq

INF=10**12
def daik(s,g,d,adj):
    used=np.array([])
    heap=[]
    table=np.array([INF for i in range(N)])
    table[s]=0
    heapq.heappush(heap,(table[s],s))
    used=np.append(used,s)
                
    while heap and not(g in used):
        q=heapq.heappop(heap)
        a=q[1]
        used=np.append(used,a)
        for i in adj[a]:
            if not(i in used):
                cost=d[a,i] 
                if cost!=INF:
                    table[i]=min(table[i],table[a]+cost)
                    heapq.heappush(heap,(table[i],i))
    return table[g]

N,M=map(int,input().split())
LRC=[]
for i in range(M):
    L,R,C=map(int,input().split())
    LRC.append([L-1,R-1,C])
LRC=np.array(LRC)
LRC=LRC[np.argsort(LRC[:,2])][::-1]

d=np.array([[INF for j in range(N)] for i in range(N)])
adj=[[] for i in range(N)]
for i in range(N-1):
    d[i+1,i]=0
    adj[i+1].append(i)
    adj[i].append(i+1)
for i in range(M):
    C=LRC[i,2]
    d[LRC[i,0],LRC[i,1]]=C
    d[LRC[i,1],LRC[i,0]]=C
    adj[LRC[i,0]].append(LRC[i,1])
    adj[LRC[i,1]].append(LRC[i,0])
adj=np.unique(adj,axis=1)
ans=daik(0,N-1,d,adj)
if ans==INF:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import numpy as np
import heapq

INF=10**15
N,M=map(int,input().split())
adj=[[] for i in range(N)]
for i in range(M):
    L,R,C=map(int,input().split())
    L-=1
    R-=1
    adj[L].append((R,C))
    adj[R].append((L,C))
for i in range(N-1):
    adj[i+1].append((i,0))
    
s=0
g=N-1
heap=[]
table=np.array([INF for i in range(N)])
table[s]=0
heapq.heappush(heap,(table[s],s))
                
while heap:
    q=heapq.heappop(heap)
    a=q[1]
    if q[0]>table[a]: continue
    for ne in adj[a]:
        p=ne[0]
        co=ne[1]
        if table[p]>table[a]+co:
            table[p]=table[a]+co
            heapq.heappush(heap,(table[p],p))
ans=table[g]
if ans==INF:
    print(-1)
else:
    print(ans)
n = int(input())
a = list(map(int, input().split()))

uv = [[] for _ in range(n)]
for _ in range(n-1):
    i, j = map(int, input().split())
    uv[i-1].append(j-1)
    uv[j-1].append(i-1)

# DFS
# 頂点iが未探索の時、ans[i] = -1
ans = [-1 for _ in range(n)]
ans[0] = 1
# dp[i] = 長さi+1のLISの最後尾の最小値
dp = [a[0]]
# history[(i, j)]のとき、変更前はdp[i] = j
# stackとして使用
history = []
# 頂点parents[i] = iの親
parents = [-1 for _ in range(n)]

todo = []
for i in uv[0]:
    todo.append(i)
    parents[i] = 0

while True:
    i = todo.pop(-1)
    
    # ans[i]を求める
    if dp[-1] < a[i]:
        dp.append(a[i])
        history.append(0)
    else:
        # dpの変更点を二分探索
        start = 0
        stop = len(dp) - 1
        flag = True
        while start < stop:
            center = (start + stop) // 2
            if dp[center] < a[i]:
                start = center + 1
            elif dp[center] > a[i]:
                stop = center
            else:
                flag = False
                break
        if flag and dp[start] > a[i]:
            history.append((start, dp[start]))
            dp[start] = a[i]
    ans[i] = len(dp)

    # todoに追加
    for j in uv[i]:
        if ans[j] == -1:
            todo.append(j)
            parents[j] = i

    if len(todo) == 0:
        break

    # back
    j = i
    while parents[todo[-1]] != j:
        k = history.pop(-1)
        if k == 0:
            dp.pop(-1)
        else:
            dp[k[0]] = k[1]
        j = parents[j]

for i in ans:
    print(i)

### FIXED CODE ###

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

uv = [[] for _ in range(n)]
for _ in range(n-1):
    i, j = map(int, input().split())
    uv[i-1].append(j-1)
    uv[j-1].append(i-1)

# DFS
# 頂点iが未探索の時、ans[i] = -1
ans = [-1 for _ in range(n)]
ans[0] = 1
# dp[i] = 長さi+1のLISの最後尾の最小値
dp = [a[0]]
# history[(i, j)]のとき、変更前はdp[i] = j
# stackとして使用
history = []
# 頂点parents[i] = iの親
parents = [-1 for _ in range(n)]

todo = []
for i in uv[0]:
    todo.append(i)
    parents[i] = 0

while True:
    i = todo.pop(-1)
    
    # ans[i]を求める
    if dp[-1] < a[i]:
        dp.append(a[i])
        history.append((-1, 0))
    else:
        # dpの変更点を二分探索
        start = 0
        stop = len(dp) - 1
        flag = True
        while start < stop:
            center = (start + stop) // 2
            if dp[center] < a[i]:
                start = center + 1
            elif dp[center] > a[i]:
                stop = center
            else:
                flag = False
                break
        if flag and dp[start] > a[i]:
            history.append((start, dp[start]))
            dp[start] = a[i]
        else:
            history.append((-2, 0))
    ans[i] = len(dp)

    # todoに追加
    for j in uv[i]:
        if ans[j] == -1:
            todo.append(j)
            parents[j] = i

    if len(todo) == 0:
        break

    # back
    j = i
    while parents[todo[-1]] != j:
        k = history.pop(-1)
        if k[0] == -2:
            None
        elif k[0] == -1:
            dp.pop(-1)
        else:
            dp[k[0]] = k[1]
        j = parents[j]

for i in ans:
    print(i)
import collections
import itertools
N = int(input())
#cnt[URLD][x y y+x y-x][value]=set()
cnt = [[collections.defaultdict(set) for _ in range(4)] for _ in range(4)]
for _ in range(N):
    x, y, u = input().split()
    x = int(x)
    y = int(y)
    p = y + x
    q = y - x
    i = 'URLD'.index(u)
    cnt[i][0][x].add(y)
    cnt[i][1][y].add(x)
    cnt[i][2][p].add(q)
    cnt[i][3][q].add(p)

INF = float('inf')


def calc(up, down):
    ret = [INF]
    for c in up.keys() & down.keys():
        ua = sorted(up[c])
        da = sorted(down[c])
        i = j = 0
        for i in range(len(ua)):
            for j in range(j, len(da)):
                if ua[i] < da[j]:
                    ret += [da[i] - ua[i]]
                    break
            i += 1
    return min(ret)


#U(0)とD(3)がx(0)が一緒:d-u(>=0)の最小値
#R(1)とL(2)がy(1)が一緒:l-r(>=0)の最小値
#U(0)とR(1)がx+y(2)が一緒:(y-x)のr-u(>=0)の最小値
#L(2)とD(3)がx+y(2)が一緒:(y-x)のd-l(>=0)の最小値
#U(0)とL(2)がy-x(3)が一緒:(y+x)のl-u(>=0)の最小値
#R(1)とD(3)がy-x(3)が一緒:(y+x)のd-r(>=0)の最小値
ans = min(
    calc(cnt[0][0], cnt[3][0]), calc(cnt[1][1], cnt[2][1]),
    calc(cnt[0][2], cnt[1][2]), calc(cnt[2][2], cnt[3][2]),
    calc(cnt[0][3], cnt[2][3]), calc(cnt[1][3], cnt[3][3]))
print('SAFE' if ans == INF else ans * 5)


### FIXED CODE ###

import collections
import itertools
N = int(input())
#cnt[URLD][x y y+x y-x][value]=set()
cnt = [[collections.defaultdict(set) for _ in range(4)] for _ in range(4)]
for _ in range(N):
    x, y, u = input().split()
    x = int(x)
    y = int(y)
    p = y + x
    q = y - x
    i = 'URLD'.index(u)
    cnt[i][0][x].add(y)
    cnt[i][1][y].add(x)
    cnt[i][2][p].add(q)
    cnt[i][3][q].add(p)

INF = float('inf')


def calc(up, down):
    ret = [INF]
    for c in up.keys() & down.keys():
        ua = sorted(up[c])
        da = sorted(down[c])
        i = j = 0
        for i in range(len(ua)):
            for j in range(j, len(da)):
                if ua[i] < da[j]:
                    ret += [da[j] - ua[i]]
                    break
            i += 1
    return min(ret)


#U(0)とD(3)がx(0)が一緒:d-u(>=0)の最小値
#R(1)とL(2)がy(1)が一緒:l-r(>=0)の最小値
#U(0)とR(1)がx+y(2)が一緒:(y-x)のr-u(>=0)の最小値
#L(2)とD(3)がx+y(2)が一緒:(y-x)のd-l(>=0)の最小値
#U(0)とL(2)がy-x(3)が一緒:(y+x)のl-u(>=0)の最小値
#R(1)とD(3)がy-x(3)が一緒:(y+x)のd-r(>=0)の最小値
ans = min(
    calc(cnt[0][0], cnt[3][0]), calc(cnt[1][1], cnt[2][1]),
    calc(cnt[0][2], cnt[1][2]), calc(cnt[2][2], cnt[3][2]),
    calc(cnt[0][3], cnt[2][3]), calc(cnt[1][3], cnt[3][3]))
print('SAFE' if ans == INF else ans * 5)
k = input()
s = raw_input()
if len(s) > 100:
    exit(1)

left = 0; right = int(s)
while 1:
    mid = (left + right) / 2
    cnt = 0
    now = 0
    for c in s:
        now = 10*now + int(c)
        if now > mid:
            cnt += 1
            now = int(c)
            if now > mid:
                cnt = 100003
                break
    if cnt > k:
        if left == mid:
            break
        left = mid
    else:
        if right == mid:
            break
        right = mid
print left+1


### FIXED CODE ###

k = input()
s = raw_input()

if k==0:
    print s
    exit(0)
if len(s) % (k+1) == 0:
    p = len(s) / (k+1)
    print max(int(s[i:i+p]) for i in xrange(0,len(s),p))
    exit(0)

l = len(s) / (k+1)
r = (len(s)+k) / (k+1)
left = 10**(l-1)
right = 10**r
while 1:
    mid = (left + right) / 2
    cnt = 0
    now = ""
    mid_c = str(mid)
    cp = idx = 0
    for c in s:
        now += c
        if not cp and idx < len(mid_c) and c != mid_c[idx]:
            cp = 1 if c > mid_c[idx] else -1
        idx += 1
        if (idx == len(mid_c) and cp == 1) or idx > len(mid_c):
            cnt += 1
            idx = 1; cp = 0
            if int(c) > mid:
                cnt = 100003
                break
            now = c
            if c != mid_c[0]:
                cp = 1 if c > mid_c[0] else -1
    if cnt > k:
        if left == mid:
            break
        left = mid
    else:
        if right == mid:
            break
        right = mid
print left+1
w, h, x, y = list(map(int, input().split(" ")))

if w%x == 0 and h%y == 0:
	print(w*h/2.0, "1")
else:
	print(w*h/2.0, "0")

### FIXED CODE ###

w, h, x, y = list(map(int, input().split(" ")))

if x*2 == w  and y*2 == h:
	print(w*h/2.0, "1")
else:
	print(w*h/2.0, "0")
a,v = map(int,input().split())
b,w = map(int,input().split())
t = int(input())

if v == w:
  print('NO')
  exit()
elif (a > b) and (v >= m):
  print('NO')
  exit()
  
for i in range(1,t+1):
  oni = a+(v*i)
  child = c+(w*i)
  if oni >= child:
    print('YES')
    break
else:
  print('NO')

### FIXED CODE ###

A, V = [int(n) for n in input().split()]
B, W = [int(n) for n in input().split()]
T = int(input())
 
if V <= W:
    print('NO')
    exit()
    
d = abs(A - B)

if V > W and d <= (V - W) * T:
    print('YES')
else:
    print('NO')
X,A=(inx(x) for x in input().split())
if X>=A:
  print(10)
else:
  print(0)

### FIXED CODE ###

X,A=(int(x) for x in input().split())
if X>=A:
  print(10)
else:
  print(0)
N, M = map(int,input().split())

return(int(N*(N-1)//2 + M*(M-1)//2))


### FIXED CODE ###

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

print(int(N * (N-1)//2 + M * (M-1)//2))
a, b, k = map(int, input().split())
nums = []
for i in range(min(a, b)-2):
    if ((a % (i+2) == 0) and (b % (i+2) == 0)):
        nums.append(i+2)
if ( max(a,b) % min(a,b) == 0 ):
    nums.append(min(a,b))
print(nums[-1*k])

### FIXED CODE ###

a, b, k = map(int, input().split())
nums = []
for i in range(min(a, b)-1):
    if ((a % (i+1) == 0) and (b % (i+1) == 0)):
        nums.append(i+1)
if ( max(a,b) % min(a,b) == 0 ):
    nums.append(min(a,b))
print(nums[-1*k])
import math

A,B,C,D = map(int,input().split())
A -= 1
g = math.gcd(C, D)
l = C * D / g

sA = A // C
eA = A // D
lA = A - (eA + sA) + A // l

sB = B // C
eB = B // D
lB = B - (eB + sB) + B // l
print(int(lB - lA))


### FIXED CODE ###

import fractions

A,B,C,D = map(int,input().split())
l = C*D // fractions.gcd(C,D)
x = (A-1) -(A-1)//C - (A-1)//D + (A-1)//l
y = B - B//C - B//D + B//l
print(y-x)
import math

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

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

success = False;
ans = 0
_lcm = lcm(N, M)
for k in range(1, N*M//_lcm + 1):
    ans = k * _lcm
    s = [(i * ans)//N + 1 for i in range(N)]
    t = [(i * ans)//M + 1 for i in range(M)]

    pool = s + t

    double_st = [x for x in set(pool) if pool.count(x) > 1]
    isImpossible = False

    for i, st in enumerate(double_st):
        s_i = s.index(st)
        t_i = t.index(st)
        if S[s_i] != T[t_i]:
            isImpossible = True
            
    if not isImpossible:
        success = True
        break

if not success:
    print(-1)
else:
    print(ans)

### FIXED CODE ###


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

def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
 
def lcm(x, y):
    return (x * y) // gcd(x, y)

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

success = False
fans = 0

_lcm = lcm(len(S), len(T))

def isImpble(k, _lcm):
    global success
    global S
    global T
    global fans
    
    ans = k * _lcm
    double_st = []
    
    for i in range(len(S)):
        if (len(T)*i)%len(S) == 0 and (len(T) * i)//len(S) <len(T):
            double_st += [(i * ans)//len(S) + 1]
    isImpossible = False

    for st in double_st:
        s_i = ((st-1) * len(S))//ans
        t_i = ((st-1) * len(T))//ans
        if S[s_i] != T[t_i]:
            isImpossible = True
            break

            
    if isImpossible:
        return True
    else:
        success = True
        fans = k*_lcm
        return False
        

imp = isImpble((len(S) * len(T))//_lcm, _lcm)

if not imp:
    for k in range(1, (len(S) * len(T))//_lcm ):
        imp = isImpble(k, _lcm)
        if success:
            break
    

if not success:
    print(-1)
else:
    print(fans)
N,M=map(int,input().split())
G=[]
for i in range(0,M):
    G.append([])

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

q=[]
sign=[-1]*N
sign[0]=0
q.append(0)
while q:
    x=q.pop(0)
    for nv in G[x]:
        if sign[nv]==-1:
            sign[nv]=x
            q.append(nv)

print("Yes")
for i in range(1,N):
    print(sign[i]+1)


### FIXED CODE ###

N,M=map(int,input().split())
G=[]
for i in range(0,N):
    G.append([])

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

q=[]
sign=[-1]*N
sign[0]=0
q.append(0)
while q:
    x=q.pop(0)
    for nv in G[x]:
        if sign[nv]==-1:
            sign[nv]=x
            q.append(nv)

print("Yes")
for i in range(1,N):
    print(sign[i]+1)
S = inout()

if S == ABC:
	print(ARC)
    
if S == ARC:
  print(ABC)

### FIXED CODE ###

S = input()

if S == "ABC":
    print("ARC")

if S == "ARC":
    print("ABC")
h,w=map(int,input().split())
ans=[]
ans.append(['#'*(w+2)])
for i in range(h):
  a=list(map(int,input().split()))
  a.insert(0,'#')
  a.append('#')
  ans.append(a)
ans.append(['#'*(w+2)])
for i in ans:
  print(''.join(i))

### FIXED CODE ###

h,w=map(int,input().split())
ans=[]
ans.append(['#']*(w+2))
for i in range(h):
  a=list(input().split())
  a.insert(0,'#')
  a.append('#')
  ans.append(a)
ans.append(['#']*(w+2))
for i in ans:
  print(''.join(i))
N, X = map(int, input().split())
L = list(map(int, input().split()))
cnt = 0
for i in range(N+2):
    if cnt <= X:
        cnt += L[i]
    else:
        print(i)
        break

### FIXED CODE ###

N, X = map(int, input().split())
L = list(map(int, input().split()))
cnt = 0
if sum(L) <= X:
    print(N+1)
else:
    for i in range(N+1):
        if cnt <= X:
            cnt += L[i]
        else:
            print(i)
            break
A, B = input().split()

A = int(A)
B = float(B)
B = (B*100).round()

print((A*B)//100)

### FIXED CODE ###

A, B = input().split()
 
A = int(A)
B = float(B)
B = round((B*100))
 
print((A*B)//100)
N, M = map(int, input().split())
A = [int(input()) for _ in range(M)]
s_A = sum(A)

if N - s_A>= 0:
    print(N - s_A)
if N -s_A < 0:
    print(-1)



### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in a:
    n-=i
    if n<0: #宿題の総日数が夏休みの日数を上回った場合
        print(-1)
        exit()
print(n)
n = int(input())
ma = 10**100
for i in range(1, 10**6+2):
  if N % i == 0:
    ma = min(ma,((i-1)+(n//i)-1))
print(ma)


### FIXED CODE ###

n = int(input())
ma = 10**100
for i in range(1, 10**6+2):
  if n % i == 0:
    ma = min(ma,((i-1)+(n//i)-1))
print(ma)
N = int(input())
for i in raNge(N+1):
    if int(i*1.08)==N:
        primt(i)
        exit()
print(':(')


### FIXED CODE ###

n=int(input())
for i in range(n+1):
    if int(i*1.08)==n:
        print(i)
        exit()
print(':(')
A,B = input().split()
A = int(A)
B = float(B*100)

s = A * B
s = s // 100
print(int(s))


### FIXED CODE ###

from decimal import Decimal

A,B = input().split()
A = int(A)
B = int(Decimal(B) * 100)

s = A * B
s = s // 100
print(int(s))
s = list(input())
x = list(map(int, s))
i = 0
ans = 0
k = 0
if len(x) == 1:
    print(0)
else:
    while(True):
        if x[i] + x[i + 1] == 1:
            k += 1
            del x[i + 1], x[i]
        if i + 2 >= len(x):
            ans += k
            if k == 0 or len(x) == 0:
                break
            k = 0
            i = 0
        else:
            i += 1
    print(ans * 2)


### FIXED CODE ###

s = list(input())
x = list(map(int, s))
k = 0
for i in range(len(x)):
    if x[i] == 0:
        k += 1
print(2 * min(k, len(x) - k))
n,x = map(int,input().split())
li = list(map(int,input().split()))
count = 1
kyori
for i in li:
  kyori = kyori + i
  count += 1
  if kyori > x:
    break
print(count-1)

### FIXED CODE ###

n,x = map(int,input().split())
li = list(map(int,input().split()))
count = 1
kyori = 0
for i in li:
  kyori = kyori + i
  count += 1
  if kyori > x:
    count -=1
    break
print(count)
import itertools
O, E = raw_input().split()
seq = []
for x, y in itertools.izip_longest(O, E):
    if x: seq.append(x)
    if y: seq.append(y)
print ''.join(seq)

### FIXED CODE ###

import itertools
O = raw_input()
E = raw_input()
seq = []
for x, y in itertools.izip_longest(O, E):
    if x: seq.append(x)
    if y: seq.append(y)
print ''.join(seq)
import numpy as np
S = input()
T = input()

tmp = np.zeros(len(T))

i=0
flg=True

while flg:
    for j in range(i, len(T)):
        if T[i:j+1] in S:
            tmp[i] = j+1-i
    i = max(i + int(tmp[i]),i+1)
    if i >= len(T)-1:
        flg=False

tmp = np.array(tmp, dtype=int)
i = np.argmax(tmp)
j = tmp[i]
s = S.find(T[i:i+j])
if s - i >= 0 and s - i + len(T) <= len(S):
    print(len(T)-int(np.max(tmp)))
else:
    l=0
    for k in range(len(T)):
        if S[s+k] == T[k]:
            l+=1
    print(len(T)-l)

### FIXED CODE ###

S=input()
T=input()
ls=len(S)
lt=len(T)
ans=lt
for i in range(0,ls-lt+1):
    a=0
    for j in range(lt):
        if S[i+j]==T[j]:
            a+=1
    ans=min(ans,lt-a)
print(ans)