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

import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
H,W = map(int,input().split())
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)
#print(S)
reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([])
Q.append([C,0])
while Q:
  z, score = Q.popleft()
  x = z[0];y=z[1]
  if reach[x][y] < score:
    #print(z,score)
    continue
 
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    #print(nx,ny)
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = [nx,ny]
      Q.append([u,score])
  #print(reach)
 
  for i in range(5): #0~4
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "#":
        continue
      if reach[mx][my] <= score+1: #すでにこのスコア以下でいける。
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = [mx,my]
      #print(v,p,"X")
      Q.append([p,score+1])
#dfs(C,0)
#print(reach)
#print(reach[D[0]][D[1]])
if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[1]])


### FIXED CODE ###

import sys
sys.setrecursionlimit(500000) 
input = sys.stdin.readline
from collections import deque
H,W = map(int,input().split())
C = list(map(int,input().split()))
C[0] -= 1; C[1] -= 1
D = list(map(int,input().split()))
D[0] -= 1; D[1] -= 1
S = []; INF = float("inf")
for i in range(H):
  temp = str(input());temp =list(temp)
  S.append(temp)
#print(S)
reach = [[INF]*W for _ in range(H)]
reach[C[0]][C[1]] = 0
dxdy = [(1,0),(-1,0),(0,1),(0,-1)]
Q = deque([])
Q.append([C,0])
while Q:
  z, score = Q.popleft()
  x = z[0];y=z[1]
 
  for i in range(4):
    nx = x + dxdy[i][0]
    ny = y + dxdy[i][1]
    #print(nx,ny)
    if 0<=nx<H and 0<=ny<W and S[nx][ny] == "." and reach[nx][ny] > score:
      reach[nx][ny] = min(score,reach[nx][ny])
      u = [nx,ny]
      Q.appendleft([u,score])
  #print(reach)
 
  for i in range(5): #0~4
    for j in range(5):
      mx = x-2 + i
      my = y-2 + j
      if i == 2 and j == 2:
        continue
      if mx < 0 or mx >= H or my < 0 or my >= W or S[mx][my] == "#":
        continue
      if reach[mx][my] <= score+1: #すでにこのスコア以下でいける。
        continue
      reach[mx][my] = min(score+1,reach[mx][my])
      p = [mx,my]
      #print(v,p,"X")
      Q.append([p,score+1])
#dfs(C,0)
#print(reach)
#print(reach[D[0]][D[1]])
if reach[D[0]][D[1]] == INF:
  print(-1)
else:
  print(reach[D[0]][D[1]])
### BUGGY CODE ###

import os

N = int(input())
alist = [int(i) for i in input().split()]

for i in range(1,N+1):
    print(alist.index(i)+1),


### FIXED CODE ###

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

i = 0
person = []
for j in range(n):
    person.append(0)
ans = []
for k in a:
    i += 1
    person[k-1] = i

a.sort()
for l in a:
    ans.append(str(person[l-1]))

order = ' '.join(ans)
print(order)
### BUGGY CODE ###

from operator import mul
from functools import reduce
N = int(input())
A = list(map(int,input().split()))

if reduce(mul, A) > 10**18:
    print(-1)
    exit()
else:
    print(reduce(mul, A))

### FIXED CODE ###

N = int(input())
A = sorted(list(map(int,input().split())), reverse=True)

if 0 in A:
    print(0)
    exit()

ans=1

for i in range(N):
    ans = ans * A[i]
    if ans > 10**18:
        print(-1)
        exit()

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

import math
n, p=map(int,input().split())
ans = 0
if n != 1:
    for i in range(1,int(math.sqrt(p+1))+1):
        ni = i**n
        if p/ni >= 1 and p/ni == int(p/ni):
            ans = i
        elif p/ni < 1:
            break
    print(ans)
else:
    print(p)

### FIXED CODE ###

n, p=map(int,input().split())
ans = 0
if n != 1:
    for i in range(1,int((p+1)**(1/n))+1):
        ni = i**n
        if p/ni >= 1 and p/ni == int(p/ni):
            ans = i
        elif p/ni < 1:
            break
    print(ans)
else:
    print(p)
### BUGGY CODE ###

from sys import stdin
import itertools

l,r = [int(x) for x in stdin.readline().rstrip().split()]


li = [x for x in range(l,r+1)]
m = 2020
for i in range(len(li)-1):
    for j in range(i+1,len(li)):
        if li[i]*li[j]%2019 == 0:
            print(0)
            exit()
        else:
            m = min(m,li[i]*li[j]%2019)
print(m)

### FIXED CODE ###

from sys import stdin

l,r = [int(x) for x in stdin.readline().rstrip().split()]
m = 2020
if r - l > 2018:
    print(0)
    exit()
for i in range(l,r):
    for j in range(i+1,r+1):
        if i*j%2019 == 0:
            print(0)
            exit()
        else:
            m = min(m,i*j%2019)
print(m)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,Q=map(int,input().split())
C=list(map(int,input().split()))

LEN=N
Sparse_table = [[1<<c for c in C]]

for i in range(LEN.bit_length()-1):
    j = 1<<i
    B = []
    for k in range(len(Sparse_table[-1])-j):
        B.append(Sparse_table[-1][k]|Sparse_table[-1][k+j])
    Sparse_table.append(B)

def query(l,r):
    i=(r-l).bit_length()-1 # 何番目のSparse_tableを見るか. 

    ANS=Sparse_table[i][l]|Sparse_table[i][r-(1<<i)]

    return bin(ANS).count("1")

for qu in range(Q):
    x,y=map(int,input().split())
    print(query(x-1,y))


### FIXED CODE ###

import sys
import io, os
input = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from operator import itemgetter

N,Q=map(int,input().split())
C=[0]+list(map(int,input().split()))

QU=[list(map(int,input().split()))+[i] for i in range(Q)]


QU.sort(key=itemgetter(0))


# BIT(BIT-indexed tree)

LEN=N+3

BIT=[0]*(LEN+1) # 1-indexedなtree

def update(v,w): # index vにwを加える
    while v<=LEN:
        BIT[v]+=w
        v+=(v&(-v)) # 自分を含む大きなノードへ. たとえばv=3→v=4

def getvalue(v): # [1,v]の区間の和を求める
    ANS=0
    while v!=0:
        ANS+=BIT[v]
        v-=(v&(-v)) # 自分より小さい2ベキのノードへ. たとえばv=3→v=2へ
    return ANS

NUM=[[] for i in range(N+1)]
for i,c in enumerate(C):
    if i==0:
        continue
    if NUM[c]==[]:
        update(i,1)
    NUM[c].append(i)
    
NUMIND=[0]*(N+1)

ANS=[-1]*Q

ia=1

for x,y,ind in QU:

    while ia!=x:
        update(NUM[C[ia]][NUMIND[C[ia]]],-1)
        NUMIND[C[ia]]+=1
        if NUMIND[C[ia]]<len(NUM[C[ia]]):
            update(NUM[C[ia]][NUMIND[C[ia]]],1)
        ia+=1

    #print(x,y,ind)
    #print([getvalue(i) for i in range(1,N+1)])
    ANS[ind]=getvalue(y)

sys.stdout.write(" ".join(map(str,ANS))+"\n")
### BUGGY CODE ###

from collections import defaultdict


n, t = map(int, input().split())

dish = []

for _ in range(n):
    time, point = map(int, input().split())
    dish.append([time, point])

dish.sort()
DP = [[0]*t for i in range(n+1)]
ans = defaultdict(int)

for i in range(1, n+1):
    time, point = dish[i-1]

    for j in range(t):
        DP[i][j] = max(DP[i-1][j], DP[i][j])
        if j + time >= t:
            ans[i] = max(DP[i-1][j]+point, ans[i])
            continue
        DP[i][j+time] = max((DP[i-1][j] + point), DP[i-1][j+time])

res = max(ans.values())
print(res)

### FIXED CODE ###

from collections import defaultdict


n, t = map(int, input().split())

dish = []

for _ in range(n):
    time, point = map(int, input().split())
    dish.append([time, point])

dish.sort()
DP = [[0]*t for i in range(n+1)]
ans = defaultdict(int)

for i in range(1, n+1):
    time, point = dish[i-1]

    for j in range(t):
        DP[i][j] = max(DP[i-1][j], DP[i][j])
        if j + time >= t:
            ans[i] = max(DP[i-1][j]+point, ans[i])
            continue
        DP[i][j+time] = max((DP[i-1][j] + point), DP[i-1][j+time])

res = max(ans.values())
print(res)
### BUGGY CODE ###

def solve():
    N, M = map(int, input().split())
    A = [int(input()) for _ in range(M)]
    mm = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[0] = 1  # 0段目に行くパターンは1とする
    dp[1] = 0 if 1 in A else 1  # 1段目の行き方を設定
    for i in range(2, N + 1):
        if i in A:
            continue
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[N] % mm)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N, M = map(int, input().split())
    A = []
    if M != 0:
        A = [int(input()) for _ in range(M)]
    A.sort(reverse=True)
    mm = 10 ** 9 + 7
    dp = [0] * (N + 1)
    dp[0] = 1  # 0段目に行くパターンは1とする
    tag = -1
    if len(A) != 0:
        tag = A.pop()
    # 1段目のパターンを設定
    if tag == 1:
        dp[1] = 0
        if len(A) == 0:
            tag = -1
        else:
            tag = A.pop()
    else:
        dp[1] = 1
    for i in range(2, N + 1):
        if i == tag:
            if len(A) == 0:
                tag = -1
            else:
                tag = A.pop()
            continue
        dp[i] = (dp[i - 1] + dp[i - 2]) % mm
    print(dp[N])


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

import itertools
import numpy as np

N = int(input())

L = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

count = 0
ptr_num = np.array(list(itertools.product(L, repeat=N)))

print(np.count_nonzero(np.any(ptr_num == 0, axis=1) & np.any(ptr_num == 9, axis=1)))

### FIXED CODE ###

NUM = 1000000007

N = int(input())

all_colab = pow(10, N)
except_0or9_colab = pow(9, N)
except_0and9_colab = pow(8, N)

include_0and9_colab = all_colab - (2*except_0or9_colab - except_0and9_colab)

print(include_0and9_colab % NUM)
### BUGGY CODE ###

N,A,B,K = map(int,input().split())
MOD = 998244353

fac = [1,1] + [0]*N
finv = [1,1] + [0]*N
inv = [0,1] + [0]*N
for i in range(2,N+2):
    fac[i] = fac[i-1] * i % MOD
    inv[i] = -inv[MOD%i] * (MOD // i) % MOD
    finv[i] = finv[i-1] * inv[i] % MOD

def ncr(n,r):
    if n < r: return 0
    if n < 0 or r < 0: return 0
    return fac[n] * (finv[r] * finv[n-r] % MOD) % MOD

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    for green in range(min(a,b) + 1):
        red = a - green
        blue = b - green
        if red + green + blue > N: continue
        tmp = 1
        tmp *= ncr(N, red+green+blue)
        tmp *= ncr(red+green+blue, green+blue)
        tmp *= ncr(green+blue, blue)
        ans += tmp % MOD
print(ans % MOD)

### FIXED CODE ###

N,A,B,K = map(int,input().split())
if A<B: A,B = B,A
MOD = 998244353

def mul(a,b):
    return (a*b) % MOD

def pow(a,n): # a^n
    ret = 1
    mag = a
    while n > 0:
        if n & 1:
            ret = mul(ret, mag)
        mag = mul(mag, mag)
        n >>= 1
    return ret

def inv(a):
    return pow(a, MOD-2)

fac = [1]
fac_inv = [1]
for n in range (1,N+10):
    f = mul(fac[n-1], n)
    fac.append(f)
    fac_inv.append(inv(f))

mem = [0] * (N+1)
def ncr(n,r):
    if mem[r] > 0:
        return mem[r]
    else:
        ret = mul(mul(fac[n], fac_inv[n-r]), fac_inv[r])
        mem[r] = ret
        return ret

ans = 0
for a in range(N+1):
    if a*A > K: break
    rem = K-a*A
    if rem%B: continue
    b = rem//B
    if b > N: continue
    ans += mul(ncr(N,a), ncr(N,b))
print(ans % MOD)
### BUGGY CODE ###

from collections import Counter
import math
N = int(input())
x,y = map(int, input().split())
dis_list = [[x,y]]
for i in range(N-1):
	x , y = map(int,input().split())
	for j in range(len(dis_list)):
		x = abs(x- dis_list[j][0])
		y = abs(y-dis_list[j][1])
		dis_list.append([x,y])
dis_list = dis_list[1:1+N*(N-1)//2]
counter = Counter(map(tuple, dis_list))
if N == 1:
    print(1)
else:
    print(N-counter.most_common()[0][1])

### FIXED CODE ###

import math
N = int(input())
s_dict = {}
cood_list=[]
ans = 0
for i in range(N):
    a,b = map(int,input().split())
    for j in range(len(cood_list)):
        p = a - cood_list[j][0]
        q = b - cood_list[j][1]
        if 0 > p:
            p = -p
            q = -q
        elif p == 0:
            q = abs(q)
        s = str(p)+","+str(q)
        if s not in s_dict:
            s_dict[s] = 1
        else:
            s_dict[s] += 1
    cood = [a,b]
    cood_list.append(cood)
if N != 1:
    print(N-max(s_dict.values()))
else:
    print(1)
### BUGGY CODE ###

n=int(input())
s=[]
for i in range(0,n):
    a=input()
    if a not in s:
        s.append(a)
print(len(s))

### FIXED CODE ###

n=int(input())
s=[]
for i in range(0,n):
  s.append(input())
a=set(s)
print(len(a))
### BUGGY CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7

#modに対応して高速なコンビネーションが求められる
# 階乗 & 逆元計算

n = 10 ** 6
factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % mod)
    inverse.append(pow(factorial[-1], mod-2, mod))

def combinations_count(n,r):
    if n-r < 0:
        return 0
    return factorial[n]*inverse[r]*inverse[n-r]%mod

d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

X,Y = LI()

if (X + Y) % 3 != 0:
    ans = 0
else:
    m = int(X * 2 / 3 - Y / 3)
    n = int(Y * 2 / 3 - X / 3)
    # print(m,n)
    ans = combinations_count(m + n, n)
print(ans)


### FIXED CODE ###

# encoding:utf-8
import copy
import random
import bisect #bisect_left　これで二部探索の大小検索が行える
import fractions #最小公倍数などはこっち
import math
import sys
import collections

mod = 10**9+7

#modに対応して高速なコンビネーションが求められる
# 階乗 & 逆元計算



d = collections.deque()
def LI(): return list(map(int, sys.stdin.readline().split()))

X,Y = LI()

if (X + Y) % 3 != 0:
    ans = 0
else:
    n = 10 ** 6
    factorial = [1]
    inverse = [1]
    for i in range(1, n+2):
        factorial.append(factorial[-1] * i % mod)
        inverse.append(pow(factorial[-1], mod-2, mod))

    def combinations_count(n,r):
        if n-r < 0:
            return 0
        return factorial[n]*inverse[r]*inverse[n-r]%mod
    m = int(X * 2 / 3 - Y / 3)
    n = int(Y * 2 / 3 - X / 3)
    if (X+Y) / 3 > X or (X + Y) / 3 > Y or m < 0 or n < 0:
        ans = 0
    else:
        ans = combinations_count((X + Y)//3, n)
print(ans)
### BUGGY CODE ###


n = int(input())
nums = list(map(int, input().split()))
res = 1
for i in range(n):
    res *= nums[i]
if res <= 1000000000000000000:
    print(res)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
nums = list(map(int, input().split()))
res = 1
for i in range(n):
    if( nums[i] == 0):
        res = 0
if(res != 0):
    for i in range(n):
        res *= nums[i]
        if(res > 1000000000000000000):
            break
if res <= 1000000000000000000:
    print(res)
else:
    print(-1)
### BUGGY CODE ###

def counting_sort(a, b, c, k):
	for i in range(1, k+1):
		c[i] = c[i] + c[i - 1]

	for i in range(len(a) - 1, -1, -1):
		num = a[i]
		b[c[num] - 1] = num
		c[num] -= 1

n = int(input())
a = list(map(int, input().split()))
b = [0] * n
c = [0] * 10000
k = 0
for i in range(n):
	num = a[i]
	k = max(k, num)
	c[num] += 1

counting_sort(a, b, c, k)
print(b[0], end='')
for i in range(1, n):
	print(' ' +  str(b[i]), end='')
print()



### FIXED CODE ###

n=int(input())
A=[0]*(n+1)
B=[0]*(n+1)
i=0
mx=(1<<30)*-1
for v in list(map(int,input().split())):
	A[i+1] = v
	mx=max(mx,A[i+1])
	i+=1	

C=[0]*(mx+1)
for i in range(n):
	C[A[i+1]]+=1
for i in range(1,mx+1):
	C[i] += C[i-1]
for i in range(n,0,-1):
	B[C[A[i]]] = A[i]
	C[A[i]]-=1

st=str(B[1])
for i in range(2,n+1):
	st += ' ' + str(B[i])
print(st)
### BUGGY CODE ###

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
import math
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
if A==[1]*N:
  print('pairwise coprime')
  exit()
a=A[0]
d=a
if A[0]!=1:
  D={}
  x=0
  for i in range(N):
    if d!=1:
      d=math.gcd(d,A[i])
    c=A[i]
    if x==0:
      F=factorization(A[i])
      for a,b in F:
        if a not in D:
          D[a]=1
        else:
          x=1
        #互いに素じゃない二組がある  
    if x==1 and d==1:
      break

  if x==1 and d==1:
    print('setwise coprime')
  elif x==0 and d==1:
    print('pairwise coprime')
  else:
    print('not coprime')
else:
  D={}
  x=0
  for i in range(N):
    if A[i]!=1:
      F=factorization(A[i])
      for a,b in F:
        if a not in D:
          D[a]=1
        else:
          x=1
    
  if x==1:
    print('setwise coprime')
  else:
    print('pairwise coprime')

### FIXED CODE ###

N=int(input())
A=list(map(int, input().split()))
A=sorted(A)
import math
import bisect
def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
if A==[1]*N:
  print('pairwise coprime')
  exit()
a=A[0]
d=a
if A[0]!=1:
  D={}
  x=0
  for i in range(N):
    if d!=1:
      d=math.gcd(d,A[i])
    c=A[i]
    if x==0:
      F=factorization(A[i])
      for a,b in F:
        if a not in D:
          D[a]=1
        else:
          x=1
        #互いに素じゃない二組がある  
    if x==1 and d==1:
      break

  if x==1 and d==1:
    print('setwise coprime')
  elif x==0 and d==1:
    print('pairwise coprime')
  else:
    print('not coprime')
else:
  l=bisect.bisect_right(A,1)
  A=A[l:]
  D={}
  x=0
  for i in range(len(A)):
    F=factorization(A[i])
    for a,b in F:
      if a not in D:
        D[a]=1
      else:
        x=1
    if x==1:
      break
    
  if x==1:
    print('setwise coprime')
  else:
    print('pairwise coprime')
### BUGGY CODE ###

inf = 10 ** 9
n, k = map(int, input().split())
h = [0] + list(map(int, input().split()))
cost = [inf for _ in range(n + 1)]
cost[1] = 0
for i in range(1, n):
    for di in range(1, k + 1):
        if i + di > n: break
        cost[i + di] = min(cost[i] + abs(h[i + di] - h[i]), cost[i + di])
print(cost[n])


### FIXED CODE ###

n, k = map(int, input().split())
k = min(n - 1, k)
h = list(map(int, input().split()))
cost = [0 for _ in range(n)]
for i, hi in enumerate(h):
    if i == 0: continue
    st = i - k if i > k else 0
    cost[i] = min([ck + abs(hi - hk) for ck, hk in zip(cost[st:i], h[st:i])])
print(cost[-1])
### BUGGY CODE ###

n = int(input())
A = [int(i) for i in input().split()]
count = 0
for j in range(n):
    for k in range(1,n-j+1,1):
        if not sum(A[j:j+k]):
            count += 1
print(count)

### FIXED CODE ###

from collections import Counter
n = int(input())
A = [int(i) for i in input().split()]
S = [0]*(n+1)
for i in range(n):
    S[i+1] = S[i] + A[i]
def hello(data):
    dt = Counter()
    for i in data:
        dt[str(i)] += 1
    return dt
num = hello(S)
out = [i*(i-1)//2 for i in num.values() if i>1]
print(sum(out))
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A_num = [0] * N
    for i in range(N):
        A_num[A[i]-1] += 1
    #print(A_num)
    A_product = [0] * N
    A_product_1 = [0] * N
    for i in range(N):
        A_product[i] = int(A_num[i] * (A_num[i]-1) / 2)
        if A_num[i] == 0:
            A_product_1[i] = 0
        else:
            A_product_1[i] = int((A_num[i]-1) * (A_num[i]-2) / 2)
    #print(A_product)
    #print(A_product_1)
    for i in range(N):
        k = A[i]
        s = sum(A_product) - A_product[k-1] + A_product_1[k-1]
        print(s)


if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A_num = [0] * N
    for a in A:
        A_num[a-1] += 1

    A_product = [0] * N
    A_product_1 = [0] * N
    for i in range(N):
        a = A_num[i]
        A_product[i] = int(a * (a-1) / 2)
        if a == 0:
            A_product_1[i] = 0
        else:
            A_product_1[i] = int((a-1) * (a-2) / 2)


    su = sum(A_product)
    for k in A:
        print(su - A_product[k-1] + A_product_1[k-1])


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

N = int(input())
S = list(input())

min = N
for i in range(N):
    left_parts = S[:i]
    right_parts = S[i:]
    left_count = left_parts.count('W')
    right_count = right_parts.count('E')
    count = left_count + right_count

    if count < min:
        min = count

print(min)

### FIXED CODE ###

N = int(input())
S = list(input())

countE = S.count('E')
countW = 0
min = countE + countW
for i in range(N):
    if S[i] == 'E':
        countE -= 1
    elif S[i] == 'W':
        countW += 1

    if countE + countW < min:
        min = countE + countW

print(min)
### BUGGY CODE ###

p = int(input())
A = list(map(int,input().split()))
a = list(range(1,p+1))
count = 0
for j,i in zip(a,A):
  if A.count(j) != 0 and i == a[A.index(j)]:
    count += 1
print(count//2)

### FIXED CODE ###

p = int(input())
ans = 0
*A,= map(int,input().split())
for j,i in enumerate(A):
  if A[A[j]-1]==j+1:
    ans+=1
print(ans//2)
### BUGGY CODE ###

from functools import reduce

words = lambda t : list(map(t, input().split()))
n = int(input())
xs = words(int)

ys = []
k = 0
for x in xs:
    y = list(reversed(bin(x)))[:-2]
    ys.append(y)
    k = max(k, len(y))
#print(ys, n)




def calc2(ans, i):
    def calc (x,y):
        if i < len(y) and y[i] == "1":
            return x+1
        else:
            return x
    x1 = 0
    x1 = reduce(calc,ys,0)
    #print(x1,x0)
    ans += x1 * (len(ys)-x1) * (2**(i))
    ans %= 10**9 + 7
    return ans
ans = reduce(calc2, range(k), 0)
print(ans)


### FIXED CODE ###

words = lambda t : list(map(t, input().split()))
n = int(input())
xs = words(int)

ys = [0]*60
for x in xs:
    for i in range(60):
        if x == 0:
            continue
        ys[i] += x & 1
        x = x >> 1

ans = 0

for i,yi in enumerate(ys):
    ans += 2**(i) * yi * (n-yi)
    ans %= 10**9 + 7
print(ans)
### BUGGY CODE ###

K=int(input());q=[(1,1)];m={}
while len(q):
 n,s=q.pop()
 if not n in m:m[n]=s;q+=[(n*10%K,s)];q=[((n+1)%K,s+1)]+q
 if n==0:print(s);exit()

### FIXED CODE ###

from collections import deque

que = deque()

K = int(input())

que.append((1, 1))
visited = {}

while len(que) != 0:
    num, step = que.popleft()
    if num in visited:
        continue
    visited[num] = step
    que.appendleft((num * 10 % K, step))
    que.append(((num + 1) % K, step + 1))

print(visited[0])
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
m = 1000000007
S = 0
for i in range(n):
    for j in range(i+1, n, 1):
        S += a[i] * a[j] % m
print(S % m)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
m = 1000000007
S = 0
Q = sum(a)
for i in range(n):
    Q -= a[i]
    S += a[i] * Q % m
print(S % m)
### BUGGY CODE ###

# 2019/09/01
# AtCoder Beginner Contest 139 - D

# Input
n = int(input())
plist = list()
mlist = list()

# Make List
p = n
asum = n % 1
plist.append(p)
plist.append(asum)

for i in range(2, n + 1):
    p = i - 1
    plist.append(p)
    mlist.append(p % i)
    asum = asum + p % i

# Output
print(asum)


### FIXED CODE ###

# 2020/08/16
# AtCoder Beginner Contest 139 - D

# Input
n = int(input())

# Calc
ans = n * (n-1) // 2

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

import numpy as np
from scipy.sparse.csgraph import csgraph_from_dense, shortest_path
n, m, *AB = map(int, open(0).read().split())
graph = [[10**9]*n for _ in range(n)]
for a, b in zip(AB[::2], AB[1::2]):
    graph[a-1][b-1] = 1
    graph[b-1][a-1] = 1
G = csgraph_from_dense(graph)
d, p = shortest_path(G, indices=0, method='D', return_predecessors=1)
if np.any(d > 10**9-1):
    print('No')
else:
    print('Yes')
    print(*map(lambda x: int(x)+1, p[1:]), sep='\n')

### FIXED CODE ###

from collections import deque
n, m, *AB = map(int, open(0).read().split())
graph = [[] for _ in range(n)]
for a, b in zip(AB[::2], AB[1::2]):
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

d = [0] * n
queue = deque([0])
while queue:
    current_node = queue.popleft()
    for next_node in graph[current_node]:
        if d[next_node] == 0:
            d[next_node] = current_node+1
            queue.append(next_node)
print('Yes')
print(*d[1:], sep='\n')