Harryxun/stf_run huggingface dataset:
from math import factorial
from operator import mul
from functools import reduce
from math import sqrt

def c(n,r):
  r = min(n-r,r)
  if r == 0 or r == n:
    return 1
  else:
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under
def num(k): # k段昇る場合の数
  return int((((1+sqrt(5))/2) ** k - ((1-sqrt(5))/2) ** k) / sqrt(5))
  """
  l,r = k // 2, 0
  for i in range(l+1):
    r += c(k-i,i)
    r %= mod
  return r
  """

n,m=map(int,input().split())
mod = 10 ** 9 + 7

if m == 0:
  print(num(n) % mod)
  exit()

a=[int(input()) for i in range(m)] # 壊れてる段

# ここから先 m > 0
a = [-1] + a + [n+1] # len(a)=m+2
sa = [a[i+1]-a[i]-2 for i in range(len(a)-1)]
ans = 1
#print(sa)
for i in sa:
  ans *= num(i)
  ans %= mod
print(ans)


### FIXED CODE ###

a=list(map(int,input().split()))
a.sort()
print(a[0]+a[1])
S, T = map(int, input().split())
A, B = map(int, input().split())
U int(input())

if U == S:
  A -= 1
if U == T:
  B -= 1
  
print(A, B)


### FIXED CODE ###

S, T = input().split()
A, B = map(int, input().split())
U = input()
 
if U == S:
  A -= 1
if U == T:
  B -= 1

print(A, B)
n=int(input())
X=[]
Y=[]
A=[]
for i in range(n):
  A=int(input())
  x=[]
  y=[]
  for j in range(A[i]):
    #x,y=[int(s) for s in input().split()]
  #X.append(x)
  #Y.append(y)
  
c=0
#for i in range(n):
 # l=[1]*n
  #for j in range(i, n-i):
   # if l[j]==0:continue
    #for k in range(A[j]):
   # 　　l[X[j][k]] *= Y[j][k]
#if c<l.count(1):
 # c=l.count(1) 
  
        
  
print(c)  
   

### FIXED CODE ###

n=int(input())
X=[]
Y=[]
A=[0]*n
for i in range(n):
  A[i]=int(input())
  a=A[i]
  x=[0]*a
  y=[0]*a
  for j in range(a):
    x[j],y[j]=[int(s) for s in input().split()]
  X.append(x)
  Y.append(y)
  
s=0
for i in range(2**n):
  c=0
  d=0
  B=[0]*n
  for j in range(n):
    if((i >> j) & 1):
      c=c+1
      B[j]=1
  for k in range(n):
    if B[k]==1:
      for j in range(A[k]):
        if Y[k][j]!=B[X[k][j]-1]:
          d=-1
          break
    if d<0:
      break
  if s<c and d==0:
    s=c
      
      
print(s)
def main():
    S = input()
    answer = solve(S)
    print(answer)


def solve(S):
    assert len(S) == 3
    assert all([x in ('S', 'R') for x in S])

    chain = []
    count = 0
    for i in range(len(S)):
        if S[i] == 'R':
            count += 1
        else:
            chain.append(count)

    return max(chain)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    S = input()
    answer = solve(S)
    print(answer)


def solve(S):
    patterns = {
        'SSS': 0,
        'SSR': 1,
        'SRS': 1,
        'SRR': 2,
        'RRR': 3,
        'RRS': 2,
        'RSR': 1,
        'RSS': 1
    }

    return patterns[S]


if __name__ == "__main__":
    main()
while True:
    n,s,e = input().split()
    n = int(n)
    s = int(s)
    e = int (e)
    if not n+s+e:
        break
    s = s//100*60+s%100
    e = e//100*60+e%100
    t = [0]*60*24    
    for i in range(n):
        m = int(input())
        for j in range(m):
            ss,ee = input().split()
            ss = int(ss)
            ee = int(ee)
            t[ss//100*60+ss%100] += 1
            t[ee//100*60+ee%100] -= 1
    cnt = 0
    ans = 0
    ma = -1
    for i in range(e):
        cnt += t[i]
        if i < s:
            continue
        if not cnt:
            ans += 1
        else:
            if ma < ans:
                ma = ans
                ans = 0
        if ma < ans:
            ma = ans
    print(ma)

### FIXED CODE ###

while True:
    n,s,e = input().split()
    n = int(n)
    s = int(s)
    e = int(e)
    if not n+s+e:
        break
    s = s//100*60+s%100
    e = e//100*60+e%100
    t = [0]*(60*24+1)
    for i in range(n):
        m = int(input())
        g = input().split()
        j = 0
        for o in g:
            a = int(o)
            if j%2:
                t[a//100*60+a%100] += 1
            else:
                t[a//100*60+a%100] -= 1
            j += 1
    cnt = n
    ans = 0
    ma = -1
    for i in range(e):
        cnt += t[i]
        if i < s:
            continue
        if cnt:
            ans += 1
        else:
            if ma < ans:
                ma = ans
            ans = 0
    print(ma if ma > ans else ans)
C = input()
print chr(ord('C') + 1)

### FIXED CODE ###

C = input()
print(chr(ord(C) + 1))
n,k=map(int,input().split())
def temp(n,k):
    if(n>=k):
        if(n % k ==0):
            return 0
        else:
            return(temp(n%k,k))
        
    else:
        if(k%n == 0):return n
        else:
            return (min(n,k%n))
print(temp(n,k))


### FIXED CODE ###

n,k=map(int,input().split())
def temp(n,k):
    if(n>=k):
        if(n % k ==0):
            return 0
        else :
            return(min(n%k,k-(n%k)))
        
    else:
        return (min(n,k-n))
print(temp(n,k))
str = input()

if str == "Sunny":
  print("Cloudy")
elif str == "Cloudy":
  print("Rainy"):
else:
  print("Sunny")

### FIXED CODE ###

str = input()
 
if str == "Sunny":
  print("Cloudy")
elif str == "Cloudy":
  print("Rainy")
else:
  print("Sunny")
N, A, B, C = map(int, input().split())
X = [input() for _ in range(N)]


def solve(x):
    d = {"A": 0, "B": 1, "C": 2}
    ans = []
    for i in range(N):
        u, v = X[i]
        if x[d[u]] == x[d[v]] == 0:
            return

        if x[d[u]] < x[d[v]]:
            x[d[u]] += 1
            x[d[v]] -= 1
            ans.append(u)
        elif x[d[u]] > x[d[v]]:
            x[d[u]] -= 1
            x[d[v]] += 1
            ans.append(v)
        else:
            # x[d[u]] == x[d[v]] >= 1
            if i < N - 1 and X[i] != X[i + 1]:
                x, y = X[i + 1]
                if u == x or u == y:
                    x[d[u]] += 1
                    x[d[v]] -= 1
                    ans.append(u)
                else:
                    x[d[u]] -= 1
                    x[d[v]] += 1
                    ans.append(v)
            else:
                x[d[u]] += 1
                x[d[v]] -= 1
                ans.append(u)

    return ans

ans = solve([A, B, C])
if ans:
    print("Yes")
    print(*ans, sep="\n")
else:
    print("No")


### FIXED CODE ###

N, A, B, C = map(int, input().split())
X = [input() for _ in range(N)]


def solve(x):
    d = {"A": 0, "B": 1, "C": 2}
    ans = []
    for i in range(N):
        u, v = X[i]
        if x[d[u]] == x[d[v]] == 0:
            return

        if x[d[u]] < x[d[v]]:
            x[d[u]] += 1
            x[d[v]] -= 1
            ans.append(u)
        elif x[d[u]] > x[d[v]]:
            x[d[u]] -= 1
            x[d[v]] += 1
            ans.append(v)
        elif i < N - 1 and X[i] != X[i + 1]:
            # x[d[u]] == x[d[v]] >= 1
            if u in X[i + 1]:
                x[d[u]] += 1
                x[d[v]] -= 1
                ans.append(u)
            else:
                x[d[u]] -= 1
                x[d[v]] += 1
                ans.append(v)
        else:
            x[d[u]] += 1
            x[d[v]] -= 1
            ans.append(u)

        if x[d[u]] < 0 or x[d[v]] < 0:
            return

    return ans

ans = solve([A, B, C])
if ans:
    print("Yes")
    print(*ans, sep="\n")
else:
    print("No")
N,M= list(map(int, input().split()))
P = [list(map(int,input().split())) for i in range(M)]
Q = list(map(list, set(map(tuple, P))))
C = []
S = []
n = N -1
sum1 = 0

for s in range(len(Q)):
    C.append(Q[s][0])
for t in range(len(Q)):
    S.append(Q[t][1])
D = list(set(C))
if D.count(1) == 1:
    unko = C.index(1)
if len(D) <len(S) or Q[unko][1] == 0:
    print("-1")
else:
    for u in range(len(Q)):
        sum1 = sum1 + Q[u][1]*(10 ** (N - Q[u][0]))
    if sum1 > (10 ** n):
        print(sum1)
    else:
        print(sum1 + 10 ** n)

### FIXED CODE ###

N,M= list(map(int, input().split()))
P = [list(map(int,input().split())) for i in range(M)]
Q = list(map(list, set(map(tuple, P))))
C = []
S = []
n = N -1
sum1 = 0
 
for s in range(len(Q)):
    C.append(Q[s][0])
for t in range(len(Q)):
    S.append(Q[t][1])
D = list(set(C))
if len(D) <len(S) :
    print("-1")
else:
    if N == 1 and M == 1 and Q[0][1] == 0:
        print("0")
    elif N == 1 and M == 0:
                print("0")
    else:
        for u in range(len(Q)):
            sum1 = sum1 + Q[u][1]*(10 ** (N - Q[u][0]))
        if sum1 >= (10 ** n):
            print(sum1)
        else:
            if D.count(1) >= 1:
                unko = C.index(1)
                if Q[unko][1] == 0:
                    print("-1")
                else:
                    print(sum1 + 10 ** n)
            else:
                print(sum1 + 10 ** n)
a, b = [int(x) for x in input().split()]
s = input()
if s[a] == "-" and len(s) == (a+b+1) and (s[:a]+s[a+1:].isdigit()):
  print("Yes")
else:
  print("No")

### FIXED CODE ###

a, b = [int(x) for x in input().split()]
s = input()
if s[a] == "-" and len(s) == (a+b+1) and (s[:a]+s[a+1:]).isdigit():
  print("Yes")
else:
  print("No")
print(len(list(filter(lambda x:x<=int(input()),[105, 135, 165, 189, 195]))))

### FIXED CODE ###

n=int(input())
ansList=[105, 135, 165, 189, 195]
m=len(list(filter(lambda x:x<=n,ansList)))
print(m)
n = int(input())
alist  = list(map(int,input().split()))
list1 = alist[1::2]
list2 = alist[0::2]
from collections import Counter
dic1 = Counter(list1).most_common()
dic2 = Counter(list2).most_common()
dic1.append([0,0])
dic2.append([0,])
if dic1[0][0]!=dic2[0][0]:
  print(n - dic1[0][1] - dic2[0][1])
else:
  print(min(n - dic1[0][1] - dic2[1][1], n -dic1[1][1] - dic2[0][1]))

### FIXED CODE ###

n = int(input())
alist  = list(map(int,input().split()))
list1 = alist[1::2]
list2 = alist[0::2]
from collections import Counter
dic1 = Counter(list1).most_common()
dic2 = Counter(list2).most_common()
dic1.append([0,0])
dic2.append([0,0])
if dic1[0][0]!=dic2[0][0]:
  print(n - dic1[0][1] - dic2[0][1])
else:
  print(min(n - dic1[0][1] - dic2[1][1], n -dic1[1][1] - dic2[0][1]))
n=int(input())
a=list(int(input())for i in range(n))
b=0
for i in range(n):
  if a[i]-a[i+1]>=2:
    b+=1
if b==0:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=0
c=a.reverse()
d=0
for i in range(n-1):
  if a[i]-a[i+1]==-1:
    a[i+1]=a[i+1]-1
  elif a[i]-a[i+1]<=-2:
    b+=1
  else:
    d=d
    
if b==0:
  print("Yes")
else:
  print("No")
input = read
rn = lambda :map(int, read().split())
m,k = rn()
import math
N = 2**(m) - 1 # 0~N
r = [i for i in range(N+1)] # 0~N
if k > N:
    print(-1)
# elif N == 1 and k == 0:
#     print(0, 0)
elif k ==  0:
    for i in r:
        print(i, end=' ')
    r.reverse()
    for i in r:
        print(i, end=' ')
elif N == 2 and k == 1:
    print(-1)
else:
    for i in r:
        if i == k:continue
        print(i, end=' ')
    print(k, end=' ')
    r.reverse()
    for i in r:
        if i == k:continue
        print(i, end=' ')
    print(k, end=' ')
    

### FIXED CODE ###

read = input 
rn = lambda :map(int, read().split())
m,k = rn()
import math
N = 2**(m) - 1 # 0~N
r = [i for i in range(N+1)] # 0~N
if k > N:
    print(-1)
# elif N == 1 and k == 0:
#     print(0, 0)
elif N == 1 and k == 1:
    print('-1')
elif k ==  0:
    for i in r:
        print(i, end=' ')
    r.reverse()
    for i in r:
        print(i, end=' ')
elif N == 2 and k == 1:
    print(-1)
else:
    for i in r:
        if i == k:continue
        print(i, end=' ')
    print(k, end=' ')
    r.reverse()
    for i in r:
        if i == k:continue
        print(i, end=' ')
    print(k, end=' ')
n = int(input())
h = list(map(int, input().split()))

i = 0
while True:
    if i == n-1:
        print('Yes')
        break
    if h[i] <= h[i+1]:
        print(i, 'a', h)
        if i == 0 or h[i-1] < h[i]:
            h[i] -= 1
        i += 1
    elif h[i] == h[i+1]+1 and (i==0 or h[i-1] < h[i]):
        print(i, 'b', h)
        h[i] -= 1
        i += 1
    else:
        print('No')
        break

### FIXED CODE ###

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

i = 0

while True:
    if i == n-1:
        print('Yes')
        break
    if h[i] <= h[i+1]:
        if i == 0 or h[i-1] < h[i]:
            h[i] -= 1
        i += 1
    elif h[i] == h[i+1]+1 and (i==0 or h[i-1] < h[i]):
        h[i] -= 1
        i += 1
    else:
        print('No')
        break
import sys


input = sys.stdin.readline

N, M = map(int, input().split())
has_broken = [False]*(N+3)
prev_a = int(input())
has_broken[prev_a+2] = True
for _ in range(M-1):
    a = int(input())
    has_broken[a+2] = True

dp = [0]*(N+3)
dp[2] = 1
MOD = 10**9+7
for i in range(2, N+3):
    if not has_broken[i]:
        dp[i] += (dp[i-1] + dp[i-2])%MOD

print(dp[N+2])

### FIXED CODE ###

import sys


input = sys.stdin.readline

N, M = map(int, input().split())
has_broken = [1]*(N+1)
for _ in range(M):
    has_broken[int(input())] = 0

dp = [1]*(N+1)
dp[1] = 1 if has_broken[1] == 1 else 0
MOD = 10**9+7
for i in range(2, N+1):
    dp[i] = has_broken[i]*(dp[i-1] + dp[i-2])

print(dp[N]%MOD)
from decimal import Decimal
import math
a,b,c=map(int,input().split())
if a+b+2*Decimal(math.sqrt(a))*Demical(math.sqrt(b))<c:
  print("Yes")
else:
  print("No")


### FIXED CODE ###

from decimal import Decimal
import math
a,b,c=map(int,input().split())
if c-a-b>0 and 4*a*b<(c-a-b)**2:
  print("Yes")
else:
  print("No")
N,M = map(int,input().split())
num =0
line_m=[]
line_s=[]
for k in range(M):
    line_m.append(0)
for i in range(N):
    line_s = list(map(int, input().split()))
    for n in range(int(line_s[0])):
        line_m[int(line_s[n+1])] = int(line_m[int(line_s[n+1])]) + 1

for s in range(M):
    if line_m[s] == N:
        num = num+1

print(num)
        

### FIXED CODE ###

N,M = map(int,input().split())
num =0
line_m=[]
line_s=[]
for k in range(M+1):
    line_m.append(0)
for i in range(N):
    line_s = list(map(int, input().split()))
    for n in range(int(line_s[0])):
        line_m[int(line_s[n+1])] = int(line_m[int(line_s[n+1])]) + 1

for s in range(M+1):
    if line_m[s] == N:
        num = num+1

# print(line_s)
# print(line_m)

print(num)
# -*- coding: utf-8 -*-
"""
Created on Fri Apr  5 14:11:52 2019

@author: adachi-lab
"""

input_code = str(input())
L1 = len(input_code)

list_3 = []
for w in range(L1):
    list_3.append(w)


x = 0
for i in range(L1):
    code = input_code[i]
    if code == 'A' or code == 'C' or code == 'G' or code == 'T':
        list_3.remove(x)
    
    x+=1

L3 = len(list_3)
list_4 = []

if list_3[0] == 0:
    for q in range(L3-1):
        list_4.append(list_3[q+1]-list_3[q]-1)
    list_4.append(L1-list_3[L3-1]-1)
    
    
else:
    list_3.insert(0,0)
    list_4.append(list_3[1])
    for q in range(L3):
        list_4.append(list_3[q+1]-list_3[q]-1)
    list_4.append(L1-list_3[L3]-1)
    list_4.pop(1)
    
    


print(max(list_4))

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Fri Apr  5 16:48:09 2019

@author: adachi-lab
"""

input_code = input()
L1 = len(input_code)
list_3 = []
list_4 = []
list_5 = []

for w in range(L1):
    list_3.append(0)
    list_4.append(0)


for i in range(L1):
    code = input_code[i]
    if code == 'A' or code == 'C' or code == 'G' or code == 'T':
        list_3[i] = 1
        
c = 0

for n,m in zip(list_3,list_4):
    
    if n == m:
        c = 0
        list_5.append(c)
        
    else:
        c += 1
        list_5.append(c)
        
print(max(list_5))
A, B = map(int input().split())
if max(A, B) > 8:
    print(':(')
else:
    print('Yay!')

### FIXED CODE ###

A, B = map(int, input().split())
if max(A, B) > 8:
    print(':(')
else:
    print('Yay!')
import sys
input = sys.stdin.readline
A=int(input())
P=int(input())
if A%2==0:
  A=A*3/2
  print(A+P)
else:
  A=(A*3+P)/2
  print(A)

### FIXED CODE ###

import sys
input = sys.stdin.readline
a,p = map(int,input().split())
print((a*3+p)//2)
import copy
import sys
sys.setrecursionlimit(400)

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())

dx=[1,0,-1,0]
dy=[0,1,0,-1]

walker=[]
for row in range(H):
    walker.append([None]*W)
waiting=[]
def func(xy, walker):
    x, y = xy
    for i in range(4):
        if 0 <= x+dx[i] < W and 0 <= y+dy[i] <H:
            if walker[y+dy[i]][x+dx[i]] == None and S[y+dy[i]][x+dx[i]] == '.':
                walker[y+dy[i]][x+dx[i]] = walker[y][x]+1
                waiting.append((x+dx[i], y+dy[i]))
    if waiting:
        func(waiting.pop(0),walker)
    else:
        return None


candicate=[]
for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == '.':
            temp_walker=copy.deepcopy(walker)
            temp_walker[sy][sx]=0
            func((sx,sy), temp_walker)
        far=0
        for gx in range(W):
            for gy in range(H):
                if S[gy][gx]=='.':
                    if far <= temp_walker[gy][gx]:
                        far = temp_walker[gy][gx]

        #print(sx, sy, temp_walker, far)
        candicate.append(far)
print(max(candicate))




### FIXED CODE ###

import copy
import sys
sys.setrecursionlimit(10**6)

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())

dx=[1,0,-1,0]
dy=[0,1,0,-1]

walker=[]
for row in range(H):
    walker.append([None]*W)
waiting=[]
def func(xy, walker):
    x, y = xy
    for i in range(4):
        if 0 <= x+dx[i] < W and 0 <= y+dy[i] <H:
            if walker[y+dy[i]][x+dx[i]] == None and S[y+dy[i]][x+dx[i]] == '.':
                walker[y+dy[i]][x+dx[i]] = walker[y][x]+1
                waiting.append((x+dx[i], y+dy[i]))
    if waiting:
        func(waiting.pop(0) ,walker)
    else:
        return None


candicate = []
for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == '.':
            temp_walker=copy.deepcopy(walker)
            temp_walker[sy][sx]=0
            func((sx,sy), temp_walker)
            far=0

            for gx in range(W):
                for gy in range(H):
                    if S[gy][gx]=='.':
                        if far < temp_walker[gy][gx]:
                            far = temp_walker[gy][gx]

            #print(sx, sy, temp_walker, far)
            candicate.append(far)
print(max(candicate))
N =  map(int,input().split())

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



for i in range(N):
    v = a[i]
    j = i-1
    while j>=0 and a[j]>v:
        a[j+1] = a[j]
        j = j-1
        a[j+1] = v
    print(a) 


### FIXED CODE ###

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


for i in range(N):
    v = b[i]
    j = i-1
    while j>=0 and b[j]>v:
        b[j+1] = b[j]
        j = j-1
        b[j+1] = v
    print(" ".join([str(n) for n in b]))
n,k = list(map(int,input().split()))
A = list(map(int,input().split()))

if k == 1:exit(print(A[0]))
t = 0
dp = [-1] * n
dp[0] = 0
for i in range(1,k+1):
  t = A[t]-1
  if dp[t] != -1:break
  dp[t] = i
  
l = i - dp[t]
K = (k-dp[t])%l + dp[t]
print(dp)
for i in range(n):
  if dp[i] == K:exit(print(i+1))

### FIXED CODE ###

n,k = list(map(int,input().split()))
A = list(map(int,input().split()))

if k == 1:exit(print(A[0]))
t = 0
dp = [-1] * n
dp[0] = 0
flg = 0
for i in range(1,k+1):
  t = A[t]-1
  if dp[t] != -1:
    flg = 1
    break
  dp[t] = i
if flg == 0:
  exit(print(t+1))
elif k == 2:
  exit(print(t+1))

l = i - dp[t]
K = (k-dp[t])%l + dp[t]

for i in range(n):
  if dp[i] == K:exit(print(i+1))
n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [i//2 for i in a]

def f(x):
  cnt = 0
  while x%2 == 0:
    x /= 2
    cnt += 1
  return cnt

def lcm(x, y):
  z = x * y
  if x < y:
    x, y = y, x
  while x%y != 0:
    x, y = y, x%y
  return z // y

t = f(a[0])
for i in range(1, t):
  if f(a[i]) != t:
    print(0)
    break
  a[i] >>= t
m >>= t

L = a[0]
for i in range(1, n):
  L = lcm(L, a[i])
  if L > M:
    print(0)
    break

m //= L
ans = (m+1) // 2
print(ans)

### FIXED CODE ###

import sys

def f(x):
  cnt = 0
  while x%2 == 0:
    x /= 2
    cnt += 1
  return cnt

def gcd(x, y):
  if y:
    return gcd(y, x%y)
  else:
    return x

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


n, m = map(int, input().split())
a = list(map(int, input().split()))
a = [i//2 for i in a]

t = f(a[0])
for i in range(n):
  if f(a[i]) != t:
    print(0)
    sys.exit()
  a[i] >>= t
m >>= t

l = 1
for i in range(n):
  l = lcm(l, a[i])
  if l > m:
    print(0)
    sys.exit()

m //= l
ans = (m+1) // 2
print(ans)
import copy
import sys
sys.setrecursionlimit(10**8)

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())

dx=[1,0,-1,0]
dy=[0,1,0,-1]

walker=[]
for row in range(H):
    walker.append([None]*W)
waiting=[]
def func(xy, walker):
    x, y = xy
    for i in range(4):
        if 0 <= x+dx[i] < W and 0 <= y+dy[i] <H:
            if walker[y+dy[i]][x+dx[i]] == None and S[y+dy[i]][x+dx[i]] == '.':
                walker[y+dy[i]][x+dx[i]] = walker[y][x]+1
                waiting.append((x+dx[i], y+dy[i]))
    if waiting:
        func(waiting.pop(0) ,walker)
    else:
        return None


candicate = []
for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == '.':
            temp_walker=copy.deepcopy(walker)
            temp_walker[sy][sx]=0
            func((sx,sy), temp_walker)
        far=0
        for gx in range(W):
            for gy in range(H):
                if S[gy][gx]=='.':
                    if far <= temp_walker[gy][gx]:
                        far = temp_walker[gy][gx]

        #print(sx, sy, temp_walker, far)
        candicate.append(far)
print(max(candicate))




### FIXED CODE ###

import copy
import sys
sys.setrecursionlimit(10**6)

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())

dx=[1,0,-1,0]
dy=[0,1,0,-1]

walker=[]
for row in range(H):
    walker.append([None]*W)
waiting=[]
def func(xy, walker):
    x, y = xy
    for i in range(4):
        if 0 <= x+dx[i] < W and 0 <= y+dy[i] <H:
            if walker[y+dy[i]][x+dx[i]] == None and S[y+dy[i]][x+dx[i]] == '.':
                walker[y+dy[i]][x+dx[i]] = walker[y][x]+1
                waiting.append((x+dx[i], y+dy[i]))
    if waiting:
        func(waiting.pop(0) ,walker)
    else:
        return None


candicate = []
for sx in range(W):
    for sy in range(H):
        if S[sy][sx] == '.':
            temp_walker=copy.deepcopy(walker)
            temp_walker[sy][sx]=0
            func((sx,sy), temp_walker)
            far=0

            for gx in range(W):
                for gy in range(H):
                    if S[gy][gx]=='.':
                        if far < temp_walker[gy][gx]:
                            far = temp_walker[gy][gx]

            #print(sx, sy, temp_walker, far)
            candicate.append(far)
print(max(candicate))
s=input()
a=[ord(c)-ord('a') for c in s]
K=int(input())

# print(a) #DB

for i in range(len(s)):
    if 26-a[i]>K:
        continue
    else:
        K-=26-a[i]
        a[i]=0

a[-1]+=K

print(''.join([chr(ord('a')+ai) for ai in a]))

### FIXED CODE ###

s=input()
K=int(input())
ans=''
for c in s:
    if c!='a' and ord('z')+1-ord(c)<=K:
        ans+='a'
        K-=ord('z')+1-ord(c)
    else:
        ans+=c
if K>0:
    ans=ans[:-1]+chr(ord(ans[-1])+K%26)

print(ans)
import sys

INF = 10**9 + 5

N, M, K = map(int, sys.stdin.readline().rstrip().split())
A = [int(x) for x in sys.stdin.readline().rstrip().split()]
B = [int(x) for x in sys.stdin.readline().rstrip().split()]

A.append(INF)
A.append(INF)
i, j = 0, 0
t = 0
while i < N or j < M:

    if A[i] < B[j]:
        t += A[i]
        if t > K: break
        i += 1
    else:
        t += B[j]
        if t > K: break
        j += 1

print(i + j)

### FIXED CODE ###

import sys

INF = 10**9 + 5

N, M, K = map(int, sys.stdin.readline().rstrip().split())
A = [int(x) for x in sys.stdin.readline().rstrip().split()]
B = [int(x) for x in sys.stdin.readline().rstrip().split()]

tmpA = [INF] * (N + 1)
tmpA[0] = 0

cntA = 0
# A だけを読み続けた場合の所要時間を記録
for i in range(1, N + 1):
    tmpA[i] = A[i - 1] + tmpA[i - 1]
    cntA = i
    if tmpA[i] > K:
        break

# print(tmpA, cntA)  # cntA 冊目まで読める

# A を一冊ずつ減らして、最大値を探索
j = 0
vol = 0
tmpB = 0

for i in range(cntA, -1, -1):
    rest = K - tmpA[i]  # 残り時間
    # print(f"A{i} 残時間 : {rest}")
    while j < M + 1:
        # print(f"B {j}冊 {tmpB}分")
        if rest < tmpB:  # 　tmpB が残り時間を超えたら終了
            break
        vol = max(i + j, vol)
        if j >= M:
            break
        tmpB += B[j]  # 超えていなければ新しい本を追加してみる
        j += 1

print(vol)