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

N = int(input())
S = str(input())

ans = float("inf")
E = S.count("E")
W = S.count("W")
for i, v in enumerate(S):
    left = S[:i]
    left_E = left.count("E")
    left_W = left.count("W")
    if v == "E":
        right_E = E - left_E - 1
    else:
        right_E = E - left_E
    ans = min(ans, left_W + right_E)


print(ans)


### FIXED CODE ###

import numpy as np
N = int(input())
S = str(input())

E = np.cumsum([1 if s == "E" else 0 for s in S])
W = np.cumsum([1 if s == "W" else 0 for s in S])

ans = float("inf")
for i, v in enumerate(S):
    if v == "E":
        ans = min(ans, (E[-1] - E[i]) + W[i])
    else:
        ans = min(ans, (E[-1] - E[i]) + W[i] - 1)
    

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

def main():
    from itertools import accumulate
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        for i,t in enumerate(a):
            if(j:=i-t)<0:j=0
            b[j]+=1
            if(j:=i-~t)<n:b[j]-=1
        *a,=accumulate(b)
        if min(a)==n:break
    print(' '.join(map(str,a)))
main()

### FIXED CODE ###

def main():
    n,k,*a=map(int,open(0).read().split())
    for _ in range(k):
        b=[0]*n
        m=10**18
        for i,t in enumerate(a):
            if t<m:m=t
            b[max(0,i-t)]+=1
            if i-~t<n:b[i-~t]-=1
        if m>=n:break
        for i in range(n-1):b[i+1]+=b[i]
        a=b
    print(' '.join(map(str,a)))
main()
### BUGGY CODE ###

K = int(input())
S = 7

for i in range(K+1):
    if int(S) % K != 0:
        S = S * 10 + 7
    else:
        print(i+1)
        break

if i >= K:
    print('-1')


### FIXED CODE ###

K = int(input())
if K % 2 == 0:
    print(-1)
elif K % 5 == 0:
    print(-1)
else:
    S = 7
    for i in range(K+1):
        if S % K == 0:
            print(i+1)
            break
        else:
            S = S % K
            S = S * 10 + 7
    else:
        print(-1)
### BUGGY CODE ###

#j-i=Ai+Aj(j>i)
#j-Aj=Ai+i

#Lj=Ri=X
from bisect import bisect_left

def main():
    N=int(input())
    A=list(map(int,input().split()))

    L={}
    R={}
    for i in range(N):
        l=(i+1)-A[i]
        r=A[i]+i+1
        if (l in L.keys()):
            L[l].append(i+1)
        else:
            L[l]=[i+1]
        if (r in R.keys()):
            R[r].append(i+1)
        else:
            R[r]=[i+1]
    
    L_zip=zip(L.keys(),L.values())
    R_zip=zip(R.keys(),R.values())

    L_zip=sorted(L_zip)
    R_zip=sorted(R_zip)

    R_key,R_value=zip(*R_zip)

    res=0


    for l,l_index in L_zip:
        if l>0:
            ind=bisect_left(R_key ,l)
            if R_key[ind]==l:
                for l in l_index:
                    for r in R_value[ind]:
                        if l>r:
                            res+=1
            if ind>=1:
                R_key=R_key[ind-1:]
                R_value=R_value[ind-1:]

    print(res)

if __name__=="__main__":
    main()





### FIXED CODE ###

#j-i=Ai+Aj(j>i)
#j-Aj=Ai+i

#Lj=Ri=X
from bisect import bisect_left

def main():
    N=int(input())
    A=list(map(int,input().split()))

    L={}
    R={}

    res=0

    for i in range(N):
        l=(i+1)-A[i]
        r=A[i]+i+1
        if (l in R.keys()):
            res+=len(R[l])
        if (r in R.keys()):
            R[r].append(i+1)
        else:
            R[r]=[i+1]


    print(res)

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

from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n,w = li()
l = []
for i in range(n):l.append(li())
l.sort()
d = defaultdict(int)
for i in l:

    for j in sorted(list(d),reverse=1):
        if j + i[0] <= w:
            d[j + i[0]] = max(d[j + i[0]],d[j] + i[1])
    d[i[0]] = max(d[i[0]],i[1])
print(max(d.values()))


### FIXED CODE ###

from decimal import *
from bisect import bisect_left as bl
from bisect import bisect_right as br
from heapq import heappush,heappop
import math
from collections import *
from functools import reduce,cmp_to_key
import sys
input = sys.stdin.readline

M = mod = 998244353
def factors(n):return sorted(set(reduce(list.__add__, ([i, n//i] for i in range(1, int(n**0.5) + 1) if n % i == 0))))
def inv_mod(n):return pow(n, mod - 2, mod)

def li():return [int(i) for i in input().rstrip('\n').split()]
def st():return input().rstrip('\n')
def val():return int(input().rstrip('\n'))
def li2():return [i for i in input().rstrip('\n')]
def li3():return [int(i) for i in input().rstrip('\n')]
def li4():return [float(i) for i in input().rstrip('\n').split(' ')]

n,w = li()
l = []
for i in range(n):l.append(li())
l.sort()
d = defaultdict(int)
for i in range(10**5 + 10):d[i] = float('inf')
for i in l:

    for j in range(10 ** 5 + 10,0,-1):
        d[j + i[1]] = min(d[j + i[1]],d[j] + i[0])
    d[i[1]] = min(d[i[1]],i[0])
ans = 0
for i in range(10**5 + 10):
    if d[i] <= w:ans = i
print(ans)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
import networkx as nx
ans = (-float("inf"), None)
for f in range(1,n*k+1):
    g = nx.DiGraph()
    for i in range(2*n):
        g.add_node(i)
    g.add_node(2*n, demand=-f)
    g.add_node(2*n+1, demand=f)
    for i in range(n):
        g.add_edge(2*n, i, capacity=k, weight=0)
        g.add_edge(i+n, 2*n+1, capacity=k, weight=0)

    for i in range(n):
        for j in range(n):
            g.add_edge(i, j+n, capacity=1, weight=-a[i][j])
    val, d = nx.network_simplex(g)
    vals = [["."]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            if d[i][j+n]==1:
                vals[i][j] = "X"
    if -val>ans[0]:
        ans = (-val, vals)
print(ans[0])
print("\n".join("".join(ans[1][i]) for i in range(n)))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
a = [list(map(int, input().split())) for _ in range(n)]
import networkx as nx
ans = (-float("inf"), None)
f = n*k
g = nx.DiGraph()
for i in range(2*n):
    g.add_node(i)
g.add_node(2*n, demand=-f)
g.add_node(2*n+1, demand=f)
for i in range(n):
    g.add_edge(2*n, i, capacity=k, weight=0)
    g.add_edge(i+n, 2*n+1, capacity=k, weight=0)
g.add_edge(2*n, 2*n+1, capacity=f, weight=0)
for i in range(n):
    for j in range(n):
        g.add_edge(i, j+n, capacity=1, weight=-a[i][j])
val, d = nx.network_simplex(g)
vals = [["."]*n for _ in range(n)]
for i in range(n):
    for j in range(n):
        if d[i][j+n]==1:
            vals[i][j] = "X"
if -val>ans[0]:
    ans = (-val, vals)
print(ans[0])
print("\n".join("".join(ans[1][i]) for i in range(n)))
### BUGGY CODE ###

n = int(input())

def num_divisors_table(n):
    table = [0] * (n + 1)
    
    for i in range(1, n + 1):
        for j in range(i, n + 1, i):
            table[j] += 1
    
    return table

a = num_divisors_table(n)
b = 0
for i in range(1, n+1):
    b += i * a[i]
print(b)

### FIXED CODE ###

n = int(input())
def div(n):
    a = 0
    for i in range(1, n+1):
        y = int(n/i)
        a += y* (y+1)*i/2
    return int(a)
print(div(n))
### BUGGY CODE ###

import random
import sys
import time
import copy

input = sys.stdin.readline

def main():
    d = int(input())
    c = list(map(int, input().split()))
    s = []
    for _ in range(d):
        s.append(list(map(int, input().split())))
    
    start_time = time.time()
    beamwidth = 10
    ans = [[] for _ in range(beamwidth)]
    suff = 0
    # while True:
    #     elapsed_time = time.time() - start_time
    #     if elapsed_time >= 1.8:
    #         break
        
    # ここから
    topk = [{"last": [0 for _ in range(26)], "score": 0, "ans": []} for _ in range(beamwidth)]
    for i in range(d):
        # print(i)
        # print(*topk, sep='\n')
        # 各候補に対して top-k を生成
        nnnnn = []  # top-k * top-k 
        for bi in range(beamwidth):
            last = topk[bi]["last"]
            tmpsufss = []
            for con in range(26):
                tmpsufss.sort(key=lambda x: -x["score"])
                ttttt = topk[bi]["score"] + s[i][con]
                minus = 0
                for j in range(26):
                    if con == j:
                        continue
                    minus -= (i - last[j]) * c[j]
                ttttt += minus

                if len(tmpsufss) < beamwidth:
                    tmpsufss.append({
                        "last": last,
                        "score": ttttt,
                        "ans": copy.deepcopy(topk[bi]["ans"])
                    })
                    tmpsufss[-1]["last"][con] = i
                    tmpsufss[-1]["ans"].append(con)
                else:
                    if tmpsufss[-1]["score"] < ttttt:
                        tmpsufss.pop()
                        tmpsufss.append({
                            "last": last,
                            "score": ttttt,
                            "ans": copy.deepcopy(topk[bi]["ans"])
                        })
                        tmpsufss[-1]["last"][con] = i
                        tmpsufss[-1]["ans"].append(con)
            nnnnn.extend(tmpsufss)

        nnnnn.sort(key=lambda x: -x["score"])
        topk = nnnnn[:beamwidth]
        

    print(*[a + 1 for a in topk[0]["ans"]])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import random
import sys
import time

input = sys.stdin.readline

def main():
    # start_time = time.time()
    # while True:
    #     elapsed_time = time.time() - start_time
    #     if elapsed_time >= 2.0:
    #         print(elapsed_time)
    #         return 0
    d = int(input())
    c = list(map(int, input().split()))
    s = []
    for _ in range(d):
        s.append(list(map(int, input().split())))
    for _ in range(d):
        print(1)

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

import sys
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
edges = [[] for _ in range(N+1)]
for i in range(N-1):
    a, b = map(int, input().split())
    edges[a].append(b)
    edges[b].append(a)

task = [[] for _ in range(N+1)]
for i in range(Q):
    p, x = map(int, input().split())
    task[p].append(x)

task_sum = [[] for _ in range(N+1)]
for i in range(N+1):
    task_sum[i].append(sum(task[i]))

#print('task_sum:', task_sum)

cnt = [[] for i in range(N+1)]

#最初はdfs(1, -1, task_sum[1])

def dfs(v, p, cost):
        
    for nv in edges[v]:
        if nv == p:
            continue
        
        dfs(nv, v, cost+task_sum[nv])

    cnt[v].append(cost)

dfs(1, -1, task_sum[1])


for i in range(1, N+1):
    print(int(sum(cnt[i][0])), end=' ')



### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

N, Q = map(int, input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]
 
g = [[] for _ in range(N+1)]
for a,b in AB:
    g[a].append(b)
    g[b].append(a)
 
cnt = [0] * (N+1)
for p,x in PX:
    cnt[p] += x

def dfs(v, p, add):
    cnt[v] += add
    for nv in g[v]:
        if nv == p:
            continue
        dfs(nv, v, cnt[v])

dfs(1, 0, 0)

print(' '.join(map(str, cnt[1:])))
### BUGGY CODE ###

import copy

import fractions

def longgcd(S):
    if len(S)==2:
        return fractions.gcd(S[0],S[1])
    else:
        x=S[0]
        for i in range(0,N):
            x=fractions.gcd(x,S[i])
        return x

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

m=0

for i in range(0,N):
    B=copy.copy(A)
    B[i]=0
    x=longgcd(B)
    if x>m:
        m=x
print(m)


### FIXED CODE ###

def gcd(n,m):#n,mは正の整数、最大公約数　許容は？
    if n==0:
        return m
    elif m==0:
        return n
    elif n>m:
        n=n%m
        return gcd(n,m)
    else:
        m=m%n
        return gcd(n,m)

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

list1=[1 for i in range(0,N)]
list2=[1 for i in range(0,N)]
list1[0]=A[0]
list2[0]=A[N-1]

for i in range(1,N):
    list1[i]=gcd(list1[i-1],A[i])
    list2[i]=gcd(list2[i-1],A[N-1-i])
m=list2[N-2]
for i in range(0,N-2):
    test=gcd(list1[i],list2[N-3-i])
    if test>m:
        m=test
test=list1[N-2]
if test>m:
    m=test
print(m)
### BUGGY CODE ###

n = int(input())
a = list(input().split())
for i in range(1,n+1):
    i = str(i)
    if i in a:
        print(a.count(i))
    else:
        print(0)

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
x = collections.Counter(a)
for i in range(1,n+1):
    print(x[i])
### BUGGY CODE ###

A, B, K = map(int, input().split())
list = [i for i in range(A, B+1)]
list1 = list[:K]
list2 = list[(B-K-A+1):]
lists = sorted(set(list1 + list2))
for i in lists:
    print(i)

### FIXED CODE ###

A, B, K = map(int, input().split())
list = [i for i in range(A, A+K)]
list.extend(i for i in range(B+1-K, B+1))
list = sorted(set(list))
for i in list:
    if A<=i<=B:
        print(i)
### BUGGY CODE ###

N,M=map(int,input().split())
H=list(map(int,input().split()))
L=[]
for i in range(M):
  L.append(list(map(int,input().split())))
#print(L)
ans=[i for i in range(N)]
for i in range(M):
  ori=L[i][0]-1
  dest=L[i][1]-1
 # print(ori,dest)
  if H[ori] <= H[dest]:
    if ori in ans: ans.remove(ori)
  if H[ori] >= H[dest]:
    if dest in ans: ans.remove(dest)

#print(ans)
print(len(ans))

### FIXED CODE ###

N,M=map(int,input().split())
H=list(map(int,input().split()))
L=[]
for i in range(M):
  L.append(list(map(int,input().split())))
#print(L)
bad=[]
for i in range(M):
  ori=L[i][0]-1
  dest=L[i][1]-1
 # print(ori,dest)
  if H[ori] <= H[dest]:
    bad.append(ori)
  if H[ori] >= H[dest]:
    bad.append(dest)

deletes=set(bad)
print(N-len(deletes))
#print(ans)
#print(len(ans))
### BUGGY CODE ###

n=int(input())
if n==1:
    print(1)
else:
    g=[list(map(int,input().split())) for i in range(n-1)]
    
    edge_sum=0
    
    for l in range(1,n+1):
        for r in range(l,n+1):
            edge_num=0
            edge_num += r-l+1
            for k in range(n-1):
                if l<=g[k][0]<=r and l<=g[k][1]<=r:
                    edge_num -= 1
            
            edge_sum +=edge_num
    print(edge_sum)

### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
    ans += i*(i+1)/2
for i in range(n-1):
    u,v=map(int,input().split())
    if u > v:
        u,v=v,u
    ans -= u*(n-v+1)
print(int(ans))
### BUGGY CODE ###

n=int(input())
i=0
j=n//2
print(i)
a=input()
print(j)
b=input()
if j%2and a!=b or not j%2and a==b:
    i,j=j,n-1
while 1:
    if j-i<2:
        print(i)
        s=input()
        if s=='Vacant':
            exit()
        print(j)
        exit()
    k=i+(j-i)//2
    print(k)
    c=input()
    if(k-i)%2and a==c:
        j=k
    else:
        i=k

### FIXED CODE ###

n=int(input())
i=0
j=n-1
print(i)
a=input()
print(j)
b=input()
while 1:
    if j-i<2:
        print(i)
        _=input()
        print(j)
        if input()!='Vacant':
            print('助けてくれ～～～')
    k=(j-i)//2+i
    print(k)
    c=input()
    if(k-i)%2and a==c or not(k-i)%2and a!=c:
        j=k
    else:
        a=c
        i=k
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)

n, q = map(int, input().split())
v = [set() for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].add(b)
  v[b].add(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  for i in v[p]:
    if i == prev:
      continue
    c[i] += c[p]
    addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

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

n, q = map(int, input().split())
v = [[] for _ in range(n+1)]
c = [0]*(n+1)

for _ in range(n-1):
  a, b = map(int, input().split())
  v[a].append(b)
  v[b].append(a)

for _ in range(q):
  p, x = map(int, input().split())
  c[p] += x

def addcount(p, prev):
  for i in v[p]:
    if i != prev:
      c[i] += c[p]
      addcount(i, p)
  return None
addcount(1, 0)
  
print(*c[1:])
### BUGGY CODE ###

import numpy as np
n = int(input())
s = input()
q = int(input())
al = "abcdefghijklmnopqrstuvwxyz"


def get(i):
    return np.identity(26)[al.index(i)]


bit = [np.zeros(26) for _ in range(n+1)]


def ko(i, j):
    global bit
    while i <= n:
        bit[i] += j
        i += i & (-i)


def su(i):
    s = np.zeros(26)
    while i != 0:
        s += bit[i]
        i -= i & (-i)
    return s


a = []
for i in range(n):
    ko(i + 1, get(s[i]))
    a.append(get(s[i]))
for _ in range(q):
    kind, i, j = [k for k in input().split()]
    i = int(i)
    if int(kind) == 1:
        ko(i, get(j)-a[i-1])
        a[i-1] = get(j)
    else:
        j = int(j)
        b = su(j) - su(i-1)
        k = 0
        for i in b:
            if i != 0:
                k += 1
        print(k)


### FIXED CODE ###

n = int(input())
s = input()
q = int(input())


class SegmentTree:
    def __init__(self, a, func=max, one=-10 ** 18):
        self.logn = (len(a) - 1).bit_length()
        self.n = 1 << self.logn
        self.func = func
        self.one = one

        self.b = [self.one] * (2 * self.n - 1)
        for i, j in enumerate(a):
            self.b[i + self.n - 1] = j
        for i in reversed(range(self.n - 1)):
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_item(self, i):
        return self.b[i + self.n - 1]

    def update(self, index, x):
        i = index + self.n - 1
        self.b[i] = x
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def update_func(self, index, x):
        i = index + self.n - 1
        self.b[i] = self.func(self.b[i], x)
        while i != 0:
            i = (i - 1) // 2
            self.b[i] = self.func(self.b[i * 2 + 1], self.b[i * 2 + 2])

    def get_segment(self, l, r, i=0):
        j = i - (1 << ((i + 1).bit_length() - 1))+1
        length = 1 << (self.logn - (i + 1).bit_length() + 1)
        ll = j * length
        rr = (j + 1) * length
        if l <= ll and rr <= r:
            return self.b[i]
        elif rr <= l or r <= ll:
            return self.one
        else:
            return self.func(self.get_segment(l, r, i * 2 + 1),
                             self.get_segment(l, r, i * 2 + 2))


def get_int(s):
    abc = "abcdefghijklmnopqrstuvwxyz"
    return 1<<abc.index(s)


seg = SegmentTree([get_int(i) for i in s], int.__or__, 0)

for _ in range(q):
    q, i, j = input().split()
    if q == "1":
        seg.update(int(i) - 1, get_int(j))
    else:
        aa = seg.get_segment(int(i) - 1, int(j))
        ans = 0
        for i in range(26):
            if (aa >> i) & 1 == 1:
                ans += 1
        print(ans)
### BUGGY CODE ###

def resolve():
    from heapq import heappush, heappop

    # 長点数V、直接移動先とコストを記したリストg、スタート地点rをとって、
    # rからiに行くまでの最低コストがdist[i]であることを意味するリストdistを返す関数
    def dijkstra(V, g, r):

        dist = [INF] * V
        queue = [(0, r)]  # queueの要素(c,v)は、コストcで直接vに行けることを意味する
        dist[r] = 0  # スタート地点rにはコスト0で行ける

        while queue:
            c, v = heappop(queue)
            if dist[v] < c:  # すでに記録されているコストの方が小さいので更新不要
                continue
            for cost, t in g[v]:
                if dist[v] + cost < dist[t]:
                    dist[t] = dist[v] + cost
                    heappush(queue, (dist[t], t))

        return dist

    N=int(input())
    V, E= N,N-1
    g = [[] for i in range(V)]

    for i in range(E):
        s, t, d = map(int, input().split())
        s,t,d=s-1,t-1,d
        g[s].append((d, t))
        g[t].append((d, s))# g[s]の要素(cost,t)はsからコストcostでtに直接行けることを意味する

    INF = 10 ** 20

    Q,K=map(int,input().split())
    l1=[INF]*V
    l2=[INF]*V
    for i in range(V):
        l1[i]=dijkstra(V, g, i)[K - 1]
        l2[i] = dijkstra(V, g, K-1)[i]

    for j in range(Q):
        x,y=map(int,input().split())
        print(l1[x-1]+l2[y-1])


resolve()

### FIXED CODE ###

import sys
from collections import deque

def solve():
    input = sys.stdin.readline
    N = int(input())
    Edge = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b, c = map(int, input().split())
        Edge[a-1].append((b-1, c))
        Edge[b-1].append((a-1, c))
    Q, K = map(int, input().split())
    q = deque()
    Dist = [-1] * N
    q.append((K-1, K-1, 0))
    while q:
        nowN, preN, nD = q.popleft()
        if Dist[nowN] == -1:
            Dist[nowN] = nD
            for e, add in Edge[nowN]:
                if e != preN: q.append((e, nowN, nD + add))
    Ans = [None] * Q
    for i in range(Q):
        x, y = map(int, input().split())
        Ans[i] = str(Dist[x-1] + Dist[y-1])
    print("\n".join(Ans))

    return 0

if __name__ == "__main__":
    solve()