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

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    # 全ルートの中で、連続する#の数が一番少ないものを探す

    ans = [H+W]
    dir = ((1, 0), (0, 1))
    # 前の色、前の進行方向、今までの連続ブロックの数
    
    def dfs(x, y, pw, pd, cnt):
        if x==W-1 and y==H-1:
            if pw=='.' and s[y][x]=='#':
                cnt += 1
            ans[0] = min(cnt, ans[0])
            if ans[0]==0:
                print(ans[0])
                sys.exit()
        else:
            for d in dir:
                nx = x+d[0]
                ny = y+d[1]
                if nx<W and ny<H:
                    ncnt = cnt
                    # 前が白で今が黒
                    if pw=='.' and s[y][x]=='#':
                        ncnt += 1
                    dfs(nx, ny, s[y][x], d, ncnt)

    dfs(0, 0, '.', dir[0], 0)
    print(ans[0])

if __name__ == '__main__':
    resolve()

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip() 

def resolve():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]

    ans = [[0]*W for _ in range(H)]
    if s[0][0]=='#':
        ans[0][0] = 1
    for i in range(1, W+H-1):
        for y in range(max(0, i-(W-1)), min(i+1, H)):
            x = i-y
            if y==0:
                if s[y][x-1]=='.' and s[y][x]=='#':
                    ans[y][x] = ans[y][x-1] + 1
                else:
                    ans[y][x] = ans[y][x-1]
            elif x==0:
                if s[y-1][x]=='.' and s[y][x]=='#':
                    ans[y][x] = ans[y-1][x] + 1
                else:
                    ans[y][x] = ans[y-1][x]
            else:
                if s[y][x]=='#':
                    ans[y][x] = min(ans[y-1][x]+(1 if s[y-1][x]=='.' else 0), ans[y][x-1]+(1 if s[y][x-1]=='.' else 0))
                else:
                    ans[y][x] = min(ans[y-1][x], ans[y][x-1])
    print(ans[-1][-1])

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

#E

import math

INF=float('inf')
ans1='pairwise coprime'
ans2='setwise coprime'
ans3='not coprime'

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

g=math.gcd(A[0],A[1])
for i in range(2,n):
  g=math.gcd(g,A[i])

if g!=1:
  print(ans3)
else:
  for i in range(n):
    for j in range(n):
      if i==j:
        continue
      if math.gcd(A[i],A[j])!=1:
        print(ans2)
        exit()
  print(ans1)

### FIXED CODE ###

import math

INF=float('inf')
ans1='pairwise coprime'
ans2='setwise coprime'
ans3='not coprime'

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

P=[0]*(10**6+1)
for i in A:
  P[i]+=1

pairwise=True
for i in range(2,10**6+1):
  cnt=0
  for j in range(i,10**6+1,i):
    cnt+=P[j]
  if cnt>1:
    pairwise=False
    break

if pairwise:
  print(ans1)
  exit()
  
g=math.gcd(A[0],A[1])
for i in A:
  g=math.gcd(g,i)

if g==1:
  print(ans2)
else:
  print(ans3)
### BUGGY CODE ###

import bisect as bi
import sys
import heapq as hq
input = sys.stdin.readline

n,m = map(int,input().split())
a = list(map(int,input().split()))
b = [0] * m
for i in range(m):
    b[i] = list(map(int,input().split()))

ans = 0
for i in range(n):
  a[i] = -a[i]
#b.sort(key=itemgetter(1),reverse=True)
for i in b:
  for j in range(i[0]):
    a.append(-i[1])

hq.heapify(a)

for i in range(n):
  ans -= hq.heappop(a)
print(ans)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from operator import itemgetter

N,M = map(int,readline().split())
A = list(map(int,readline().split()))
m = map(int,read().split())
BC = list(zip(m,m))

BC.sort(key = itemgetter(1),reverse=True)

BC.append((N,-1))

change = []
for b,c in BC:
    change += [c] * b
    if len(change) > N:
        break

A += change
A.sort()
answer = sum(A[-N:])
print(answer)
### BUGGY CODE ###

X, K, D = map(int, input().split())
ans = float('inf')
for bit in range(2**K):
    ans_pre = X
    for i in range(K):
        if bit & (1<<i):
            ans_pre += D
        else:
            ans_pre -= D
            
    ans = min(ans, abs(ans_pre))
    
print(ans)

### FIXED CODE ###

X, K, D = map(int, input().split())

low = 0
high = K

while low <= high:
    mid = (low + high) //2
    i = mid
    j = K-mid
    ans_pre = (X + D*i - D*j)
    if ans_pre > 0:
        high = mid-1
    else:
        low = mid+1
        

if low > K :
    low = high
if high < 0:
    high = low
    
ans_h = min(abs((X + D*high - D*(K-high))), abs(X + D*(K-high)-D*high))
ans_l = min(abs((X + D*low - D*(K-low))), abs(X + D*(K-low)-D*low))
    
print(min(ans_l, ans_h))
### BUGGY CODE ###

H, W = [int(_) for _ in input().split()]

S = [input() for _ in range(H)]
memo = [[0] * W for _ in range(H)]

for h in range(H):
    done = [False] * W
    for w in range(W):
        if S[h][w] == '#': continue
        if done[w]: continue

        tmp = w
        cnt = 0
        while tmp < W:
            if S[h][tmp] == '#': break
            cnt += 1
            tmp += 1

        for i in range(w, tmp):
            memo[h][i] += cnt
            done[i] = True

for w in range(W):
    done = [False] * H
    for h in range(H):
        if S[h][w] == '#': continue
        if done[h]: continue

        tmp = h
        cnt = 0
        while tmp < H:
            if S[tmp][w] == '#': break
            cnt += 1
            tmp += 1

        for i in range(h, tmp):
            memo[i][w] += cnt
            done[i] = True

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, memo[i][j] - 1)
print(ans)


### FIXED CODE ###

H, W = [int(_) for _ in input().split()]

S = [input() for _ in range(H)]
memo = [[0] * W for _ in range(H)]

for h in range(H):
    done = [False] * W
    for w in range(W):
        if S[h][w] == '#': continue
        if done[w]: continue

        tmp = w
        cnt = 0
        while tmp < W:
            if S[h][tmp] == '#': break
            cnt += 1
            tmp += 1

        for i in range(w, tmp):
            memo[h][i] += cnt
            done[i] = True

for w in range(W):
    done = [False] * H
    for h in range(H):
        if S[h][w] == '#': continue
        if done[h]: continue

        tmp = h
        cnt = 0
        while tmp < H:
            if S[tmp][w] == '#': break
            cnt += 1
            tmp += 1

        for i in range(h, tmp):
            memo[i][w] += cnt
            done[i] = True

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, memo[i][j] - 1)
print(ans)
### BUGGY CODE ###

n, q = map(int, input().split(' '))
import sys
sys.setrecursionlimit(10**7)

visit = [0 for _ in range(n)]
point = [0 for _ in range(n)]
dic = [[] for _ in range(n)]

def add_p(num):
    if visit[num] == 1:
        return 0
    visit[num] = 1
    for i in dic[num]:
        if visit[i] == 0:
            point[i] += point[num]
            add_p(i)
    return 0

for _ in range(n-1):
    a, b = map(int, input().split(' '))
    dic[a-1].append(b-1)
    dic[b-1].append(a-1)
for _ in range(q):
    p, x = map(int, input().split(' '))
    point[p-1] += x

add_p(0)

print(*point)


### FIXED CODE ###

def main():
    n, q = map(int, input().split(' '))
    import sys
    from collections import deque
    sys.setrecursionlimit(10**7)

    visit = [True for _ in range(n)]
    point = [0 for _ in range(n)]
    dic = [[] for _ in range(n)]
    for _ in range(n-1):
        a, b = map(int, input().split(' '))
        dic[a-1].append(b-1)
        dic[b-1].append(a-1)
    for _ in range(q):
        p, x = map(int, input().split(' '))
        point[p-1] += x
    next_visit = deque()
    next_visit.append(0)
    visit[0] = False
    counter = 1
    while counter < n:
        t = next_visit.pop()
        for s in dic[t]:
            if visit[s]:
                point[s] += point[t]
                visit[s] = False
                counter += 1
                next_visit.append(s)
    print(*point)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

if not 1 in (a):
  print(-1)
else:
  ans = 1
  for i in range(1, n+1):
    idx = a.index(i)
    ans += len(a[:idx]) - 1
    a = a[idx:]
  
    if not i+1 in a:
      print(ans + len(a) - 1)
      break

### FIXED CODE ###

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

ans = n
check = 1
for i in range(n):
  if a[i] == check:
    ans -= 1
    check += 1
if ans == n:
  ans = -1

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

s = list(input())

minLength = 4
maxLength = len(s)
cnt = 0

skipFlag = 0
skipFlag2 = 0

for length in range(minLength,maxLength+1):
    for position in range(maxLength - length + 1):
        if skipFlag > 0:
            skipFlag += 1
            if skipFlag == 4:
                skipFlag = 0
            continue
        if skipFlag2 > 0:
            skipFlag2 += 1
            if skipFlag2 == 2:
                skipFlag2 = 0
            continue
        num = int(''.join(s[position:position+length]))
        if num % 3 == 0:
            if num % 673 == 0:
                cnt += 1
                skipFlag = 1
            else:
                skipFlag2 = 1

print(cnt)

### FIXED CODE ###

s = list(input())
mods = [0]*(len(s))
countRemainder = [0] * 2019
cnt = 0


m = 1
mod = 0
for i in range(len(s)):
    mod += int(s[len(s) - i - 1]) * m

    mod %= 2019
    m *= 10
    m %= 2019

    countRemainder[mod] += 1

countRemainder[0] += 1

for i in range(2019):
    cnt += int(countRemainder[i] * (countRemainder[i] - 1) / 2)

print(cnt)
### BUGGY CODE ###

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

C=[input().split() for i in range(N)]

CX=[]
for i in C:
    for j in i:
        try:CX.append(int(j))

        except ValueError:
            pass

CA=[]
CB=[]
i=0

for k in CX:

    if (i+2)%2==0:
        CA.append(CX[i])
    else:
        CB.append(CX[i])
    i+=1



k=0
l=0#何番目の店
m=0#その店で買う数
money=0
X=0#持ち数

while M>X:
    Min=int(C[0][0])
    for i in C:#どの店で買うか
        if Min>=int(i[0]):
            Min=int(i[0])
            l=k
        k+=1
    
    for x in range(int(C[l][1])):#何個かえるか

        m+=1
        if M==X+m:#max
            money+=m*Min
            print(money)
            break


    money+=m*Min
    X+=m

    C.pop(l)#取り出す
    #リセット
    k=0
    l=0
    m=0#その店で買う数


### FIXED CODE ###

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

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

B.sort()

k=0
l=0#何番目の店
m=0#その店で買う数
money=0
X=0#持ち数
for a,b in B:
    if(M<=0):
        break
    if(b<=M):
        money+=a*b
    else:
        money+=M*a
    M-=b
print(money)
### BUGGY CODE ###

import sys

n = int(input())
a=sys.stdin.readline().rstrip().split()
 
ans=1
 
for i in a:
    ans=ans*int(i)
 
if ans>1000000000000000000:
    print("-1")
else:
    print(ans)

### FIXED CODE ###

import sys

def main():
    n = int(input())
    a=sys.stdin.readline().rstrip().split()
    if '0' in a:
        print(0)
        return
    ans=1
 
    for i in a:
        ans=ans*int(i)
        if ans>1000000000000000000:
            print("-1")
            return
    else:
        print(ans)
main()
### BUGGY CODE ###

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[100001 for i in range(N + 1)] for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
    for k in range(N + 1):
        for i in range(N + 1):
            for j in range(N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(range(1, min(N + 1, 9))):
        move = 0
        flag = {i: 1 for i in RR}
        for i in range(min(N - 1, 8)):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
            flag[a] = flag[b] = 0
            if sum(flag.values()) == 0: break
        ans = min(ans, move)

    print(ans)

main()


### FIXED CODE ###

import itertools

def main():
    N, M, R = map(int, input().split())
    RR = tuple(map(int, input().split()))
    ABC = {tuple(map(int, input().split())) for _ in range(M)}

    dist = [[float('inf')] * (N + 1) for j in range(N + 1)]
    for a, b, c in ABC:
        dist[a][b] = dist[b][a] = c
        dist[a][a] = dist[b][b] = 0
    for k in range(1, N + 1):
        for i in range(1, N + 1):
            for j in range(1, N + 1):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

    ans = float('inf')
    for r in itertools.permutations(RR):
        move = 0
        for i in range(R - 1):
            a = r[i]
            b = r[i+1]
            move += dist[a][b]
        ans = min(ans, move)

    print(ans)

main()
### BUGGY CODE ###

N = int(input())
H = list(map(int, input().split()))
count = 0

for i in range(N-1):
  moving = 0
  for j in range(i, N-1):
    if H[j] >= H[j+1]:
      moving += 1
    else:
      break
      
    if moving > count:
      count = moving
      
print(count)

### FIXED CODE ###

N = int(input())
H = list(map(int, input().split()))
count = 0
i = 0

while i < N-1:
  moving = 0
  for j in range(i, N-1):
    if H[j] >= H[j+1]:
      moving += 1
    else:
      i = j + 1
      break
      
    if moving > count:
      count = moving
      
    i += 1
      
print(count)
### BUGGY CODE ###

def main():
    INF = 2**60
    N, M = map(int, input().split())
    XYZ = [list(map(int, input().split())) for _ in range(N)]

    sgn = [[1,1,1], [1,1,-1],[1,-1,1],[1,-1,-1],[-1,1,1],[-1,1,-1],[-1,-1,1],[-1,-1,-1]]
    ans = -INF 
    for a, b, c in sgn:
        dp = [-INF]*(M+1)
        dp[0] = 0
        for x, y, z in XYZ:
            for j in range(M-1, -1, -1):
                # if dp[j] == -INF: continue
                s = dp[j]+ a*x + b*y + c*z
                if s > dp[j+1]:
                    dp[j+1] = s
        if dp[M] > ans:
            ans = dp[M]
    print(ans)

main()


### FIXED CODE ###

import sys

def main():
    INF = -2**60
    N, M = map(int, sys.stdin.buffer.readline().split())
    XYZ = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(N)]

    sgn = [[1,1,1], [1,1,-1],[1,-1,1],[1,-1,-1],[-1,1,1],[-1,1,-1],[-1,-1,1],[-1,-1,-1]]
    ans = INF 
    for a, b, c in sgn:
        dp = [INF]*(M+1)
        dp[0] = 0
        for x, y, z in XYZ:
            for j in range(M-1, -1, -1):
                if dp[j] == INF: continue
                s = dp[j]+ a*x + b*y + c*z
                if s > dp[j+1]:
                    dp[j+1] = s
        if dp[M] > ans:
            ans = dp[M]
    print(ans)

main()
### BUGGY CODE ###

N, Q  = map(int, input().split())
S = list(input())
ans = [0] * Q
A = 0

for i in range(Q):
  L, R = map(int, input().split())
  A = 0
  SS = S[L-1:R]
  for j in range(len(SS)-1):
    if SS[j] == "A" and SS[j+1] == "C":
      A += 1
  ans[i] = A

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

### FIXED CODE ###

N, Q  = map(int, input().split())
S = list(input())
Lsub = [0]
Rsub = [0]
L = 0
R = 0


for k in range(1,N):
  if S[k-1] == "A" and S[k] == "C":
    L += 1
  Lsub.append(L)

for j in range(0,N-1)[::-1]:
  if S[j] == "A" and S[j+1] == "C":
    R += 1
  Rsub.append(R)


for i in range(Q):
  L, R = map(int, input().split())
  print(Rsub[N-1] - Lsub[L-1] - Rsub[N-R])
### BUGGY CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return divisors # sortしたリストで欲しい時はsorted(divisors)



ret = 0
a = make_divisors(n)
for k in a:
    if k == 1:
        continue
    m = n
    while m >= k:
        if m % k == 0:
            m //= k
        else:
            m -= k
    if m == 1:
        ret += 1

s = make_divisors(n - 1)
s.discard(1)
print(ret + len(s))


### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

n = I()
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return divisors # sortしたリストで欲しい時はsorted(divisors)

ret = 0
a = make_divisors(n)
for k in a:
    if k == 1:
        continue
    m = n
    while m % k == 0:
        m //= k
    if m % k == 1:
        ret += 1

s = make_divisors(n - 1)
s.discard(1)
print(ret + len(s))
### BUGGY CODE ###

def f():
    N, Y = map(int, input().split())
    
    y1 = 10000
    y2 = 5000
    y3 = 1000
    
    y1_num = 0
    y2_num = 0
    y3_num = 0
    for y1_num in reversed(range(N+1)):
        y2_num = 0
        remain_Y1 = Y - y1*y1_num
        if remain_Y1 == 0 and sum([y1_num, y2_num, y3_num]) == N:
            return print(y1_num, y2_num, y3_num)
        elif remain_Y1 < 0:
            continue
        else:
            for y2_num in reversed(range(N+1 - y1_num)):
                y3_num = 0
                remain_Y2 = remain_Y1 - y2*y2_num
                if remain_Y2 == 0 and sum([y1_num, y2_num, y3_num]) == N:
                    return print(y1_num, y2_num, y3_num)
                elif remain_Y2 < 0:
                    continue
                else:
                    for y3_num in reversed(range(N+1 - y1_num - y2_num)):
                        remain_Y3 = remain_Y2 - y3*y3_num
                        if remain_Y3 == 0 and sum([y1_num, y2_num, y3_num]) == N:
                            return print(y1_num, y2_num, y3_num)
                        elif remain_Y3 < 0:
                            continue
    return print(-1, -1, -1)
                        
f()
      

### FIXED CODE ###

def f():
    N, Y = map(int, input().split())
    
    y1 = 10000
    y2 = 5000
    y3 = 1000
    
    y1_num = 0
    y2_num = 0
    y3_num = 0
    for y1_num in reversed(range(N+1)):
        y2_num = 0
        remain_Y1 = Y - y1*y1_num
        if remain_Y1 == 0 and sum([y1_num, y2_num, y3_num]) == N:
            return print(y1_num, y2_num, y3_num)
        elif remain_Y1 < 0:
            continue
        else:
            for y2_num in reversed(range(N+1 - y1_num)):
                y3_num = N - y1_num - y2_num
                remain_Y2 = remain_Y1 - y2*y2_num - y3*y3_num
                if remain_Y2 == 0 and sum([y1_num, y2_num, y3_num]) == N:
                    return print(y1_num, y2_num, y3_num)
                elif remain_Y2 < 0:
                    continue
    return print(-1, -1, -1)
                        
f()
### BUGGY CODE ###

# DP
def main():
    from builtins import max

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

    dp = [-1] * (W + 1)
    dp[0] = 0
    max_w = 0
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(min(max_w, W - w), -1, -1):
            dpj = dp[j]
            if dpj != -1:
                jw = j + w
                dp[jw] = max(dp[jw], dpj + v)
            max_w = max(max_w, jw)
    print(max(dp))


main()


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

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

ans = [0 for _ in range(b)]

for i in range(b):
    ans[i] = (a*i // b - a * (i // b))
    
ans = ans[:n+1] if n < b else ans

print(max(ans))

### FIXED CODE ###

a,b,n = [int(i) for i in input().split()]
 
x = min(n,b-1)
print(a*x // b)
### BUGGY CODE ###

h,w = map(int,input().split())
ch,cw = map(int,input().split())
dh,dw = map(int,input().split())
road_map = []
count_road = 0
for i in range(h):
    road = input()
    road_map.append(road)
    count_road = road.count(".")

queue = [[ch-1,cw-1,0]]
used_map = [[-1]*w for _ in range(h)]

while queue != []:
    dot = queue.pop(0)
    if dot[0] < 0 or dot[1] < 0 or dot[0] >= h or dot[1] >= w:
        continue
    if used_map[dot[0]][dot[1]] > -1 and used_map[dot[0]][dot[1]] <= dot[2]:
        continue
    if road_map[dot[0]][dot[1]] == "#":
        continue
    used_map[dot[0]][dot[1]] = dot[2]

    queue.append([dot[0],dot[1]-1,dot[2]])
    queue.append([dot[0],dot[1]+1,dot[2]])
    queue.append([dot[0]+1,dot[1],dot[2]])
    queue.append([dot[0]+1,dot[1],dot[2]])

    for x in range(-2,3,1):
        for y in range(-2,3,1):
            queue.append([dot[0]+x,dot[1]+y,dot[2]+1])
    
print(used_map[dh-1][dw-1])

### FIXED CODE ###

#shotoyooさんのコードをお借りしてテスト

import numpy as np
from numba import njit, b1, i4, i8, f8
from heapq import heappop as hpp, heappush as hp

@njit((b1[:, :],i8,i8,i8,i8), cache=True)
def main(ss,ch,cw,dh,dw):
    inf = 1<<30
    h,w = ss.shape
    start = ch*w+cw
    goal = dh*w+dw
    n = h*w
    seen = np.full(n, inf, np.int64)
    seen[start] = 0
    q = [(0, start)] # ワープ回数, 現在位置, 最後の道の位置
    while q:
        pnum,pu = hpp(q)
        ux,uy = divmod(pu,w)
        if pu==goal:
            break
        for xx in range(-2, 3):
            for yy in range(-2, 3):
                if xx==yy==0:
                    continue
                if abs(xx)+abs(yy)<=1:
                    vv = 0
                else:
                    vv = 1
                x,y = ux+xx, uy+yy
                u = x*w + y
                num = pnum+vv
                if x<0 or y<0 or x>=h or y>=w or ss[x][y]:
                    continue
        #         print(x,y)
                if seen[u]>num:
                    seen[u] = num
                    hp(q,(num, u))
                
    val = seen[goal]
    if val==inf:
        return -1
    else:
        return val
      

h,w = map(int, input().split())
ch,cw = map(int, input().split())
dh,dw = map(int, input().split())
ch -= 1
cw -= 1
dh -= 1
dw -= 1
ss = np.array([[c=="#" for c in input()] for _ in range(h)])

print(main(ss,ch,cw,dh,dw))
### BUGGY CODE ###

n=int(input())
s=input()
ans=s[1:].count('E')

for i in range(1,n):
    x=s[:i].count('W')+s[i+1:].count('E')
    ans=min(x,ans)
print(ans)


### FIXED CODE ###

n=int(input())
s=input()
w=0
et=s.count('E')
ans=float('INF')
for i in range(n):
    a=w
    if s[i]=='W':
        w+=1
    e=et-(i+1-w)
    ans=min(ans,a+e)
print(ans)