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

H,W=map(int,input().split())
A=[[None]*(W+2)]+\
  [[i=="." for i in "#"+input()+"#"] for _ in range(H)] + \
  [[None]*(W+2)]

q=[[(i,j) for i in range(1,H+1) for j in range(1,W+1) if not A[i][j]]]

for k in range(2000):
    q.append([])
    f=True
    for i,j in q[k]:
        if A[i-1][j]:
            A[i-1][j]=None
            q[k+1].append((i-1,j))
        if A[i+1][j]:
            A[i+1][j]=None
            q[k+1].append((i+1,j))
        if A[i][j-1]:
            A[i][j-1]=None
            q[k+1].append((i,j-1))
        if A[i][j+1]:
            A[i][j+1]=None
            q[k+1].append((i,j+1))
    if not q[k+1]:
        break
print(k)

### FIXED CODE ###

H,W = list(map(int,input().split()))
A = [list(str(input())) for i in range(H)]
 
black = []
 
cnt = 0
 
for i in range(H):
    for j in range(W):
        if A[i][j] == "#":
            black.append([i,j])
 
length = len(black)
            
while (length < H*W):
    gray = []
    for l in black:
        if l[1] != 0:
            c1 = (l[0],l[1]-1)
            if A[c1[0]][c1[1]] == ".":
                gray.append(c1)
                A[c1[0]][c1[1]] = "#"
        if l[1] != W-1:
            c2 = (l[0],l[1]+1)
            if  A[c2[0]][c2[1]] == ".":
                gray.append(c2)
                A[c2[0]][c2[1]] = "#"
        if l[0] != 0:
            c3 = (l[0]-1,l[1])
            if  A[c3[0]][c3[1]] == ".":
                gray.append(c3)
                A[c3[0]][c3[1]] = "#"
        if l[0] != H-1:
            c4 = (l[0]+1,l[1])
            if  A[c4[0]][c4[1]] == ".":
                gray.append(c4)
                A[c4[0]][c4[1]] = "#"
    
    gray = list(set(gray))
    black = [l for l in gray]
    
    cnt += 1
    length += len(black)
    
print(cnt)
### BUGGY CODE ###

import sys
import math
input=sys.stdin.readline
INF=1000000000
# A Dynamic Programming based Python Program for 0-1 Knapsack problem 
# Returns the maximum value that can be put in a knapsack of capacity W 
def knapSack(W,l, n):
    
    
    
    min_cost = [[0 for i in range(W+1)] for j in range(n+1)] 
    # fill 0th row with infinity 
    for i in range(W+1): 
        min_cost[0][i] = INF 
  
    # fill 0th column with 0 
    for i in range(1, n+1): 
        min_cost[i][0] = 0
    # now check for each weight one by one and fill the 
    # matrix according to the condition 
    for i in range(1, n+1): 
        for j in range(1, W+1): 
            # wt[i-1]>j means capacity of bag is 
            # less than weight of item 
            if (l[i-1][0] > j): 
                min_cost[i][j] = min(min_cost[i-1][j] ,l[i-1][1])
            # here we check we get minimum cost either 
            # by including it or excluding it 
            else: 
                min_cost[i][j] = min(min_cost[i-1][j], 
                    min_cost[i][j-l[i-1][0]] + l[i-1][1]) 
    
  
    # exactly weight W can not be made by given weights 
    if(min_cost[n][W] == INF): 
        return -1
    else: 
        return min_cost[n][W]

h,n=map(int,input().split())
l=list()
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b])
print( knapSack(h , l , n) ) 


### FIXED CODE ###


INF=1000000000
# A Dynamic Programming based Python Program for 0-1 Knapsack problem 
# Returns the maximum value that can be put in a knapsack of capacity W 
def knapSack(W,l, n):
    
    
    
    min_cost = [[0 for i in range(W+1)] for j in range(n+1)] 
    # fill 0th row with infinity 
    for i in range(W+1): 
        min_cost[0][i] = INF 
  
    # fill 0th column with 0 
    for i in range(1, n+1): 
        min_cost[i][0] = 0
    # now check for each weight one by one and fill the 
    # matrix according to the condition 
    for i in range(1, n+1): 
        for j in range(1, W+1): 
            # wt[i-1]>j means capacity of bag is 
            # less than weight of item 
            if (l[i-1][0] > j): 
                min_cost[i][j] = min(min_cost[i-1][j] ,l[i-1][1])
            # here we check we get minimum cost either 
            # by including it or excluding it 
            else: 
                min_cost[i][j] = min(min_cost[i-1][j], 
                    min_cost[i][j-l[i-1][0]] + l[i-1][1]) 
    
  
    # exactly weight W can not be made by given weights 
    if(min_cost[n][W] == INF): 
        return -1
    else: 
        return min_cost[n][W]

h,n=map(int,input().split())
l=list()
for i in range(n):
    a,b=map(int,input().split())
    l.append([a,b])
print( knapSack(h , l , n) )
### BUGGY CODE ###

N=int(input())
s=input()
R=[0]
G=[0]
B=[0]
ans=0
#RGBの累積和を作る
for i in range(N):
  if s[i]=="R":
    R[i]+=1
  elif s[i]=="G":
    G[i]+=1
  else:
    B[i]+=1
  R.append(R[i])
  G.append(G[i])
  B.append(B[i])
del R[-1]
del G[-1]
del B[-1]
#作った

#全探索する
for i in range(N-2):
  a=s[i]
  for j in range(i+1,N-1):
    if a==s[j]:
      continue
    b=s[j]
    k=2*j-i
    if "R" not in a+b:
      ans+=R[-1]-R[j]
      try:
        if s[k]=="R":
          ans-=1
      except:
        pass
    
    if "G" not in a+b:
      ans+=G[-1]-G[j]
      try:
        if s[k]=="G":
          ans-=1
      except:
        pass
        
    if "B" not in a+b:
      ans+=B[-1]-B[j]
      try:
        if s[k]=="B":
          ans-=1
      except:
        pass
print(ans)

### FIXED CODE ###

N=int(input())
s=input()
R=[0]
G=[0]
B=[0]
ans=0
#RGBの累積和を作る
for i in range(N):
  if s[i]=="R":
    R[i]+=1
  elif s[i]=="G":
    G[i]+=1
  else:
    B[i]+=1
  R.append(R[i])
  G.append(G[i])
  B.append(B[i])
del R[-1]
del G[-1]
del B[-1]
#作った

#全探索する
for i in range(N-2):
  a=s[i]
  for j in range(i+1,N-1):
    if a==s[j]:
      continue
    b=s[j]
    k=2*j-i
    if "R" not in a+b:
      ans+=R[-1]-R[j]
      try:
        if s[k]=="R":
          ans-=1
      except:
        pass
    
    if "G" not in a+b:
      ans+=G[-1]-G[j]
      try:
        if s[k]=="G":
          ans-=1
      except:
        pass
        
    if "B" not in a+b:
      ans+=B[-1]-B[j]
      try:
        if s[k]=="B":
          ans-=1
      except:
        pass
print(ans)
### BUGGY CODE ###

A, B = map(int,input().split())
for i in range(max(A,B),1000000001):
    if i%A==0 and i%B==0:
        print(i)
        break

### FIXED CODE ###

A, B = map(int,input().split())
for i in range(max(A,B),0,-1):
    if A%i==0 and B%i==0:
        print(A*B//i)
        break
### BUGGY CODE ###

#TLE
N = int(input())
A = input().split()
ans = 0
for l in range(N):
    ans += A.count(A[l]) - 1
ans /= 2
for k in range(N):
    answer = ans - (A.count(A[k]) - 1)
    print(int(answer))

### FIXED CODE ###

#TLE
n = int(input())
a = input().split()
ans = 0
import collections
dic = collections.Counter(a)
for i in dic.values():
    ans += i * (i-1)
ans /= 2
for i in range(n):
    print(int(ans - dic[a[i]] + 1))
### BUGGY CODE ###

n,m = map(int,input().split())
a_ls = [int(input()) for _ in range(m)]

dp = [0] * (n+1)
dp[0] = 1
for i in range(n):
    if i+1 not in a_ls and i not in a_ls:
        if dp[i + 1] == 0:
            dp[i+1] = dp[i]
        else:
            dp[i+1] = (dp[i+1] + dp[i]) % 1000000007
    if i+2 <= n and i+2 not in a_ls and i not in a_ls:
        if dp[i + 2] == 0:
            dp[i+2] = dp[i]
        else:
            dp[i+2] = (dp[i+2] + dp[i]) % 1000000007
print(dp[-1])

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)

mod = 1000000007

n,m = map(int,input().split())
good = [True] * (n+1)
for _ in range(m):
    x = int(input())
    good[x] = False

dp = [0] * (n+1)
dp[0] = 1

for i in range(n):
    # 出発点になれるなら、のみでOK
        # Falseの部分が更新されることはあっても、出発点になれないから
    if good[i]:
        if i+1 <= n:
            dp[i+1] += dp[i]
            dp[i+1]%= mod
        if i+2 <= n:
            dp[i+2] += dp[i]
            dp[i+2] %= mod

print(dp[n])
### BUGGY CODE ###

def main():
  n, k, offset=0, 0, 0
  while k < K:
    if O[n] >= offset:
      L.append(O[n])
      k+=1
      offset = O[n] + C + 1
    n+=1

  n, k, offset=len(O)-1, -1, N
  while k < K and n>=0:
    if O[n] <= offset:
      R.append(O[n])
      k+=1
      offset = O[n] - C - 1
    n-=1
  
  for l in L:
    if l in R:
      print(l)

if __name__=='__main__':
  N, K, C=map(int, input().split())
  S = input()
  O = [int(x)+1 for x, v in enumerate(list(S)) if v=='o'] 
  L,R=[],[]
  main()


### FIXED CODE ###

def main():
  N, K, C=map(int, input().split())
  S = input()

  R=[0]*K
  n, k=N-1, 0
  while k < K:
    if S[n]=='o':
      R[k]=n+1
      k+=1
      n -= C
    n-=1
  R=R[::-1]
  
  n, k=0, 0
  while k < K:
    if S[n]=='o':
      if n+1 == R[k]:
        print(n+1)
      k+=1
      n += C
    n+=1
  #print(L)
  

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

def solve():
    N, K = map(int, input().split())
    ps = list(map(int, input().split()))
    maxi = ps[:K]
    expected = ps[:K]
    for index in range(K, N):
        expected.pop(0)
        expected.append(ps[index])
        if sum(expected) > sum(maxi):
            maxi = expected[:]
    res = sum([(x + 1) / 2 for x in maxi])
    print(res)

solve()

### FIXED CODE ###

def solve():
    N, K = map(int, input().split())
    ps = list(map(int, input().split()))
    curSum = sum(ps[:K])
    curMax = curSum
    i = K; j = 0
    while i < N:
        curSum -= ps[j]
        curSum += ps[i]
        curMax = max(curSum, curMax)
        i += 1; j += 1
    print((curMax + K) / 2)
solve()
### BUGGY CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
sys.setrecursionlimit(10**6)
def resolve():
    N = ir()
    c = lr()
    ab = [[] for i in range(N)]
    for i in range(N-1):
        a, b = lr()
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    tot = N*(N+1)//2
    il = [0]*N
    ol = [0]*N
    cnt = [-1]
    def dfs(u, p):
        cnt[0] += 1
        il[u] = cnt[0]
        for i in ab[u]:
            if i != p:
                dfs(i, u)
        ol[u] = cnt[0]
    dfs(0, -1)
    vs = [[] for i in range(N)]
    for i in range(N):
        vs[c[i]-1].append(i)
    sl = [1]*N
    for i in range(N):
        his = []
        ans = tot
        tvs = sorted(vs[i], key=lambda x: il[x])[::-1]
        for v in tvs:
            n = 1
            for j in ab[v]:
                if il[j] > il[v]:
                    tmp = sum(sl[il[j]:ol[j]+1])
                    ans -= tmp*(tmp+1)//2
                    n += tmp
            sl[il[v]] -= n
            his.append([il[v], n])
        tmp = sum(sl[0:ol[0]+1])
        ans -= tmp*(tmp+1)//2
        for h in his:
            sl[h[0]] += h[1]
        print(ans)
resolve()

### FIXED CODE ###

import sys
sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))
sys.setrecursionlimit(10**6)
class Bit:
    def __init__(self, n):
        self.size = n
        self.tree = [0] * (n + 1)
 
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & (-i)
        return s
 
    def add(self, i, x):
        while i <= self.size:
            self.tree[i] += x
            i += i & (-i)
def resolve():
    N = ir()
    c = lr()
    ab = [[] for i in range(N)]
    for i in range(N-1):
        a, b = lr()
        ab[a-1].append(b-1)
        ab[b-1].append(a-1)
    tot = N*(N+1)//2
    il = [0]*N
    ol = [0]*N
    cnt = [0]
    def dfs(u, p):
        cnt[0] += 1
        il[u] = cnt[0]
        for i in ab[u]:
            if i != p:
                dfs(i, u)
        ol[u] = cnt[0]
    dfs(0, -1)
    vs = [[] for i in range(N)]
    for i in range(N):
        vs[c[i]-1].append(i)
    sl = Bit(N)
    for i in range(1, N+1):
        sl.add(i, 1)
    for i in range(N):
        his = []
        ans = tot
        tvs = sorted(vs[i], key=lambda x: il[x])[::-1]
        for v in tvs:
            n = 1
            for j in ab[v]:
                if il[j] > il[v]:
                    tmp = sl.sum(ol[j])-sl.sum(il[j]-1)
                    ans -= tmp*(tmp+1)//2
                    n += tmp
            sl.add(il[v], -n)
            his.append([il[v], n])
        tmp = sl.sum(ol[0])-sl.sum(0)
        ans -= tmp*(tmp+1)//2
        for h in his:
            sl.add(h[0], h[1])
        print(ans)
resolve()
### BUGGY CODE ###

A = "AC"
N, Q = map(int, input().split())
S = list(input())
ans = [0] * (N - 1)
ind = 0
for i in range(N):
    try:
        ind = S.index('A', ind)
        if S[ind + 1] == 'C':
            ans[ind] = 1
        ind = ind + 1
    except:
        break


for i in range(Q):
    l, r = map(int, input().split())
    print(sum(ans[l-1:r-1]))



### FIXED CODE ###

A = "AC"
N, Q = map(int, input().split())
S = list(input())
ans = [0]
cnt = 0
for j in range(N - 1):
    tmp1 = S[j] + S[j + 1]
    if tmp1 == A:
        cnt += 1
    ans.append(cnt)

for i in range(Q):
    l, r = map(int, input().split())
    print(ans[r-1] - ans[l-1])
### BUGGY CODE ###

h,w=map(int,input().split())
c=eval('list(input()),'*h)
q=[]
for i in range(h):
 for j in range(w):
  if'.'>c[i][j]:q+=[(i,j,0)]
a=0
while q:
 y,x,v=q.pop(0);a=max(a,v)
 for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
  if h>i>=0and w>j>=0and'#'<c[i][j]:c[i][j]='#';q.append((i,j,v+1))
print(a)

### FIXED CODE ###

from collections import*
h,w=map(int,input().split())
c=eval('list(input()),'*h)
q=deque()
for i in range(h):
    for j in range(w):
        if c[i][j]=='#':
            q.append((i,j,0))
ans=0
while q:
    y,x,v=q.popleft()
    ans=max(ans,v)
    for i,j in((y,x-1),(y,x+1),(y-1,x),(y+1,x)):
        if h>i>=0 and w>j>=0 and c[i][j]=='.':
            c[i][j]='#'
            q.append((i,j,v+1))
print(ans)
### BUGGY CODE ###

# coding: utf-8
import sys
from itertools import permutations

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

# 3色を全探索
N, COLOR = lr()
D = [lr() for _ in range(COLOR)]
C = [lr() for _ in range(N)]

answer = 10 ** 10
for comb in permutations(range(COLOR), 3):
    temp = 0
    for i in range(N):
        for j in range(N):
            num = (i+j)%3
            color = comb[num]
            temp += D[C[i][j]-1][color]
    if temp < answer:
        answer = temp

print(answer)
# 15


### FIXED CODE ###

import sys
import numpy as np
import itertools

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, C = lr()
D = np.array([lr() for _ in range(C)])

grid = [lr() for _ in range(N)]
three = [[0] * C for _ in range(3)]
for i in range(N):
    for j in range(N):
        remain = (i+j) % 3
        three[remain][grid[i][j]-1] += 1

three = np.array(three)
answer = 10 ** 10
for x, y, z in itertools.permutations(range(C), 3):
    # three[0]をxの色にする
    result = 0
    for i in range(3):
        s = [x, y, z][i]
        result += (three[i] * D[:, s]).sum()
    if result < answer:
        answer = result

print(answer)
# 35
### BUGGY CODE ###

import bisect
n = int(input())
l = sorted(list(map(int, input().split())))
ans = 0
for i in range(n-2):
  a = l[i]
  for j in range(i + 1, n-1):
    ans += bisect.bisect_left(l, l[j]+a, lo = j + 1)-j-1
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int,input().split())))
ans = 0
 
for i in range(n-2):
    for j in range(i+1, n-1):
        ans += bisect.bisect_left(l,l[i] + l[j]) - j - 1
print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
for _ in range(Q):
    l, r = map(int, input().split())
    s = S[l-1:r]
    print(s.count("AC"))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
    t[i + 1] = t[i] + (1 if S[i : i + 2] == "AC" else 0)
for i in range(Q):
    l, r = map(int, input().split())
    print(t[r - 1] - t[l - 1])
### BUGGY CODE ###

N, A = map(int,input().split())
X = list(map(int,input().split()))

from itertools import combinations

cnt = 0
for i in range(1,N+1):
  for per in combinations(X, i):
    #print(per,i,sum(per))
    if(sum(per)/i == A):
      cnt += 1
print(cnt)


### FIXED CODE ###

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

X = [int(x) - A for x in input().split()]
dp = [[0 for _ in range(100*N+1)] for _ in range(N+1)]
dp[0][50*N] = 1

for i in range(N):
  for j in range(50, 100*N+1-50):
    dp[i+1][j] = dp[i][j] + dp[i][j - X[i]]
print(dp[N][50*N] - 1)
### BUGGY CODE ###

n, m = map(int,input().split())
stairs = list([int(input()) for i in range(m)])
dp = [0] * (n+1)
dp[0] = 1

for i in range(1, n+1):
    if i in stairs: 
        dp[i] = 0
        continue

    dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)

print(dp[n])

### FIXED CODE ###

n, m = map(int,input().split())
stairs = set([int(input()) for i in range(m)])
dp = [0] * (n+1)
dp[0] = 1

for i in range(1, n+1):
    if i in stairs: 
        dp[i] = 0
        continue

    dp[i] = (dp[i-1] + dp[i-2]) % (10**9+7)

print(dp[n])
### BUGGY CODE ###

import itertools


def main():
    X, Y, Z, K = list(map(int, input().split(' ')))
    A = list(map(int, input().split(' ')))
    B = list(map(int, input().split(' ')))
    C = list(map(int, input().split(' ')))
    AB = list(map(sum, itertools.product(A, B)))
    AB.sort(reverse=True)
    AB = AB[:min([K, X * Y])]
    ABC = list(map(sum, itertools.product(AB, C)))
    ABC.sort(reverse=True)
    for ans in ABC[:K]:
        print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import numpy as np


def main():
    X, Y, Z, K = list(map(int, input().split(' ')))
    A = np.array(list(map(int, input().split(' '))))
    B = np.array(list(map(int, input().split(' '))))
    C = np.array(list(map(int, input().split(' '))))
    AB = np.array(np.meshgrid(A, B)).T.reshape(-1, 2).sum(axis=1)
    AB[::-1].sort()
    AB = AB[:min([K, X * Y])]
    ABC = np.array(np.meshgrid(AB, C)).T.reshape(-1, 2).sum(axis=1)
    ABC[::-1].sort()
    for ans in ABC[:K]:
        print(ans)


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

from operator import itemgetter
import bisect
import numpy as np
N, M, Q = map(int, input().split())

trains = [list(map(int, input().split())) for _ in range(M)]
trains = np.array(sorted(trains, key=itemgetter(0)))
query = [map(int, input().split()) for _ in range(Q)]
bleft = bisect.bisect_left
bright = bisect.bisect_right
for p, q in query:
    li = bleft(trains[:, 0].ravel(), p)
    #print(trains[:li])
    tmpTrains = np.array(sorted(trains[li:, 1].ravel()))
    ri = bright(tmpTrains, q)
    print(ri)


### FIXED CODE ###

N, M, Q = map(int, input().split())
X = [[0 for _ in range(N)] for _ in range(N)]


for _ in range(M):
    l, r = list(map(int, input().split()))
    X[l-1][r-1] += 1
C = []
for line in X:
    tmp = [0, ]
    for c in line:
        tmp.append(tmp[-1] + c)
    C.append(tmp)
query = [map(int, input().split()) for _ in range(Q)]
# print(X)
# print(C)

for p, q in query:
    ans = 0
    for i, line in enumerate(C):
        if p-1 <= i and i <= q-1:
            ans += line[q] - line[p-1]
    print(ans)
### BUGGY CODE ###

N = input()
a = [0] * 2050
for i in range(len(N)):
    n = N[len(N)-1-i:]
    a[int(n) % 2019] += 1
ans = 0
for i in range(2019):
    if i == 0:
        ans += a[i] * (a[i]+1) // 2
    else:
        ans += (a[i]-1) * a[i] // 2
print(ans)


### FIXED CODE ###

N = input()
a = [0] * 2050
n = 0
p = 1
for i in range(len(N)):
    n += int(N[len(N)-1-i]) * p
    p *= 10
    p %= 2019
    a[int(n) % 2019] += 1
ans = 0
for i in range(2019):
    if i == 0:
        ans += a[i] * (a[i]+1) // 2
    else:
        ans += (a[i]-1) * a[i] // 2
print(ans)
### BUGGY CODE ###

import sys
INF = 10**18
sys.setrecursionlimit(10**6)
from collections import defaultdict
def li():
    return [int(x) for x in input().split()]
from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

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

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch-1][Cw-1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        # print(que)
        # 左から取り出す
        x, y = que.popleft()
        # 通常移動パターン
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            # バリデーション、初探索 or コストが下がる場合
            if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                # コストゼロは左から
                que.appendleft((nx, ny))
                costmap[ny-1][nx-1] = costmap[y-1][x-1]
        # 特殊移動パターン
        for i in range(x-2, x+3):
            for j in range(y-2, y+3):
                nx, ny = i, j
                # バリデーション、初探索 or コストが下がる場合
                if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                    # コスト1は右から
                    que.append((nx, ny))
                    costmap[ny-1][nx-1] = costmap[y-1][x-1] + 1
    return costmap

costmap = bfs()
# print(costmap)
print(costmap[Dh-1][Dw-1])


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[list(input()) for i in range(h)]
 
#幅優先で解く。
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs():
  maze=[[-1]*w for i in range(h)]
  maze[ch-1][cw-1]=0
  qu=deque([])
  qu.append((cw-1,ch-1))
  magic=0
  
  while qu:
    x,y=qu.popleft()
    for i in range(4):
      nx=dx[i]+x
      ny=dy[i]+y
      if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]):
        qu.appendleft((nx,ny))
        maze[ny][nx]=maze[y][x]
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        nx=i
        ny=j
        if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]+1):
          qu.append((nx,ny))
          maze[ny][nx]=maze[y][x]+1
  return maze
    
maze = bfs()
print(maze[dh-1][dw-1])
### BUGGY CODE ###


def Attention():
    N = int(input())
    S = input()
    ans = 300000

    for i in range(N):
        count = len(S[:i-1].replace('E', '')) + len(S[i+1:].replace('W', ''))

        """
        for a in S[:i-1]:
            if a == 'W':count+=1
        for a in S[i+1:]:
            if a == 'E':count+=1'
        ans = min(ans, count)
        """
        ans = min(ans, count)
    print(ans)

Attention()


### FIXED CODE ###


def Attention():
    N = int(input())
    S = input()
    ans = 300000

    Wcount = [0]
    Ecount = [0]
    cnt = 0
    for i in range(N):
        if S[i] == 'W':
            cnt += 1
        Wcount.append(cnt)
    cnt = 0
    for i in range(N):
        if S[(i + 1) * -1] == 'E':
            cnt += 1
        Ecount.append(cnt)

    for i in range(N):
        cnt = Wcount[i] + Ecount[(i + 2) * -1]
        ans = min(cnt, ans)
    print(ans)

Attention()
### BUGGY CODE ###

#素直な実装　
MOD = 10 ** 9 + 7
L = list(input())
N = len(L)
# print (N)
n = 0
for l in L:
    n = 2 * n + int(l)

ans = 0
for i in range(n + 1):
    tmp = 1
    for j in range(N):
        if (i >> j) & 1:
            tmp *= 2
    # print (i, tmp)
    ans += tmp
    ans %= MOD

print (ans)



### FIXED CODE ###

# すべて1のところ
# 毎回calc(x)を計算しているから遅い
MOD = 10 ** 9 + 7
L = list(input())
N = len(L)

lst = [-1] * N
def calc(x): #1が続いている桁数
    if x == 0:
        return 1
    tmp_ans = 1
    tmp = 1
    for i in range(1, x):
        tmp = (tmp * (x + 1 - i))//i
        tmp_ans += pow(2, i, MOD) * tmp
        tmp_ans %= MOD

    tmp_ans += pow(2, x, MOD)
    tmp_ans %= MOD
    return tmp_ans

def calc1(x):
    return pow(3, x, MOD)

#ここまでで一番上の桁が0の場合を処理済み（N - 1桁で書ける場合）
ans = calc1(N - 1) + 2
# print (ans)

# 1xxxxxxのxxxxxxの部分を足す必要がある

count = 1
for i in range(1, N):
    if L[i] == '1':
        ans += pow(2, count, MOD) * (calc1(N - 1 - i) + 1)
        count += 1
        ans %= MOD
    
print (ans % MOD)