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

import sys
import numpy as np
import random
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
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)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n = I()
	x, y = LI()
	for _ in range(n-1):
		t, a = LI()
		if x <= t and y <= a:
			x, y = t, a
		else:
			l = 1
			xl, yl = l*t, l*a
			while xl < x or yl < y:
				l += 1
				xl, yl = l*t, l*a
			x, y = xl, yl
	print(x+y)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import numpy as np
import random
import math
from decimal import Decimal
import itertools
import re
import bisect
from collections import deque, Counter
from functools import lru_cache

sys.setrecursionlimit(10**9)
INF = 10**13
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)]
def SERIES(n): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ')
def GRID(h,w): return np.fromstring(sys.stdin.buffer.read(), dtype=np.int32, sep=' ').reshape(h,-1)[:,:w]
def GRIDfromString(h,w): return np.frombuffer(sys.stdin.buffer.read(), 'S1').reshape(h,-1)[:,:w]
MOD = 1000000007

def main():
	n = I()
	x, y = 1, 1
	for _ in range(n):
		t, a = LI()
		m = max((x+t-1)//t,(y+a-1)//a)
		x, y = m*t, m*a
	print(x+y)


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

n=int(input())
l=[int(x) for x in input().split()]

l.sort()
ans=0
import itertools
# (1,2,3),(1,2,4),---,(7,8,9)
for seq in itertools.combinations(range(len(l)),3):
    if l[seq[0]]+l[seq[1]]>l[seq[2]]:ans+=1
print(ans)

### FIXED CODE ###

n=int(input())
l=[int(x) for x in input().split()]

l.sort()
ans=0

for i in range(len(l)-2):
    for j in range(i+2,len(l)):
        a=l[i]
        c=l[j]
        b_min=i+1
        b_max=j-1
        while b_max-b_min>1:
            if l[(b_max+b_min)//2]>c-a:
                b_max=(b_max+b_min)//2
            else:
                b_min=(b_max+b_min)//2
        if l[b_min]>c-a:ans+=j-b_min
        elif l[b_max]>c-a:ans+=j-b_max
print(ans)
### BUGGY CODE ###

import sys
from collections import Counter
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A.sort()

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i in nums:
                return False
            if i != n // i:
                divisors.append(n // i)
                if n // i in nums:
                    return False
    return True

nums = set()
used = set()
done = set()
ans = 0
for a in A:
    if a in used and a not in done:
        ans -= 1
        done.add(a)
    if make_divisors(a):
        if a not in used:
            ans += 1
            used.add(a)
    nums.add(a)
print(ans)

### FIXED CODE ###

import sys
from collections import Counter
N = int(sys.stdin.readline().rstrip())
A = list(map(int, sys.stdin.readline().rstrip().split()))
A_counters = Counter(A)
A.sort()
A_set = set(A)
ans = 0
for a in A:
    if a in A_set:
        if A_counters[a] == 1:
            ans += 1
        for i in range(1, A[-1] // a + 1):
            if a * i in A_set:
                A_set.remove(a * i)
print(ans)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
l_li=[]
r_li=[]
for i in range(q):
    l,r=map(int,input().split())
    l_li.append(l)
    r_li.append(r)
    
dp =[[0 for i in range(n)] for j in range(n)]

for j in range(n):
    t=0
    if s[j]=="C" and j!=0 and s[j-1]=="A":
        dp[0][j]=dp[0][j-1]+1
    else:
        dp[0][j]=dp[0][j-1]

for i in range(1,n):
    t=0
    if s[i]=="C" and s[i-1]=="A":   
        dp[i][i:n]=list(map(lambda x: x-1,dp[i-1][i:n]))
    else:
        dp[i][i:n]=dp[i-1][i:n]       
        
        
for i in range(q):
    print(dp[l_li[i]-1][r_li[i]-1])


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
    
dp =[0 for j in range(n)]


for j in range(n):
    t=0
    if s[j]=="C" and j!=0:
        if s[j-1]=="A":
            t=1

    dp[j]=dp[j-1]+t
        

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

import numpy as np
from functools import reduce
from fractions import gcd

n = int(input())
array = np.array(list(map(int, input().strip().split())))

reductive_gcd = lambda list_: list_[0] if len(list_) == 1 else reduce(gcd, list_)

print(max([reductive_gcd([array[i] for i in range(n) if i != j]) for j in range(n)]))


### FIXED CODE ###

from fractions import gcd

n = int(input())
list_ = list(map(int, input().strip().split()))

gcd_from_left = [0]
gcd_from_right = [0]
for i in range(n):
    gcd_from_left.append(gcd(gcd_from_left[i], list_[i]))
    gcd_from_right.append(gcd(gcd_from_right[i], list_[-(i + 1)]))

gcd_from_left.insert(0, 0)
gcd_from_right.insert(0, 0)
gcd_from_right.reverse()

print(max(gcd(gcd_from_left[i], gcd_from_right[i]) for i in range(n + 2)))
### BUGGY CODE ###

from collections import deque
def bfs(A,H,W,D):
    que = deque(D)
    cnt = 0
    d = [-1,1]
    tmp = deque([])
    flag = 0
    while que:
        u = que.popleft()
        y,x = u
        for k in range(2):
            s = y + d[k]
            t = x + d[k]
            if 0 <= s < H:
                if A[s][x] == '.':
                    A[s][x] = '#'
                    tmp.append((s,x))
                    flag = 1
            if 0 <= t < W:
                if A[y][t] == '.':
                    A[y][t] = '#'
                    tmp.append((y,t))
                    flag = 1
            
        if not que:
            que = tmp 
            tmp = deque([])
            if flag:
                cnt += 1
            flag = 0

    return cnt

def main():
    H,W = map(int,input().split(" "))
    A = []
    D = []
    D_append = D.append
    for i in range(H):
        tmp = []
        for j,s in enumerate(input()):
            tmp.append(s)
            if s == '#':
                D_append((i,j))
        A.append(tmp)

    ans = bfs(A,H,W,D)
    print(ans)


if __name__ == "__main__":
    main()
            

### FIXED CODE ###

from collections import deque
def bfs(A,H,W,D):
    que = deque(D)
    cnt = 0
    d = [-1,1]
    tmp = set()
    flag = 0
    while que:
        u = que.popleft()
        
        y,x = u
        for k in range(2):
            s = y + d[k]
            t = x + d[k]
            if 0 <= s < H:
                if A[s][x] == '.':
                    A[s][x] = '#'
                    tmp.add((s,x))
                    flag = 1
              
            if 0 <= t < W:
                if A[y][t] == '.':
                    A[y][t] = '#'
                    tmp.add((y,t))
                    flag = 1

            
        if not que:
            que = deque(tmp) 
            tmp = set()
            if flag:
                cnt += 1
            flag = 0
    return cnt

def main():
    H,W = map(int,input().split(" "))
    A = []
    D = []
    D_append = D.append
    for i in range(H):
        tmp = []
        for j,s in enumerate(input()):
            tmp.append(s)
            if s == '#':
                D_append((i,j))
        A.append(tmp)

    ans = bfs(A,H,W,D)
    print(ans)


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

N, M = map(int, input().split())
l = []
for i in range(M):
  a = input().split()
  l.append([int(a[0]), a[1]])

ansewered_question = set([l[i][0] for i in range(len(l))])

AC = 0
WA = 0
for i in ansewered_question:
    wa = 0
    for submit in l:
        if submit[0] == i:
            if submit[1] == "WA":
                wa += 1
            else:
                AC += 1
                WA += wa
                break

print(AC, WA)

### FIXED CODE ###

N, M = map(int, input().split())
l = []
ansewered_question = set()
submit_for = {}

for i in range(M):
  a = input().split()
  l.append([int(a[0]), a[1]])
  ansewered_question.add(int(a[0]))
for submition in l:
    if submition[0] in submit_for:
        submit_for[submition[0]].append(submition[1])
    else:
        submit_for[submition[0]] = [submition[1]]
AC = 0
WA = 0
for i in ansewered_question:
    wa = 0
    for submit in submit_for[i]:
      if submit == "WA":
        wa += 1
      else:
          AC += 1
          WA += wa
          break
print(AC, WA)
### BUGGY CODE ###

n = int(input())
x = list(map(int,input().split()))
ans = int(n/2-1)
for i in range(1,n+1):
    a = []
    a = x[:i-1] + x[i:]
    a.sort()
    print(a[ans])

### FIXED CODE ###

n = int(input())
x = list(map(int,input().split()))
a = sorted(x)
#print(a)
ans1 = a[int(n/2-1)]
ans2 = a[int(n/2)]
#print(ans1,ans2)
if ans1 == ans2:
    for i in range(n):
        print(ans1)
else:
    for i in range(n):
        if x[i] < ans2:
            print(ans2)
        else:
            print(ans1)
### BUGGY CODE ###

from collections import Counter

s = input()
N = len(s)

l = []
sum = 0

for i in range(N):
    if i == N-1:
        l.append(0)
    l.append(int(s[i:N])%2019)
    
c = Counter(l)
for key in c.keys():
    m = c[key]
    sum += m*(m-1)/2
print(int(sum))

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

n, t = list(map(int, input().split()))
dishes = [list(map(int, input().split())) for _ in range(n)]

dishes.sort(key = lambda x: (x[0], -x[1]))
#print(dishes)

# dp[i][j]はi番目までの品物から時間の和がj以下なるように選んだときの価値の和の最大値を表す。
dp = [[-1 for _ in range(t + 1)] for _ in range(n + 1)]

for j in range(t):
	dp[0][j] = 0

for i in range(n):
	for j in range(t):
		if j - dishes[i][0] >= 0:
			dp[i + 1][j] = max(dp[i][j], dp[i][j - dishes[i][0]] + dishes[i][1])
		else:
			dp[i + 1][j] = dp[i][j]
	dp[i + 1][t] = max(dp[i][t], dp[i][t - 1] + dishes[i][1])

#print(dp)
print(dp[-1][-1])

### FIXED CODE ###

n, t = list(map(int, input().split()))
dishes = [list(map(int, input().split())) for _ in range(n)]

dishes.sort(key = lambda x: (x[0], -x[1]))
#print(dishes)

# dp[i][j]はi番目までの品物から時間の和がj以下なるように選んだときの価値の和の最大値を表す。
dp = [[-1 for _ in range(t + 1)] for _ in range(n + 1)]

for j in range(t):
	dp[0][j] = 0

for i in range(n):
	for j in range(t):
		if j - dishes[i][0] >= 0:
			dp[i + 1][j] = max(dp[i][j], dp[i][j - dishes[i][0]] + dishes[i][1])
		else:
			dp[i + 1][j] = dp[i][j]
	dp[i + 1][t] = max(dp[i][t], dp[i][t - 1] + dishes[i][1])

#print(dp)
print(dp[-1][-1])
### BUGGY CODE ###

n = int(input())
a = []
for i in range(5):
    a.append(int(input()))
nn = [0] * 6
nn[0] = n
count = 0
while nn[5] != n:
    idou_1 = min(a[0],nn[0])
    idou_2 = min(a[1],nn[1])
    idou_3 = min(a[2],nn[2])
    idou_4 = min(a[3],nn[3])
    idou_5 = min(a[4],nn[4])
    nn[0] -= idou_1
    nn[1] += idou_1
    nn[1] -= idou_2
    nn[2] += idou_2
    nn[2] -= idou_3
    nn[3] += idou_3
    nn[3] -= idou_4
    nn[4] += idou_4
    nn[4] -= idou_5
    nn[5] += idou_5
    count += 1
    #if nn[5] == n:
        #break
    #print(nn)
print(count)

### FIXED CODE ###

import math
n = int(input())
a = [int(input()) for i in range(5)]
print(math.ceil(n/min(a[0],a[1],a[2],a[3],a[4]))+4)
### BUGGY CODE ###

import math
import sys
input = sys.stdin.readline
def main():
	H,N = map(int,input().split())
	A,B = [],[]
	for _ in range(N):
		a,b = map(int,input().split())
		A.append(a)
		B.append(b)
	
	dp = [[0 for _ in range(H+1)] for _ in range(N)]
	
	for i in range(1,H+1):
		dp[0][i] = math.ceil(i/A[0])*B[0]

	for i in range(1,N):
		for j in range(1,H+1):
			if j<=A[i]:
				dp[i][j] = min(dp[i-1][j],B[i])
			else:
				dp[i][j] = min([dp[i-1][j],dp[i-1][j-A[i]]+B[i],
										   dp[i][j-A[i]]+B[i]])

	print(dp[N-1][H])
if __name__ == '__main__':
	main()

### FIXED CODE ###

import math
import sys
input = sys.stdin.readline
def main():
	H,N = map(int,input().split())
	A,B = [],[]
	ap = A.append
	bp = B.append
	for _ in range(N):
		a,b = map(int,input().split())
		ap(a)
		bp(b)
	
	dp = [[0 for _ in range(H+1)] for _ in range(N)]
	
	for i in range(1,H+1):
		dp[0][i] = math.ceil(i/A[0])*B[0]

	for i in range(1,N):
		for j in range(1,H+1):
			if j<=A[i]:
				dp[i][j] = min(dp[i-1][j],B[i])
			else:
				dp[i][j] = min(dp[i-1][j],dp[i][j-A[i]]+B[i])

	print(dp[N-1][H])
if __name__ == '__main__':
	main()
### BUGGY CODE ###

n = int(input())
pwr = 1
for i in range(1,n+1):
    pwr = pwr*i
print(pwr%(10**9+7))

### FIXED CODE ###

n = int(input())
pwr = 1
for i in range(1,n+1):
    pwr = pwr*i
    pwr = pwr%(10**9+7)
print(pwr)
### BUGGY CODE ###

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

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

print(ans)


### FIXED CODE ###

from collections import defaultdict
n = int(input())
a = list(map(int, input().split()))

left = defaultdict(int)
for i in range(n):
    left[i + a[i]] += 1

ans = 0
for i in range(n):
    sub = i - a[i]
    if sub in left:
        ans += left[sub]

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

import sys
from itertools import accumulate

readline = sys.stdin.readline
INF = 10 ** 9
h, w, k = map(int, readline().split())
s = [readline() for _ in range(h)]

ans = INF
for bit in range(2**h-1):
    cut = bin(bit).count('1')
    group = 0
    peace = [[0] * (bin(bit).count('1') + 1) for _ in range(w)]

    for i in range(w):
        group = 0
        for j in range(h):
            if s[j][i] == '1':
                peace[i][group] += 1
            if bit >> j & 1:
                group += 1

    if any(max(col) > k for col in peace):
        continue
    current = [0] * (bin(bit).count('1') + 1)
    for i in range(w):
        current = list(map(sum, zip(current, peace[i])))
        if max(current) > k:
            cut += 1
            current = peace[i]
    if ans > cut:
        ans = cut

print(ans)


### FIXED CODE ###

import sys
from itertools import accumulate

readline = sys.stdin.readline
INF = 10 ** 9
h, w, k = map(int, readline().split())
s = [readline() for _ in range(h)]

ans = INF
for bit in range(2**h-1):
    cut = bin(bit).count('1')
    group = 0
    peace = [[0] * (bin(bit).count('1') + 1) for _ in range(w)]

    for i in range(w):
        group = 0
        for j in range(h):
            if s[j][i] == '1':
                peace[i][group] += 1
            if bit >> j & 1:
                group += 1

    if any(max(col) > k for col in peace):
        continue
    current = [0] * (bin(bit).count('1') + 1)
    for i in range(w):
        current = list(map(sum, zip(current, peace[i])))
        if max(current) > k:
            cut += 1
            current = peace[i]
    if ans > cut:
        ans = cut

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

N=int(input())
P=list(map(int,input().split()))

ct=0
for i in range(N):
  if min(P[:i+1]) ==P[i]:
    ct+=1

print(ct)

### FIXED CODE ###

import numpy as np
N=int(input())
P=list(map(int,input().split()))

ct=0
min_p=P[0]
for i in range(N):
	if P[i]<=min_p:
		min_p=P[i]
		ct+=1


print(ct)
### BUGGY CODE ###

c=int(input())
p=1
m=10**9+7
for i in range(c):
  p*=i+1
print(p%m)

### FIXED CODE ###

c=int(input())
p=1
m=10**9+7
for i in range(2,c+1):
  p=(p*i)%m
print(p)
### BUGGY CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

H, W = list(map(int,input().split()))
A = []
for i in range(H):
	A.append(input())

dist = [[10000000 for i in range(W)] for j in range(H)]

for i in range(H):
	for j in range(W):
		que = deque()
		if A[i][j] == '#':
			dist[i][j] = 0
			que.append([i, j])
			while len(que) > 0:
				loc = que.popleft()
				if loc[0] < H - 1 and A[loc[0] + 1][loc[1]] == "." and dist[loc[0] + 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
					dist[loc[0] + 1][loc[1]] = dist[loc[0]][loc[1]] + 1
					que.append([loc[0] + 1, loc[1]])
				if loc[0] > 0 and A[loc[0] - 1][loc[1]] == "." and dist[loc[0] - 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
					dist[loc[0] - 1][loc[1]] = dist[loc[0]][loc[1]] + 1
					que.append([loc[0] - 1, loc[1]])
				if loc[1] < W - 1 and A[loc[0]][loc[1] + 1] == "." and dist[loc[0]][loc[1] + 1] > dist[loc[0]][loc[1]] + 1:
					dist[loc[0]][loc[1] + 1] = dist[loc[0]][loc[1]] + 1
					que.append([loc[0], loc[1] + 1])
				if loc[1] > 0 and A[loc[0]][loc[1] - 1] == "." and dist[loc[0]][loc[1] - 1] > dist[loc[0]][loc[1]] + 1:
					dist[loc[0]][loc[1] - 1] = dist[loc[0]][loc[1]] + 1
					que.append([loc[0], loc[1] - 1])

num = 0
for i in range(H):
	for j in range(W):
		num = max(num, dist[i][j])

print(num)







### FIXED CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

H, W = list(map(int,input().split()))
A = []
for i in range(H):
	A.append(input())

dist = [[10000000 for i in range(W)] for j in range(H)]

now = deque()
for i in range(H):
	for j in range(W):
		if A[i][j] == "#":
			now.append([i,j])
			dist[i][j] = 0


while len(now) > 0:
	loc = now.popleft()
	if loc[0] < H - 1 and dist[loc[0] + 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0] + 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0] + 1, loc[1]])
	if loc[0] > 0 and dist[loc[0] - 1][loc[1]] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0] - 1][loc[1]] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0] - 1, loc[1]])
	if loc[1] < W - 1 and dist[loc[0]][loc[1] + 1] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0]][loc[1] + 1] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0], loc[1] + 1])
	if loc[1] > 0 and dist[loc[0]][loc[1] - 1] > dist[loc[0]][loc[1]] + 1:
		dist[loc[0]][loc[1] - 1] = dist[loc[0]][loc[1]] + 1
		now.append([loc[0], loc[1] - 1])

num = 0
for i in range(H):
	for j in range(W):
		num = max(num, dist[i][j])
print(num)
### BUGGY CODE ###

#!/usr/bin/env python3
a = [0] + list(map(int, list(input())))
n = len(a)
dp = [[10 ** 9] * 2 for _ in range(n + 1)]
dp[0][0] = 0
dp[0][1] = 1
for i in range(n):
    dp[i + 1][0] = min(dp[i][0] + a[i], dp[i][1] + 10 - a[i])
    dp[i + 1][1] = min(dp[i][0] + a[i] + 1, dp[i][1] + 10 - a[i] - 1)
print(dp[n][0])


### FIXED CODE ###

#!/usr/bin/env python3
a = [0] + list(map(int, list(input())))
n = len(a)
dp = [[10 ** 9] * 2 for _ in range(n + 1)]
dp[0][0] = 0
dp[0][1] = 1
for i in range(n):
    dp[i + 1][0] = min(dp[i][0] + a[i], dp[i][1] + 10 - a[i])
    dp[i + 1][1] = min(dp[i][0] + a[i] + 1, dp[i][1] + 10 - a[i] - 1)
print(dp[n][0])
### BUGGY CODE ###

N = int(input())

min_f = len(str(N))
for a in range(1, N):
  if N % a != 0:
    continue
  b = int(N / a)
  f = max(len(str(a)), len(str(b)))
  if min_f > f:
    min_f = f
  if a**2 > N:
    break

print(min_f)

### FIXED CODE ###

import math

N = int(input())

min_f = len(str(N))
for a in range(1, int(math.sqrt(N)) + 1):
  if N % a != 0:
    continue
  b = int(N / a)
  f = max(len(str(a)), len(str(b)))
  if min_f > f:
    min_f = f

print(min_f)
### BUGGY CODE ###

# -*- coding:utf-8 -*-

N=int(input())
S=input()
S=list(S)
number=0
ans=[]
for i in range(N):
  Left=S[:i]
  Right=S[i+1:]
  number+=Left.count('W')
  number+=Right.count('E')
  ans.append(number) 
  number=0
print(min(ans))

### FIXED CODE ###

n = int(input())
s = input()
e = s.count("E")
w = s.count("W")
cnt1 = 0
cnt2 = 0
ans = 10e9
for i in s:
    if i=="E":
        cnt1 += 1
        ans = min(ans,cnt2+e-cnt1)
    else:
        ans = min(ans,cnt2+e-cnt1)
        cnt2 += 1
print(ans)
### BUGGY CODE ###

import sys, math, collections, heapq, itertools
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    event = []
    for i in range(N):
        s, t, x = map(int, line_input())
        event.append((max(s-x, -1), 1, x))
        event.append((max(t-x, 0), -1, x))
    for i in range(Q):
        d = int(single_input())
        event.append((d, 2, d))
    event.sort()
    stop = set()
    ans = ""
    for time, parameter, co in event:
        if parameter == 1: stop |= {co}
        elif parameter == -1: stop -= {co}
        else:
            if stop:
                ans += str(min(stop)) + "\n"
            else: ans += "-1\n"
    print(ans)
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys, collections, heapq
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()

def solve():
    N, Q = map(int, line_input())
    event = []
    for i in range(N):
        s, t, x = map(int, line_input())
        event.append((s-x, 1, x))
        event.append((t-x,-1, x))
    for i in range(Q):
        d = int(single_input())
        event.append((d, 2, d))
    event.sort()
    candidate = []
    heapq.heapify(candidate)
    stop = collections.defaultdict(int)
    ans = ""
    for time, parameter, co in event:
        if parameter == 1:
            heapq.heappush(candidate, co)
            stop[co] += 1
        elif parameter == -1:
            stop[co] -= 1
        else:
            while candidate:
                x = heapq.heappop(candidate)
                if stop[x] > 0:
                    heapq.heappush(candidate, x)
                    ans += str(x) + "\n"
                    break
            else: ans += "-1\n"
    print(ans)

    return 0

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

from collections import deque
def solve():
  n = int(input())
  treepath = [[False]*n for _ in range(n)]
  treenode = [[]*n for _ in range(n)]
  treecolor = [-1]*n
  for i in range(n-1):
    u,v,w = (int(i) for i in input().split())
    u -= 1
    v -= 1
    treenode[u].append(v)
    treenode[v].append(u)
    treepath[u][v] = w%2
    treepath[v][u] = w%2
  query = deque([(0,0,0)])
  while query:
    a,b,c = query.popleft()
    if b%2 == 0:
      treecolor[a] = c
      nextc = c
    else:
      treecolor[a] = 1^c
      nextc = 1^c
    for nextnode in treenode[a]:
      if treecolor[nextnode] != -1:
        continue
      else:
        query.append((nextnode,treepath[a][nextnode],nextc))  
        treecolor[nextnode] = -2
  #print(treecolor)
  for i in treecolor:
    print(i)
solve()

### FIXED CODE ###

import sys
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  treenode = [[] for _ in range(n)]
  treecolor = [-2]*n
  for i in range(n-1):
    u,v,w = (int(i) for i in input().split())
    u -= 1
    v -= 1
    treenode[u].append((v,w%2))
    treenode[v].append((u,w%2))
  query = deque([(0,0,0)])
  while query:
    a,b,c = query.popleft()
    if b%2 == 0:
      treecolor[a] = c
      nextc = c
    else:
      treecolor[a] = 1^c
      nextc = 1^c
    for nextnode,weight in treenode[a]:
      if treecolor[nextnode] != -2:
        continue
      else:
        query.append((nextnode,weight,nextc))  
        treecolor[nextnode] = -1
  for i in treecolor:
    print(i)
solve()