Harryxun/stf_run huggingface dataset:
h,w=map(int,input().split())

m=[input() for i in range(w)]


cnt=[[1000000 for i in range(h)] for j in range(w)]

if m[0][0]=="#":
    cnt[0][0]=1
else:
    cnt[0][0]=0

for y in range(w):
    for x in range(h):
        if x>0:
            if m[y][x-1]=="." and m[y][x]=="#":
                cnt[y][x]=min(cnt[y][x],cnt[y][x-1]+1)
            else:
                cnt[y][x]=min(cnt[y][x],cnt[y][x-1])
        if y>0:
            if m[y-1][x]=="." and m[y][x]=="#":
                cnt[y][x]=min(cnt[y][x],cnt[y-1][x]+1)
            else:
                cnt[y][x]=min(cnt[y][x],cnt[y-1][x])


print(cnt[w-1][h-1])

### FIXED CODE ###

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

m=[input() for i in range(h)]


cnt=[[1000000 for i in range(w)] for j in range(h)]

if m[0][0]=="#":
    cnt[0][0]=1
else:
    cnt[0][0]=0

for y in range(h):
    for x in range(w):
        if x>0:
            if m[y][x-1]=="." and m[y][x]=="#":
                cnt[y][x]=min(cnt[y][x],cnt[y][x-1]+1)
            else:
                cnt[y][x]=min(cnt[y][x],cnt[y][x-1])
        if y>0:
            if m[y-1][x]=="." and m[y][x]=="#":
                cnt[y][x]=min(cnt[y][x],cnt[y-1][x]+1)
            else:
                cnt[y][x]=min(cnt[y][x],cnt[y-1][x])


print(cnt[h-1][w-1])
a, b = map(int, input().split())
s = input()
first, second = s.split("-")
if len(first) == a and len(second) == b:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

a = int(input())
print(48-a)
n,m = map(int,input().split())

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

b = [b for b in a if b >= 1/4/m]

if len(b)>= m:
	print(‘Yes’)
else:
	print(‘No’)

### FIXED CODE ###

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

x = max(a)
s = 0
for i in a:
    s += i
y = [l for l in a if l >=s/4/m]
if len(y) >=m:
    print('Yes')
else:
    print('No')
s = input()
k = int(input())
n = len(s)
l2 = sorted([s[i:i+2] for i in range(n-1)])
l3 = sorted([s[i:i+3] for i in range(n-2)])
l4 = sorted([s[i:i+4] for i in range(n-3)])
l5 = sorted([s[i:i+5] for i in range(n-4)])
out = sorted([min(s),l2[0],l2[1],l2[2],l2[3],l3[0],l3[1],l3[2],l4[0],l4[1],l5[0]])
print(out[k-1])

### FIXED CODE ###

s = input()
k = int(input())
n = len(s)
if n == 1:
    print(s)
elif n == 2:
    l2 = sorted(list(set([s[i:i+2] for i in range(n-1)])))
    print(l2[0])
elif n == 3:
    l1 = list(set(s))
    l2 = list(set([s[i:i+2] for i in range(n-1)]))
    l3 = list(set([s[i:i+3] for i in range(n-2)]))
    out = sorted(l1 + l2 + l3)
    print(out[k-1])
elif n == 4:
    l1 = list(set(s))
    l2 = list(set([s[i:i+2] for i in range(n-1)]))
    l3 = list(set([s[i:i+3] for i in range(n-2)]))
    l4 = list(set([s[i:i+4] for i in range(n-3)]))
    out = sorted(l1 + l2 + l3 + l4)
    print(out[k-1])
else:
    l1 = list(set(s))
    l2 = list(set([s[i:i+2] for i in range(n-1)]))
    l3 = list(set([s[i:i+3] for i in range(n-2)]))
    l4 = list(set([s[i:i+4] for i in range(n-3)]))
    l5 = list(set([s[i:i+5] for i in range(n-4)]))
    out = sorted(l1 + l2 + l3 + l4 + l5)
    print(out[k-1])
def gcd(x, y):
    a_x = list()
    a_y = list()

    for i in range(1, x+1):
        if x % i == 0:
            a_x.append(i)

    for i in range(1, y+1):
        if y % i == 0:
            a_y.append(i)

    a_cd = list(set(a_x).intersection(set(a_y)))

    return max(a_cd)

if __name__ == "__main__":
    x, y = map(int, input().split())
    if x > y:
        tmp = x
        x = y
        y = tmp
    print(gcd(x, y%x))

### FIXED CODE ###

def gcd(x, y):
    if x < y:
        tmp = x
        x = y
        y = tmp

    while y > 0:
        r = x % y
        x = y
        y = r

    return x

if __name__ == "__main__":
    x, y = map(int, input().split())
    print(gcd(x, y))
n,x,t = map(int, input().split())
Y = X
ans = 0
cnt = 1

while X < N:
    X = X + Y
    cnt = cnt + 1
	ans = T * cnt
	print(ans)

### FIXED CODE ###

n, x, t = map(int, input().split())
tm = (n // x) * t 
if (n % x) != 0:
    tm += t
print(tm)
import math as ma


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


a, b = map(int, input().split())

print(lcm(a, b))


### FIXED CODE ###

import fractions

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

a, b = map(int, input().split())

print(lcm(a, b))
in_n, in_cond = map(int, input().split())
def hoge(n, cond):
    for i in range(n+1):
        for j in range(n+1):
            for k in range(n+1):
                if((i + j + k == n) & (10000 * i + 5000 * j + 1000 * k == cond)):
                    return [i, j, k]
    return [-1 -1 -1]
print(" ".join(hoge(in_n, in_cond)))




### FIXED CODE ###

in_n, in_cond = map(int, input().split())
def hoge(n, cond):
    for i in range(n+1):
        for j in range(n + 1 -i):
            if(10000 * i + 5000 * j + 1000 * (n - i - j) == cond):
                return [str(i), str(j), str(n - i - j)]
    return ["-1","-1","-1"]
print(" ".join(hoge(in_n, in_cond)))
import numpy as np

h,w,m = (int(x) for x in input().split())

a = np.zeros( (h,w) )
for i in range(m):
    hi,wi = (int(x) for x in input().split())
    a[hi-1][wi-1] = 1

'''
for i in range(h):
    print(a[i])
'''

Hs = []
greatH = 0
gHs = []
for i in range(h):
    x = np.sum( a[i,:] )
    Hs.append(x)
    if x > greatH:
        greatH = x
for i in range(h):
    if Hs[i] == greatH:
        gHs.append(i)
Ws = []
greatW = 0
gWs = []
for i in range(w):
    x = np.sum( a[:,i] )
    Ws.append(x)
    if x > greatW:
        greatW = x
for i in range(w):
    if Ws[i] == greatW:
        gWs.append(i)

great = greatH + greatW

flag = 1
for i in range( len(gHs) ):
    x = gHs[i]
    for j in range( len(gWs) ):
        y = gWs[j]
        if a[x][y] == 0:
            flag = 0

print( int(great - flag) )


### FIXED CODE ###

import queue
h,w,m = ( int(x) for x in input().split() )

h_array = [ 0 for i in range(h) ]
w_array = [ 0 for i in range(w) ]
ps = set()
for i in range(m):
    hi,wi = ( int(x)-1 for x in input().split() )
    h_array[hi] += 1
    w_array[wi] += 1
    ps.add( (hi,wi) )
h_great = max(h_array)
w_great = max(w_array)
h_greats = list()
w_greats = list()
for i in range( h ):
    if h_array[i] == h_great:
        h_greats.append(i)
for i in range( w ):
    if w_array[i] == w_great:
        w_greats.append(i)

ans = h_great + w_great - 1

escaper = False

for i in range( len(h_greats) ):
    hi = h_greats[i]
    for j in range( len(w_greats) ):
        wi = w_greats[j]
        if (hi,wi) not in ps:
            ans += 1
            escaper = True
            break
    if escaper:
        break

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

N = int(input())
T = [int(input()) for _ in range(N)]
if N == 1:
    print(T)

ans = lcm(T[0] , T[1])
for i in range(2 , N):
    ans = lcm(T[i] , ans)
print(ans)

### FIXED CODE ###

import math


def lcm(a, b):
    return a * b // math.gcd(a, b)


N = int(input())
ans = int(input())
for _ in range(N - 1):
    ans = lcm(ans, int(input()))
print(ans)
def main ():
N = int(input())
A = list(map(int,input().split()))
if 0 in A: print (0)
return
prod = 1 for a in A:
prod *= a
if prod > 1000000000000000000:
print(-1) return
print(prod) main ()

### FIXED CODE ###

a , b = input() . split()
c = int(a) *int(b)
print(c)
A,B,K=map(int,input().split())
list=[]
for i in range(1,min(A,B)+1):
  if A%i==0 and B%i==0 :
    list.append(i)
print(list[len(list)-K+1])

### FIXED CODE ###

A,B,K=map(int,input().split())
list=[]
for i in range(1,min(A,B)+1):
  if A%i==0 and B%i==0 :
    list.append(i)
print(list[len(list)-K])
ar=input().split()
    print(ar.index('0')+1)

### FIXED CODE ###

ar=input().split()
print(ar.index('0')+1)
s = input()

l = [
    "a",
    "b",
    "c",
    "d",
    "e",
    "f",
    "g",
    "h",
    "i",
    "j",
    "k",
    "l",
    "m",
    "n",
    "o",
    "p",
    "q",
    "r",
    "s",
    "t",
    "u",
    "v",
    "w",
    "x",
    "y",
]

print(l[l.index(s)+1])

### FIXED CODE ###

s = input()

l = [
    "a",
    "b",
    "c",
    "d",
    "e",
    "f",
    "g",
    "h",
    "i",
    "j",
    "k",
    "l",
    "m",
    "n",
    "o",
    "p",
    "q",
    "r",
    "s",
    "t",
    "u",
    "v",
    "w",
    "x",
    "y",
    "z"
]

print(l[l.index(s)+1])
import bisect
n,k = map(int,input().split())
a = list(map(int,input().split()))
a.sort()
zero = bisect.bisect_left(a,0)
cnt = min(-sum(a[zero-k:zero]),sum(a[zero:zero+k+1]))
for i in range(1,k):
    if cnt > -2*a[zero-i]+a[zero+k-i-1]:
        cnt = -2*a[zero-i]+a[zero+k-i-1]
    else:
        break
for i in range(1,k):
    if cnt > -a[zero-k+i]+2*a[zero+k-1]:
        cnt = -a[zero-k+i]+2*a[zero+k-1]
    else:
        break
print(cnt)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
c=10**10
for i in range(n-k+1):
    c=min(c,-a[i]+a[i+k-1]\
          +min(abs(a[i]),abs(a[i+k-1])))
print(c)
# dict形式で既出分をもたせる
N, Q = map(int, raw_input().split())
string = raw_input()
a = []
for i in range(Q):
    a.append(map(int, raw_input().split()))
test_dict = {}
result = ''
for temp in a:
    if test_dict.get(string[temp[0]-1:temp[1]]):
        result += '\n' + str(test_dict.get(string[temp[0]-1:temp[1]]))
        continue
    test_dict[string[temp[0]-1:temp[1]]] = string[temp[0]-1:temp[1]].count('AC')
    result += '\n' + str(test_dict[string[temp[0]-1:temp[1]]])
print(result)

### FIXED CODE ###

N, Q = map(int, raw_input().split())
string = raw_input()
cnt = [0]
for i in range(N):
#    print(i)
#    print(string[i-2:i])
#    if i == 0:
#        cnt.append(0)
#        continue
    if string[i-1:i+1] == 'AC':
        cnt.append(cnt[i]+1)
        continue
    cnt.append(cnt[i])

for j in range(Q):
    #print(j)
    pare = map(int, raw_input().split())
    print(cnt[pare[1]] - cnt[pare[0]])
n,m=map(int,input().split())
a=[0]*(n+1)
b=[int(input()) for i in range(m)]
a[0]=1
j=0
if b[0]==1:
  a[1]=0
  if j!=1:
    j=1
else:
  a[1]=1
for i in range(2,n+1):
  if i==b[j]:
    if j<m-1:
      j+=1
  else:
    a[i]=(a[i-1]+a[i-2])%(10**9+7)
print(a[n])

### FIXED CODE ###

n,m=map(int,input().split())
a=[0]*(n+1)
b=[int(input()) for i in range(m)]
a[0]=a[1]=1
if m==0:
  for i in range(2,n+1):
    a[i]=(a[i-1]+a[i-2])%(10**9+7)
else:
  j=0
  if b[0]==1:
    a[1]=0
    if m>1:
      j=1
  for i in range(2,n+1):
    if i==b[j]:
      if j<m-1:
        j+=1
    else:
      a[i]=(a[i-1]+a[i-2])%(10**9+7)
print(a[n])
import sys, math
from functools import lru_cache
from collections import defaultdict
from decimal import Decimal
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    S = input()
    if S == 'zyxwvutsrqponmlkjihgfedcba':
        print(-1)
        return

    l = [0]*26
    for c in S:
        l[ord(c)-ord('a')] += 1

    if len(S) < 26:
        i = l.index(0)
        print(S+chr(i+ord('a')))
        return

    for i in range(len(S)):
        if S[i] > S[i+1]:
            break

    c = min(S[i+1:])
    print(S[:i-1]+c)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys, math
from functools import lru_cache
from collections import defaultdict
from decimal import Decimal
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

def mi():
    return map(int, input().split())

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    S = input()
    if S == 'zyxwvutsrqponmlkjihgfedcba':
        print(-1)
        return

    l = [0]*26
    for c in S:
        l[ord(c)-ord('a')] += 1

    if len(S) < 26:
        i = l.index(0)
        print(S+chr(i+ord('a')))
        return

    for i in range(len(S)-1, 0, -1):
        if S[i-1] < S[i]:
            break

    c = min(S[j] for j in range(i, len(S)) if S[j] > S[i-1])
    print(S[:i-1]+c)

if __name__ == '__main__':
    main()
dp[0][1][1]=int(n[0])-1
dp[0][1][0]=1
dp[0][0][1]=1

for i in range(1,l):
  for j in range(4):
    b=i-1
    now=int(n[i])
    if now==0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
    dp[i][j][1]+=dp[b][j][1]
    dp[i][j+1][1]+=9*dp[b][j][1]
print(dp[l-1][k][0]+dp[l-1][k][1])


### FIXED CODE ###

n=input()
k=int(input())
l=len(n)
dp=[[[0 for _ in range(2)] for _ in range(5)] for _ in range(l+1)]
dp[0][1][1]=int(n[0])-1
dp[0][1][0]=1
for i in range(1,l):
  for j in range(4):
    b=i-1
    now=int(n[i])
    if now==0:
      dp[i][j][0]+=dp[b][j][0]
    else:
      dp[i][j][1]+=dp[b][j][0]
      dp[i][j+1][1]+=dp[b][j][0]*(now-1)
      dp[i][j+1][0]+=dp[b][j][0]
    dp[i][j][1]+=dp[b][j][1]
    dp[i][j+1][1]+=dp[b][j][1]*9
  dp[i][1][1]+=9
print(dp[l-1][k][0]+dp[l-1][k][1])
N = int(input())
V = input().split()
C = input().split()
i = int(0)
if i < N:
    if V[i] - C[i] > 0:
        value = value + V[i] - C[i]
        i += 1
print(value)

### FIXED CODE ###

N = int(input())
V = input().split()
C = input().split()
value = int(0)
i = int(0)
for i in range(N):
    if int(V[i]) > int(C[i]):
        add = int(V[i]) - int(C[i])
        value = value + add
    i = i + 1
print(value)
N,D=map(int,input().split())
X = []
for i in range(N):
  X.append(input().split())
c=0
for n in range(0,N-1):
  for m in range(n+1,N):
    a=0
    for j in range(0,D):
      a=a+int((int(X[n][j])-(int(X[m][j])**2)
    if (int(a**(1/2)))**2==a:
      c=c+1
print(c)

### FIXED CODE ###

n,d=map(int,input().split())
X=[[]*d for i in range(n)]
for i in range(n):
  X[i]=list(map(int,input().split()))
b=0
for i in range(n-1):
  for j in range(i+1,n):
    a=0
    for k in range(d):
      a=a+(X[i][k]-X[j][k])**2
      a=float(a)
    if a**(1/2)==int(a**(1/2)):
      b=b+1
print(b)
K, X = int(input())
wealth = 500 * K
if K >= X:
  print('Yes")
else:
  print('No')

### FIXED CODE ###

K, X = map(int, input().split())
wealth = 500 * K
if wealth >= X:
    print('Yes')
else:
    print('No')
n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [2*10**4]*n*k
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
      dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
print(dp[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [2**60 for i in range(110000)]
dp[0] = 0
for i in range(n):
    for j in range(1,k+1):
        if i+j < n:
            dp[i+j] = min(dp[i+j], dp[i]+abs(h[i+j]-h[i]))
print(dp[n-1])
T = []
for i in range(5):
    T.append(input())
tmp = []
for i in range(5):
    tmp.append(10 - int(T[i][-1]))
minlist = []
for i in range(5):
    if tmp[i] > 4:
        minlist.append(tmp[i])
    else:
        minlist.append(10)
last = tmp.index(min(minlist))
tmp2 = [0 if x == 10 else x for x in tmp]
ans = []
for i in range(5):
    ans.append(tmp2[i] + int(T[i]))
print(sum(ans) - ans[last] + int(T[last]))

### FIXED CODE ###

T = []
for i in range(5):
    T.append(input())
tmp = []
for i in range(5):
    tmp.append(int(T[i][-1]))
T2 = []
for i in range(5):
    if tmp[i] != 0:
        T2.append(int(T[i]) + 10 - tmp[i])
    else:
        T2.append(int(T[i]))
ans = []
for i in range(5):
    if tmp[i] != 0:
        ans.append(sum(T2) - 10 + tmp[i])
    else:
        ans.append(sum(T2))
    
    
    
    

print(min(ans))
#coding: utf-8
times= int(input())
a= 1
if 0 in times:
  print(0)
for i in list(map(int, input().split())):
  a*= i
  if a > 10**18:
    print('-1')
else:
  print(a)

### FIXED CODE ###

#coding: utf-8
times= int(input())
nums= list(map(int, input().split()))
a= 1
if 0 in nums:
  print(0)
  exit()
for i in nums:
  a*= i
  if a > 10**18:
    print('-1')
    exit()
else:
  print(a)
INF = 10 ** 20
 
N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0
 
for i in range(1,N+1):
	for coin in coin_list:
    	if i-coin >= 0: dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])

### FIXED CODE ###

INF = 10 ** 20

N = int(input())
coin_list = [1] + [6**i for i in range(1, 7)] + [9**i for i in range(1, 6)]
dp = [INF]*(N+1)
dp[0] = 0
 
for coin in coin_list:
    for i in range(coin,N+1):
        dp[i] = min(dp[i], dp[i-coin]+1)
 
print(dp[N])
print(min(b//a,c))

### FIXED CODE ###

a,b,c = map(int,input().split())
print(min(b//a,c))
n = int(input())
l = list(map(int, input().split()))
l.reverse()

for i in range(n):
	if i >= 1:
		print(" ", end = '')
	print(a[i], end = '')
print()


### FIXED CODE ###

#
# 6a
#

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    print(*a)


if __name__ == '__main__':
    main()
N, A, B, C, D = map(int, input().split())
S = str(input())

Sarr = [True if s == '.' else False for s in S]
#print(Sarr)

def canmove(st):
  global N, Sarr
  can = [False] * N
  can[st-1] = True
  for i in range(st, N):
    if Sarr[i]:
      if can[i-1] or can[i-2]:
        can[i] = True
  return can

Acan = canmove(A)
Bcan = canmove(B)
#print(Acan)
#print(Bcan)

ans = Acan[C-1] and Bcan[D-1]
#print(ans)

def canpass(st, ed):
  global Sarr
  for i in range(st, ed-1):
    if Sarr[i] and Sarr[i+1] and Sarr[i+2]:
      return True
  return False

if C > D:
  ans = ans and canpass(B-1, D+1)
#print(ans)

if ans:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

N, A, B, C, D = map(int, input().split())
S = str(input())

Sarr = [True if s == '.' else False for s in S]
#print(Sarr)

def canmove(st):
  global N, Sarr
  can = [False] * N
  can[st-1] = True
  for i in range(st, N):
    if Sarr[i]:
      if can[i-1] or can[i-2]:
        can[i] = True
  return can

Acan = canmove(A)
Bcan = canmove(B)
#print(Acan)
#print(Bcan)

ans = Acan[C-1] and Bcan[D-1]
#print(ans)

def canpass(st, ed):
  global Sarr
  for i in range(st, ed-1):
    if Sarr[i] and Sarr[i+1] and Sarr[i+2]:
      return True
  return False

if C > D:
  ans = ans and canpass(B-2, D)
#print(ans)

if ans:
  print('Yes')
else:
  print('No')
num = input()

print(num ** 3)


### FIXED CODE ###

num_str = input()
num = int(num_str)
print(num ** 3)
N = int(input())
S = input()
h = N/2
if S[0:h] == S[h:N]
	return Yes
return No

### FIXED CODE ###

N = int(input())
S = input()
h = int(N/2)
if S[0:h] == S[h:N]:
    print("Yes")
else:
    print("No")
n = int(input())
c0 = c1 = c2 = c3 = 0
for _ in range(n):
  s = input()
  if s == "AC":
    c0 += 1
  elif s == "WA":
    c1 += 1
  elif s == "TLE":
    c2 += 1
  else
  	c3 += 1

print("AC x", c0, sep = " ")
print("WA x", c1, sep = " ")
print("TLE x", c2, sep = " ")
print("RE x", c3, sep = " ")


### FIXED CODE ###

N = int(input())
s = [input() for i in range(N)]
for v in ['AC', 'WA', 'TLE', 'RE']:
    print('{} x {}'.format(v, s.count(v)))
import math
A,B,N= map(int,input().split())
x=[]
AB=A/B
if N<=B:
    #x.append(math.floor(AB*N-1)-A*(N//B)
    print(math.floor(AB*N-1)-A*(N//B)
else:
    print(math.floor(AB*B-1)

### FIXED CODE ###

import math
A,B,N= map(int,input().split())
x=[]
AB=A/B
if B==1:
    print("0")
elif N<B:
    #x.append(math.floor(AB*N-1)-A*(N//B)
    print(math.floor(AB*N))
else:
    x=[math.floor(AB*N)-A*(N//B)]
    for i in range(N//B):
        x.append(math.floor(AB*((i+1)*B-1))-i)
    print(max(x))
print x*x*x

### FIXED CODE ###

A=int(input())
print A**3
import bisect
n = int(input())
a = [0]+list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)

m = 10**18
dp = [m]*(n+1)
ans = [1]*(n+1)
checked = [False]*(n+1)
checked[1] = True
changes = []

def search(x):
    ind = bisect.bisect_left(dp,a[x])
    changes.append((ind,dp[ind]))
    dp[ind] = a[x]
    ans[x] = bisect.bisect_left(dp,m)
    
    for i in t[x]:
        if not checked[i]:
            checked[i] = True
            search(i)
    
    b,c = changes.pop()
    dp[b] = c
    
search(1)
for i in ans[1:]:
    print(i)

### FIXED CODE ###

import bisect
import sys
sys.setrecursionlimit(10**7)

n = int(input())
a = [0]+list(map(int,input().split()))
t = [[] for _ in range(n+1)]
for _ in range(n-1):
    u,v = map(int,input().split())
    t[u].append(v)
    t[v].append(u)

m = 10**18
dp = [m]*(n+1)
ans = [1]*(n+1)
checked = [False]*(n+1)
checked[1] = True
changes = []

def search(x):
    ind = bisect.bisect_left(dp,a[x])
    changes.append((ind,dp[ind]))
    dp[ind] = a[x]
    ans[x] = bisect.bisect_left(dp,m)
    
    for i in t[x]:
        if not checked[i]:
            checked[i] = True
            search(i)
    
    b,c = changes.pop()
    dp[b] = c
    
search(1)
for i in ans[1:]:
    print(i)
n,k=map(int,input().split())
s=list(input())
s=list(map(int,s))
stack=[]
tmp=1
flag=True
for i in range(1,len(s)):
  if s[i]!=s[i-1]:
    stack.append(tmp)
    tmp=1
  else:
    tmp+=1
stack.append(tmp)
left=[0]
right=[0]
tmp=0
if s[0]==0:
  flag=False
  if len(stack)%2==1:
    stack.append(0)
  if len(stack)//2<=k:
    print(len(s))
    exit()
else:
  flag=True
  if len(stack)%2==0:
    stack.append(0)
  if len(stack)//2<=k:
    print(len(s))
    exit()
for i in range(len(stack)):
  tmp+=stack[i]
  if i%2==0:
    if flag:
      right.append(tmp)
    else:
      left.append(tmp)
  else:
    if flag:
      left.append(tmp)
    else:
      right.append(tmp)
ans=0
for i in range(len(right)-k):
  ans=max(ans,right[i+k]-left[i])
print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
print(max(a+a-1,b+b-1,a+b))
while True:
    H,W= map(int, input().split())
    s = "#"
    for i in range(H):
        if H==0 and W==0:
            break
        else:
            x = s*W
            print(x)
    print("")        
              

### FIXED CODE ###

while True:
    H,W= map(int, input().split())
    if H==0 and W==0:
        break
    s = "#"
    for i in range(H):        
        x = s*W
        print(x)
    print("")
judge = 'Yes'
n = int(input())
txy_l = [0]
for i in range(n):
    txy_l.append(list(map(int,input().split())))

for i in range(n):
    t_dif = txy_l[i+1][0] - txy_l[i][0]
    x_dif = txy_l[i+1][1] - txy_l[i][1]
    y_dif = txy_l[i+1][2] - txy_l[i][2]
    spare_time = t_dif - (abs(x_dif)+abs(y_dif))
    if spare_time < 0 or spare_time%2 != 0:
        judge = 'No'

print(judge)

### FIXED CODE ###

judge = 'Yes'
n = int(input())
txy_l = [[0,0,0]]
for _ in range(n):
    txy_l.append(list(map(int,input().split())))

for i in range(n):
    t_dif = txy_l[i+1][0] - txy_l[i][0]
    x_dif = txy_l[i+1][1] - txy_l[i][1]
    y_dif = txy_l[i+1][2] - txy_l[i][2]
    spare_time = t_dif - (abs(x_dif)+abs(y_dif))
    if spare_time < 0 or spare_time%2 != 0:
        judge = 'No'

print(judge)