항상 충실하게

from collections import deque

n, m = map(int,input().split())
temp = []
for _ in range(n):
    aaa = input()
    aa = []
    for a in aaa:
        aa.append( int(a))

    temp.append(aa)

# print(temp)
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


visited=[(0,0)]
round = 0
stack = deque ()
stack.append((0,0, 0) )
pointX = 0
pointY = 0
while pointX != n-1 or pointY != m-1:
    pointX, pointY, round =stack.popleft()
    for i in range(4):
        temp_pointX  =pointX+ dx[i]
        if temp_pointX <0 or temp_pointX> n-1:
            continue
        temp_pointY  =pointY+ dy[i]
        if temp_pointY <0 or temp_pointY >m-1:
            continue
        if temp[temp_pointX][temp_pointY] ==0:
            continue
        else:
            temp[temp_pointX][temp_pointY] = 0
            stack.append((temp_pointX, temp_pointY, round+1) )


print(round+1)

n= int(input())

for i in range(n): 
    a = int(input())
    aa = list(map(int,input().split()))
    print(min(aa),max(aa))

aa = []
for i in range(28):
    aa.append(int(input()))
    
dd = list(set([j for j in range(1,31)]) -set(aa))

print(min(dd))
print(max(dd))

cash = int(input())

prices = list(map(int,input().split()))

J = [0,cash]
S = [0,cash]

def J_asset(prices,J):
  for price in prices:
    if J[1]>= price:
        J[0] += J[1]//price
        J[1] = J[1]%price
  
  return prices[-1]*J[0] + J[1]


def S_asset(prices,S):
  for day in range(3, len(prices)):
    if prices[day-3:day][0]<prices[day-3:day][1]<prices[day-3:day][2]:
        S[1] += S[0]*prices[day]
        S[0] = 0
      # print("sell"+str(day))
    
    if prices[day-3:day][0]>prices[day-3:day][1]>prices[day-3:day][2] and S[1] > prices[day]:
        S[0] += S[1]//prices[day]
        S[1] = S[1]%prices[day]
      # print("buy"+str(day))
    # print(J)
  return prices[-1]*S[0] +S[1]

j_asset =J_asset(prices,J)
s_asset =S_asset(prices,S)
# print(j_asset)
# print(s_asset)

if j_asset > s_asset:
    print("BNP")
elif j_asset<s_asset:
    print("TIMING")
else:
    print("SAMESAME")

n = int(input())
temp=0
temp_counter={}
for i in range(n):
    a,b = map(int,input().split())
    if a in list(temp_counter.keys()):
        if b != temp_counter[a]:
            temp +=1
            temp_counter[a]=b
    else:
        temp_counter[a]=b

print(temp)

temp = []
for _ in range(5):
  temp.append(list(map(int,input().split())))

bingo = []
for __ in range(5):
  bingo.append(list(map(int,input().split())))

def bingo_check(temp):
  bingo_count=0
  for line in temp:
    if sum(line) == 0:
      bingo_count +=1

  for i in range(5):
    if temp[0][i]+temp[1][i]+temp[2][i]+temp[3][i]+temp[4][i] ==0:
      bingo_count+=1
  
  if temp[4][0]+temp[3][1]+temp[2][2]+temp[1][3]+temp[0][4] ==0:
    bingo_count+=1
  
  if temp[0][0]+temp[1][1]+temp[2][2]+temp[3][3]+temp[4][4] ==0:
    bingo_count +=1
  
  return bingo_count


def answer_check(bingo, temp):
  answer=0
  for order in bingo:
    for num in order:
      answer+=1
      for i in range(5):
        for j in range(5):
          if temp[i][j] == num:
            temp[i][j] = 0
            if bingo_check(temp)>=3:
              return(answer)

print(answer_check(bingo, temp))

n = int(input())
mine_map=["."*(n+2)]
open_map=["."*(n+2)]
for _ in range(n):
  mine_map.append( "."+ input()+".")
for __ in range(n):
  open_map.append("."+ input()+".")
open_map.append("."*(n+2))
mine_map.append("."*(n+2))

finished = False
temp =[]
for column_num in range(1,n+1):
  for row_num in range(1,n+1):
    if mine_map[column_num][row_num] == "*":
      temp.append((column_num, row_num))
    count =0
    if mine_map[column_num+1][row_num] =="*":
      count += 1
    if mine_map[column_num+1][row_num+1] =="*":
      count += 1
    if mine_map[column_num+1][row_num-1] =="*":
      count += 1
    if mine_map[column_num][row_num+1] =="*":
      count += 1
    if mine_map[column_num][row_num-1] =="*":
      count += 1
    if mine_map[column_num-1][row_num] =="*":
      count += 1
    if mine_map[column_num-1][row_num-1] =="*":
      count += 1
    if mine_map[column_num-1][row_num+1] =="*":
      count += 1
    
    if open_map[column_num][row_num] == "x":
      if mine_map[column_num][row_num] == "*":
        finished = True
      else:
        open_map[column_num]= open_map[column_num][:row_num] + str(count) + open_map[column_num][row_num+1:]

if finished:
  for jj in temp:
    j,k = jj
    open_map[j]= open_map[j][:k] + "*" + open_map[j][k+1:]  

for ii in range(1,n+1):
  print(open_map[ii][1:-1])

quack = input()

next_q ={
  "q":"u",
  "u":"a",
  "a":"c",
  "c":"k",
  "k":"q"
}

temp=[]
printm1=False
for alphabet in quack:
  last_change = " "
  if len(temp)==0 and alphabet =="q":
    temp.append(alphabet)
    continue
  else:
    for temp_index in range(len(temp)):
      if next_q[temp[temp_index][-1]] == alphabet:
        temp[temp_index] += alphabet
        last_change = temp[temp_index]
        break
    if alphabet =="q" and last_change[-1] !="q":
      temp.append("q")
    if alphabet !="q" and last_change==" ":
      printm1 =True

for quackquack in temp:
  if quackquack[-1] !="k":
    printm1=True

if printm1:
  print(-1)

else:
  print(len(temp))