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

# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 7)

        MOD = 10 ** 9 + 7
        n, k  = [int(_) for _ in input().split()]
        adj = defaultdict(list)
        for i in range(n - 1):
            a, b = [int(_) for _ in input().split()]
            a -= 1
            b -= 1
            adj[a].append(b)
            adj[b].append(a)
        done = [0] * n
        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                if rem <= 0:
                    return 0
                res *= rem * dfs(x, k - 2)
                res %= MOD
                rem -= 1
                if res == 0:
                    return 0
            return res

        print((dfs(0, k - 1) * k) % MOD)




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()


### FIXED CODE ###

# @author 

import sys

class EVirusTree2:

    def solve(self):
        from collections import defaultdict
        import sys
        sys.setrecursionlimit(10 ** 5 + 5)

        MOD = 10 ** 9 + 7
        n, k  = [int(_) for _ in input().split()]
        adj = defaultdict(list)
        for i in range(n - 1):
            a, b = [int(_) for _ in input().split()]
            a -= 1
            b -= 1
            adj[a].append(b)
            adj[b].append(a)
        done = [0] * n
        def dfs(s, rem):
            done[s] = 1
            if rem < 0:
                return 0
            res = 1
            for x in adj[s]:
                if done[x]:
                    continue
                if rem <= 0:
                    return 0
                res = (res * rem) % MOD
                res = (res * dfs(x, k - 2)) % MOD
                rem -= 1
                if res == 0:
                    return 0
            return res

        print((dfs(0, k - 1) * k) % MOD)




solver = EVirusTree2()
input = sys.stdin.readline

solver.solve()
### BUGGY CODE ###

import math
N, K = map(int, input().split())
As = list(map(int, input().split()))


def cut_num(a, cut_length):
    return math.ceil(a/cut_length) - 1


"""cut length N binary search
if cut num > K, search more longer cut length,
"""
l = 1
r = max(As)

ans = r
while True:
    m = (l+r)//2
    current_cut_num = sum([cut_num(a, m) for a in As])
    if current_cut_num <= K:
        r = m
    else:
        l = m

    if r - l < 1:
        break

if sum([cut_num(a, l) for a in As]) <= K:
    print(l)
else:
    print(r)

### FIXED CODE ###

import math
N, K = map(int, input().split())
As = list(map(int, input().split()))


def cut_num(a, cut_length):
    return math.ceil(a/cut_length) - 1


"""cut length N binary search
if cut num > K, search more longer cut length,
"""
l = 1
r = max(As)
m = (l+r)//2
ans = r
while r > l + 1:
    current_cut_num = sum([cut_num(a, m) for a in As])
    if current_cut_num <= K:
        r = m
    else:
        l = m
    m = (l+r)//2

if sum([cut_num(a, l) for a in As]) <= K:
    print(l)
else:
    print(r)
### BUGGY CODE ###

import re

def main():
    NumString = int(input())
    String = input()
    
    total_ans = 0
    for i in range(NumString):
        RGB = 'RGB'
        for j in range(i+1, NumString):
            if String[i] == String[j]:
                continue

            k_RGB = RGB.replace(String[i], '').replace(String[j], '')
            total_ans += String.count(k_RGB, j+1)
            if (j + (j-i)) < NumString and String[j + (j-i)] == k_RGB:
                total_ans -= 1
    
    print(total_ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

NumString = int(input())
String = input()

r_string_num, g_string_num, b_string_num = 0, 0, 0
for i_string in String:
    if i_string == 'R':
        r_string_num += 1
    elif i_string == 'G':
        g_string_num += 1
    else:
        b_string_num += 1
    
total_ans = r_string_num * g_string_num * b_string_num

exclude_num = 0
for i in range(NumString-2):
    for j in range(i+1, NumString-1):
        if (2*j - i) < NumString and String[i] != String[j] and \
            String[j] != String[2*j-i] and String[i] != String[2*j-i]:
            exclude_num += 1

total_ans -= exclude_num

print(total_ans)
### BUGGY CODE ###

n,a=int(input()),list(map(int,input().split()))
c=[0]*3
for i in a:c[i-1]+=1
x=[1/i for i in range(1,n+1)]
dp=[[[0]*(n+2) for i in range(n+2)]for i in range(n+2)]
for k in range(n+1):
  for j in range(n-k+1):
    for i in range(n-k-j+1):
      if n+1>i+j+k>0:
        dp[i][j][k]=(n+dp[i-1][j][k]*i+dp[i+1][j-1][k]*j+dp[i][j+1][k-1]*k)*x[i+j+k-1]
print(dp[c[0]][c[1]][c[2]])

### FIXED CODE ###

n,a=int(input()),map(int,input().split());c=[0]*3
for i in a:c[i-1]+=1
x,y,z=c;dp=[[[None]*(z+2) for i in range(n-x+2)]for i in range(n+2)];dp[0][0][0]=0
for k in range(z+1):
  for j in range(n-x-k+1):
    for i in range(n-k-j+1):
      if i+j+k:dp[i][j][k]=((dp[i-1][j][k]*i if i else 0)+(dp[i+1][j-1][k]*j if j else 0)+(dp[i][j+1][k-1]*k if k else 0)+n)/(i+j+k)
print(dp[x][y][z])
### BUGGY CODE ###

def main():
  n=int(input())
  num=[int(i) for i in input().split()]
  mod=10**9+7

  import math
  if max(num)==0:
    print(0)
    exit()
  l=math.ceil(math.log(max(num),2))

  ans=[0]*l
  tmp1,tmp2,tmp3=0,0,0
  for i in range(l):
    ans[i]=tmp3
    cnt=0
    for j in range(n):
      if (num[j]>>i)&1:
        cnt+=1
    tmp1=cnt*(n-cnt)
    tmp2=(ans[i]+tmp1)%2
    tmp3=(ans[i]+tmp1)//2
    ans[i]=tmp2

  a_append=ans.append
  while tmp3>0:
    a_append(tmp3%2)
    #print(tmp3)
    tmp3//=2
  #print(ans)
  ans=int(''.join([str(i) for i in ans[::-1]]),2)%mod
  print(ans)
  
if __name__=='__main__':
  main()


### FIXED CODE ###

def main():
  n=int(input())
  num=[int(i) for i in input().split()]
  mod=10**9+7

  import math
  if max(num)==0:
    print(0)
    exit()
  l=math.ceil(math.log(max(num),2))

  ans=[0]*l
  tmp1,tmp2,tmp3=0,0,0
  for i in range(l):
    ans[i]=tmp3
    cnt=0
    for j in range(n):
      if (num[j]>>i)&1:
        cnt+=1
    tmp1=cnt*(n-cnt)
    tmp2=(ans[i]+tmp1)%2
    tmp3=(ans[i]+tmp1)//2
    ans[i]=tmp2

  a_append=ans.append
  while tmp3>0:
    a_append(tmp3%2)
    #print(tmp3)
    tmp3//=2
  #print(ans)
  ans=int(''.join([str(i) for i in ans[::-1]]),2)%mod
  print(ans)
  
if __name__=='__main__':
  main()
### BUGGY CODE ###

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

if m==0:
    print(0,0)
    import sys
    sys.exit()

p=[list(input().split()) for _ in range(m)]
correct=set([p[i][0] for i in range(m) if p[i][1]=='AC'])

correct2=[]
sum_wa=0

for i in [p[j] for j in range(m) if p[j][0] in correct]:
    if i[0] in correct2:
        continue
    else:
        if i[1]=='WA':
            sum_wa+=1
        else:
            correct2.append(i[0])

print(len(correct),sum_wa)

### FIXED CODE ###

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

if m==0:
    print(0,0)
    import sys
    sys.exit()

p=[list(input().split()) for _ in range(m)]
correct=set([p[i][0] for i in range(m) if p[i][1]=='AC'])

s=set()
sum_wa=0

for i in [p[j] for j in range(m) if p[j][0] in correct]:
    if i[0] in s:
        continue
    else:
        if i[1]=='WA':
            sum_wa+=1
        else:
            s.add(i[0])

print(len(correct),sum_wa)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int, input().split()))

def kitai(x):
  a = 0
  b = 1
  t = x
  while t > 0:
    a += b
    b += 1
    t -= 1
  return a/x

isum = 0
keys = (0, 0)
for i in range(n):
  if i+k > n:
    break
  temp = p[i:i+k]
  if sum(temp) > isum:
    isum = sum(temp)
    keys = (i, i+k)

ans = 0
for i in p[keys[0]:keys[1]]:
  ans += kitai(i)
print(ans)

### FIXED CODE ###

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

def kitai(x):
  return (1+int(x))/2

p = list(map(kitai, input().split()))

pre = psum = sum(p[0:k])

for i in range(1, n):
  if i+k > n:
    break
  pre = pre - p[i-1] + p[i+k-1]
  psum = max(psum, pre)

print(psum)
### BUGGY CODE ###

n,m = map(int,input().split())
c  = [list(map(int,input().split())) for _ in range(m)]
a = [[] for _ in range(n)]
for i in range(m):
    a[c[i][0]-1].append(c[i][1])
for lis in a:
    lis.sort()
for i in range(m):
    upper_len = len(str(c[i][0]))
    if upper_len < 6:
        upper = '0'*(6-upper_len) + str(c[i][0])
    else:
        upper = str(c[i][0])
    index = a[c[i][0]-1].index(c[i][1]) + 1
    lower_len = len(str(index))
    if lower_len < 6:
        lower = '0'*(6-lower_len) + str(index)
    else:
        lower = str(index)
    print(upper+lower)

### FIXED CODE ###

n,m = map(int,input().split())
py = []
for i in range(m):
    num = i+1
    p,y = map(int,input().split())
    py.append([num,p,y])
py = sorted(py, key = lambda x:x[1]*10**10+x[2])
x = 0
b = '000000'
ans = []
for pyi in py:
    if pyi[1] != x:
        x = pyi[1]
        cnt = 1
    else:
        cnt += 1
    ans.append([pyi[0], (b+str(pyi[1]))[-6:], (b+str(cnt))[-6:]])
ans = sorted(ans, key = lambda x: x[0])
for ansi in ans:
    print(ansi[1]+ansi[2])
### BUGGY CODE ###

#dp[i][j]:S[i-x:i]==S[j-x:j]となる最大のx
import numpy as np

def solve(NS):
    N = NS[0]
    S = NS[1:]
    dp=np.zeros((N+1,N+1),dtype=int)
    for i in range(N - 1):
        for j in range(i + 1, N):
            dp[i][j] = min(j - i, dp[i - 1][j - 1] + 1) if S[i] == S[j] else 0
    return dp.max()

def main():
    NS = np.array([int(input())] + [ord(_) for _ in input()])
    print(solve(NS))

def cc_export():
    from numba.pycc import CC
    cc = CC('my_module')
    cc.export('solve', '(i8[:],)')(solve)
    cc.compile()

if __name__ == '__main__':
    import sys
    if sys.argv[-1] == 'ONLINE_JUDGE':
        cc_export()
        exit(0)
    #from my_module import solve
    main()


### FIXED CODE ###

import itertools
N = int(input())
S = input()
dp = [[0] * N for _ in range(N)]
ans = 0
for i, j in itertools.combinations(range(N), 2):
    if S[i] == S[j]:
        dp[i][j] = dp[i - 1][j - 1] + 1
    else:
        dp[i][j] = 0
    ans = max(ans, min(j - i, dp[i][j]))
print(ans)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0

for i in range(k+1):
    for j in range(k+1):
        for k in range(k+1):
            if i + j + k == s:
                count += 1

print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0

for x in range(k+1):
    for y in range(k+1):
        z =  s - x - y
        if 0 <= z & z <= k:
            count +=1
print(count)
### BUGGY CODE ###

n=int(input())
s=input()
cnt=0
a=[]
b=[]
c=[]
for i in range(n):
  d=s[i]
  if d in b:continue
  else:b.append(d)
  for j in range(i+1,n):
    d=s[i]+s[j]
    if d in c:continue
    else:c.append(d)
    for k in range(j+1,n):
      e=s[i]+s[j]+s[k]
      if e not in a:
        a.append(e)
        cnt+=1
print(cnt)

### FIXED CODE ###

n=int(input())
s=input()
cnt=0
for m in range(1000):
  m=str(m).zfill(3)
  j=0
  for i in m:
    if i not in s[j:]:break
    j+=s[j:].index(i)+1
  else:cnt+=1
print(cnt)
### BUGGY CODE ###

def swap(lst, a, b):
    tmp = lst[a]
    lst[a] = lst[b]
    lst[b] = tmp

S = input()
K = int(input())
N = len(S)
substrings = [""] * 10

al = [chr(ord('a') + i) for i in range(26)]
tmp_al = []
if K==1:
    for s in al:
        if s in S:
            print(s)
            exit()

for s in al:
    if s in S:
        if len(tmp_al) == 3:
            break
        if N - S.rfind(s) >= K:
            tmp_al.append(s)
            break
        else:
            if N - S.find(s) >= K:
                tmp_al.append(s)
                break
            else:
                tmp_al.append(s)
                continue

count = [[] for _ in range(len(tmp_al))]
for i in range(len(tmp_al)):
    for k in range(N):
        if S[k] == tmp_al[i]:
            count[i].append(k)
ans_list = []
ans_list.append(tmp_al[0])
for i in count[0]:
    cnt = 1
    while i + cnt <= N:
        ans_list.append(S[i:i+cnt])
        cnt += 1
ans_list = list(set(ans_list))
if len(ans_list) < K:
    for i in count[1]:
        cnt = 1
        while i + cnt <= N:
            ans_list.append(S[i:i+cnt])
            cnt += 1
ans_list = list(set(ans_list))
if len(ans_list) < K:
    for i in count[2]:
        cnt = 1
        while i + cnt <= N:
            ans_list.append(S[i:i+cnt])
            cnt += 1
ans_list = list(set(ans_list))
ans_list.sort()
##print(ans_list)
print(ans_list[K-1])

### FIXED CODE ###

S = input()
K = int(input())
N = len(S)

al = [chr(ord('a') + i) for i in range(26)]
tmp_al = []
if K==1:
    for s in al:
        if s in S:
            print(s)
            exit()

for s in al:
    if s in S:
        if len(tmp_al) == 3:
            break
        if N - S.rfind(s) >= K:
            tmp_al.append(s)
            break
        else:
            if N - S.find(s) >= K:
                tmp_al.append(s)
                break
            else:
                tmp_al.append(s)
                continue

count = [[] for _ in range(len(tmp_al))]
for i in range(len(tmp_al)):
    for k in range(N):
        if S[k] == tmp_al[i]:
            count[i].append(k)
ans_list = []
ans_list.append(tmp_al[0])
for i in count[0]:
    cnt = 1
    while (i + cnt <= N):
        if cnt == 7:
            break
        ans_list.append(S[i:i+cnt])
        cnt += 1

ans_list = list(set(ans_list))

if len(ans_list) < K:
    for i in count[1]:
        cnt = 1
        while (i + cnt <= N):
            if cnt == 7:
                break
            ans_list.append(S[i:i+cnt])
            cnt += 1
ans_list = list(set(ans_list))

if len(ans_list) < K:
    for i in count[2]:
        cnt = 1
        while i + cnt <= N:
            ans_list.append(S[i:i+cnt])
            cnt += 1
ans_list = list(set(ans_list))


ans_list.sort()
##print(ans_list)
print(ans_list[K-1])
### BUGGY CODE ###

import numpy as np
S = input()[::-1]
mod = 1000000007

n = len(S)
a = S[0]
x = np.zeros(26, int)
l = [[13 - i * j % 13 for j in range(0, 10)] for i in [1, 10, 9, 12, 3, 4]] * (n // 6 + 1)
if a == "?":
    x[0:10] += 1
else:
    x[int(a)] += 1
for s, l_ in zip(S[1:], l[1:]):
    x %= mod
    x[13:] = x[:13]
    if s == "?":
        x[:13] = sum([x[v:v+13] for v in l_])
    else:
        v = l_[int(s)]
        x[:13] = x[v:v+13]
print(x[5] % mod)

### FIXED CODE ###

#!python3

LI = lambda: list(map(int, input().split()))

# input
S = input()

MOD = 10 ** 9 + 7


def main():
    n = len(S)
    m = 5
    w = []
    p = 1
    for i in range(n):
        s = S[-1 - i]
        if s == "?":
            w.append(p)
        else:
            m = (m - int(s) * p) % 13
        p = p * 10 % 13

    n = len(w)
    l1 = [0] * 13
    l1[0] = 1
    for i in range(1, n + 1):
        l2 = [0] * 13
        for j in range(10):
            x = w[i - 1] * j % 13
            for k in range(13):
                t = (x + k) % 13
                l2[t] += l1[k]
        l1 = [y % MOD for y in l2]
    
    ans = l1[m]
    print(ans)


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

n = int(input())
a = [0] * n
#dp = []

for i in range(n):
    a[i] = int(input())

maxV = max(a)

for i in range(n):
    if a[i] == maxV:
        new = list(a)
        del new[i]
        print(max(new))
    else:
        print(maxV)


### FIXED CODE ###

n = int(input())
a = [0] * n

for i in range(n):
    a[i] = int(input())

#maxV = max(a)
sortedA = sorted(a)
maxV = sortedA[n-1]
maxV2 = sortedA[n-2]

for i in range(n):
    if a[i] == maxV:
        # new = list(a)
        # del new[i]
        # print(max(new))
        print(maxV2)
    else:
        print(maxV)
### BUGGY CODE ###

def back(x, y, N, M):
    if x == 0 and x == (N - 1) and y == 0 and y == (M - 1):
        return True

    if x == 0 and x == (N - 1) and (y == 0 or y == (M - 1)):
        return False

    if (x == 0 or x == (N - 1)) and y == 0 and y == (M - 1):
        return False

    if x == 0 and x == (N - 1):
        return True

    if y == 0 and y == (M - 1):
        return True

    if x == 0:
        return False

    if x == (N - 1):
        return False

    if y == 0:
        return False

    if y == (M - 1):
        return False

    return True



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

print(len([None for i in range(N) for j in range(M) if back(i, j, N, M)]))


### FIXED CODE ###

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

if N == 1 and M == 1:
    print(1)
elif N == 1:
    print(M - 2)
elif M == 1:
    print(N - 2)
else:
    print(N * M - ((N - 2) * 2 + (M - 2) * 2) - 4)
### BUGGY CODE ###

n, k = map(int,input().split())
p = list(map(int,input().split()))

sums = []
for ind in range(n-k+1):
  sums.append(sum(p[ind:ind+k]))
max_val = float(max(sums))
k = float(k)
print(max_val/2+k/2)

### FIXED CODE ###

n, k = map(int,input().split())
p = list(map(int,input().split()))

exps = [(elm+1)/2 for elm in p]
#print(exps)
cum_sums = [0]*(n+1)
for ind in range(n):
  cum_sums[ind+1] = cum_sums[ind]+exps[ind]
#print(cum_sums)
k_exps = [cum_sums[ind+k]-cum_sums[ind] for ind in range(n-k+1)]
#print(k_exps)
print(max(k_exps))
### BUGGY CODE ###

import copy

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

count = 0

for j in range(N):
    #print(j)
    #print(list)
    #print("j="+str(j))
    list2 = copy.copy(list)
    #print(list2)
    #print(j)
    del list2[j+1:]
    #print(list2)
    list2 = sorted(list2)
    #print(list[j])
    if(list2[0] >= list[j]):
        count +=1

print(count)


### FIXED CODE ###

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

ans = 0
min = list[0]

for j in range(N):
    if (min  >= list[j]):
        ans += 1
        min = list[j]
    else:
        continue

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

from collections import deque
N = int(input())
T = [[]for i in range(N)]
A = []
D = [[0]*N for i in range(N)]
for i in range(N-1):
    a,b = map(lambda x:int(x)-1,input().split())
    T[a].append(b)
    T[b].append(a)
    A.append((a,b))
K = 0
for t in T:
    K = max(K,len(t))
print(K)
Q = deque([(0,-1,0)])
while Q:
    q = Q.popleft()
    v,p,k = q[0],q[1],q[2]
    ck = 1
    for c in T[v]:
        if ck==k:ck+=1
        if c!=p:
            if len(T[c])!=1:
                Q.append((c,v,ck))
            D[c][v] = ck
            D[v][c] = ck
            ck+=1
for a in A:
    print(D[a[0]][a[1]])

### FIXED CODE ###

from collections import deque
N = int(input())
ab = [list(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
T = [[] for i in range(N)]
for a,b in ab:
    T[a].append(b)
q = deque([0])
color = [0]*N
while q:
    x = q.popleft()
    c = 1
    for y in T[x]:
        if c==color[x]:
            c+=1
        color[y] = c
        c+=1
        q.append(y)
print(max(color))
for i in range(N-1):
    print(color[ab[i][1]])
### BUGGY CODE ###

n = int(input())
s = input()
ans = 0

for i in range(1000): #0~999を全探索
  flg1 = False #1桁目があるか
  flg2 = False #2桁目があるか
  flg3 = False #3桁目があるか
  one = str(i//100) #1桁目
  two = str(i%100//10) #2桁目
  three = str(i%10) #3桁目
  t = 0
  
  for j in range(n-2):
    if s[j] == one:
      flg1 = True
      t = j+1
      break
  for j in range(t,n-1):
    if s[j] == two:
      flg2 = True
      t = j+1
      break
  for j in range(t,n):
    if s[j] == three:
      flg3 = True
      t = j+1
      break
  if flg1 and flg2 and flg3:
    ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
s = input()
ans = 0

for i in range(1000): #0~999を全探索
  flg1 = False #1桁目があるか
  flg2 = False #2桁目があるか
  flg3 = False #3桁目があるか
  one = str(i//100) #1桁目
  two = str(i%100//10) #2桁目
  three = str(i%10) #3桁目
  t = 0
  
  for j in range(n-2):
    if s[j] == one:
      flg1 = True
      t = j+1
      break
  for j in range(t,n-1):
    if s[j] == two:
      flg2 = True
      t = j+1
      break
  for j in range(t,n):
    if s[j] == three:
      flg3 = True
      t = j+1
      break
  if flg1 and flg2 and flg3:
    ans += 1
print(ans)
### BUGGY CODE ###

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

INF = 10**10
vsum = 10**5
dp = [INF for i in range(vsum+1)]
dp[0] = 0

for _ in range(N):
    w,v = map(int,input().split())
    dp1 = [d for d in dp]
    for i,d in enumerate(dp):
        if d == INF:
            continue
        else:
            if i + v <= vsum:
                dp1[i+v] = min(dp[i+v], dp[i]+w)
    dp = [d1 for d1 in dp1]

ans = 0
for i,d in enumerate(dp):
    if d <= W:
        ans = i

print(ans)


### FIXED CODE ###

import numpy as np
N,W = map(int, input().split())
INF =  10**10
V_max = 100001
N_max = 101
# dp = np.ones((N_max,V_max), dtype=np.int64)*INF
dp = np.ones(V_max,dtype=np.int64)*INF
dp[0] = 0
for i in range(N):
    a = np.ones(V_max)*INF
    w,v = map(int,input().split())
    # np.minimum(dp[i][:-v]+w,dp[i][v:],out=dp[i+1][v:])
    np.minimum(dp[:-v]+w,dp[v:],out=dp[v:])
ans = 0
for i,d in enumerate(dp):
    if d<=W:
        ans = i
print(ans)
### BUGGY CODE ###

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

S=input()


for i 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()
old=''
count=0
data=[0]*len(S)

for i  in range(len(S)):
    if old =='A' and S[i] =='C':
        count+=1
    data[i]=count
    old=S[i]

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

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

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True) + [0]
B = sorted(list(map(int, input().split())), reverse=True) + [0]
C = sorted(list(map(int, input().split())), reverse=True) + [0]

E = []
for i in range(X):
    for j in range(Y):
        E.append(A[i] + B[j])
E.sort(reverse=True)

F = []
for i in range(min(X * Y, K)):
    for j in range(Z):
        F.append(E[i] + C[j])
F.sort(reverse=True)

for i in range(K):
    print(F[i])


### FIXED CODE ###

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

X, Y, Z, K = map(int, input().split())
A = sorted(list(map(int, input().split())), reverse=True)
B = sorted(list(map(int, input().split())), reverse=True)
C = sorted(list(map(int, input().split())), reverse=True)

Comb = []
for i in range(X):
    for j in range(Y):
        if (i + 1) * (j + 1) > K:
            break
        for k in range(Z):
            if (i + 1) * (j + 1) * (k + 1) > K:
                break
            Comb.append(A[i] + B[j] + C[k])

Comb.sort(reverse=True)
for i in range(K):
    print(Comb[i])
### BUGGY CODE ###

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

ans = n
for i in range(n):
  res = 0
  for j in range(i):
    if s[j] == 'W':
      res += 1
  for k in range(i+1, n):
    if s[k] == 'E':
      res += 1
  ans = min(ans, res)
print(ans)


### FIXED CODE ###

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

ans = [0]*(n+1)
for i in range(n):
  if s[i] == 'E':
    ans[i+1] = ans[i] + 1
  else:
    ans[i+1] = ans[i]
    
print(min(i-ans[i]+ans[n]-ans[i+1] for i in range(n)))
### BUGGY CODE ###

N,M = map(int, input().split())
s = N
c = M
i = 0
if 2*N>=M:
  print(M//2)
else:
  while 2*s<c:
    s = s+1
    c = c-2
  print(c//2)

### FIXED CODE ###

N,M = map(int, input().split())
s = N
c = M
if 2*N>=M:
  print(M//2)
else:
  t = 2*s+c
  print(t//4)
### BUGGY CODE ###

s=input()
for i in range(10**5):
  s=s.replace("ST","")

print(len(s))

### FIXED CODE ###

s=input()

from collections import deque

stack=deque()

for i in s:
  if i=="S":
    stack.append(i)
  if i=="T":
    if len(stack)>0 and stack[-1]=="S":
      stack.pop()
    else:
      stack.append(i)
      
  #print(stack)
print(len(stack))