Harryxun/stf_run huggingface dataset:
n = int(input())
d = {}
for i in range(n):
    a=input()
    if a in d:
        d[a]+=1
    else:
        d[a]=1
m = int(input())
for i in range(n):
    a=input()
    if a in d:
        d[a]-=1
    else:
        d[a]=-1
print(max(d.values()))


### FIXED CODE ###

n = int(input())
d = {}
for i in range(n):
    a=input()
    if a in d:
        d[a]+=1
    else:
        d[a]=1
m = int(input())
for i in range(m):
    a=input()
    if a in d:
        d[a]-=1
    else:
        d[a]=-1
m=max(d.values())
if m<0:
    m=0
print(m)
import math

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

if N == K:
    print(1)
    quit()
else:
    one_index = A.index(1)
    l = one_index #1の左側にある数字の数
    r = N - one_index - 1 #1の右側にある数字の数

    assert r % 3 == 1
    
    print(114514)


### FIXED CODE ###

input_line = input().split()

num_array = int(input_line[0])
num_equal = int(input_line[1])

input_line = input() # 無視

equalized = 1
i = 0
while equalized < num_array:
    equalized += (num_equal - 1)
    # print(i, equalized)
    i += 1

print(str(i))
import math
a = list(map(input().split()))
ans = float(a[1])*int(a[0])
print(math.floor(ans))

### FIXED CODE ###

a,b = input().split()
a = int(a)
b = round(100*float(b))
print(a*b//100)
S,T=map(int,input().split())
A,B=map(int,input().split())
U=input()
if U=S:
  print("{} {}".format(A-1,B))
if U=T:
  print("{} {}".format(A,B-1))
  

### FIXED CODE ###

S,T=map(str,input().split())
A,B=map(int,input().split())
U=str(input())
if U==S:
  print(A-1,B)
else:
  print(A,B-1)
N = int(input())
adj = [[] for _ in range(n)] # 辞書の箱を作る
adj_dict = dict()

for i in range(N - 1):
    a, b = [int(x) - 1 for x in input().split()]
    adj[a].append(b)
    adj[b].append(a)
    if a > b:
        adj_dict[(b, a)] = i
    else:
        adj_dict[(a, b)] = i

m = int(input())
uv = []
for _ in range(m):
    uv.append([int(x) - 1 for x in input().split()])

# 深さ優先探索
def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(adj[v]) == 1:
        return False
    for nv in adj[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False

edgest = [0] * (2 ** m)
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in adj_dict:
            edgest[1 << i] |= (1 << adj_dict[(uu, vv)])

for i in range(1, 2 ** m):
    lsb = i & (-i)
    edgest[i] = edgest[i ^ lsb] | edgest[lsb]

dp = [0] * (2 ** m)
dp[0] = 1 << (N - 1)
ans = dp[0]
for i in range(1, 2 ** m):
    lsb = i & (-i)
    lim = bin(edgest[i] ^ edgest[i ^ lsb]).count('1')
    dp[i] = dp[i ^ lsb] >> lim
    if bin(i).count('1') % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)


### FIXED CODE ###

n = int(input())
adj = [[] for _ in range(n)]
adj_dict = dict()

for i in range(n - 1):
    a, b = [int(x) - 1 for x in input().split()]
    adj[a].append(b)
    adj[b].append(a)
    if a > b:
        adj_dict[(b, a)] = i
    else:
        adj_dict[(a, b)] = i

m = int(input())
uv = []
for _ in range(m):
    uv.append([int(x) - 1 for x in input().split()])

def dfs(p, v, dest):
    if v == dest:
        return [v]
    if p != -1 and len(adj[v]) == 1:
        return False
    for nv in adj[v]:
        if nv == p:
            continue
        ret = dfs(v, nv, dest)
        if ret:
            return ret + [v]
    return False

edgest = [0] * (2 ** m)
for i, (u, v) in enumerate(uv):
    ret = dfs(-1, u, v)
    for uu, vv in zip(ret, ret[1:]):
        if uu > vv:
            uu, vv = vv, uu
        if (uu, vv) in adj_dict:
            edgest[1 << i] |= (1 << adj_dict[(uu, vv)])

for i in range(1, 2 ** m):
    lsb = i & (-i)
    edgest[i] = edgest[i ^ lsb] | edgest[lsb]

dp = [0] * (2 ** m)
dp[0] = 1 << (n - 1)
ans = dp[0]
for i in range(1, 2 ** m):
    lsb = i & (-i)
    lim = bin(edgest[i] ^ edgest[i ^ lsb]).count('1')
    dp[i] = dp[i ^ lsb] >> lim
    if bin(i).count('1') % 2 == 0:
        ans += dp[i]
    else:
        ans -= dp[i]
print(ans)
X = input()
sum = 0

for i in range(len(x)):
  sum += int(x[i])
  
if int(x) % sum == 0
  print("Yes")
else
  print("No")

### FIXED CODE ###

x = input()
sum = 0

for i in range(len(x)):
  sum += int(x[i])
  
if int(x) % sum == 0:
  print("Yes")
else:
  print("No")
a=[]
while True:
    b=input()
    if b=="":
        break
    else:
        a=a+[str(x) for x in b.lower().replace(" ","",10000)]
for i in "abcdefghijklmnopqrstuvwxyz":    
    counter=0
    for j in a:
        if i==j:
            counter+=1
    print(str(i)+" : "+str(counter))

### FIXED CODE ###

import sys
cnts = {}
for line in sys.stdin:
    for c in list(line.lower()): cnts[c] = cnts.get(c,0) + 1
  
for c in range(ord('a'),ord('z')+1): print(chr(c),':',cnts.get(chr(c),0))
A = int(input())
B = int(input())
C = int(input())

A, B, C = map(int, input().split())
if A < C < B:
    print('Yes')
else:
   print('No')

### FIXED CODE ###

A, B, C = map(int, input().split())
if A < C < B:
    print('Yes')
elif B < C < A:
    print('Yes')
else:
   print('No')
#import numpy as np
n,k = map(int, input().split())
a = list(map(int, input().strip().split()))
#a = np.array(a)

for i in range(len(a)):
    a[i] -= 1
#a -= 1
#print(a)
visited = [-1] * (n+1)


now = 0
visited[0] = 0
pre_roop = 0
pos = 0
i = 1
while i < k:
    next = a[now]
    #print('roop:',i,now+1,next+1)
    if visited[next] >= 0:
        r = i-visited[next]
        pre_roop = visited[next]
        pos = next
        #print(i,r,pre_roop,next)
        #print(visited)
        break
    else:
        visited[next] = i
        now = next
        #print(i,visited)
        i += 1
l = (k - pre_roop) % r
#print(l)
i = 0
p = pos
while i < l:
    p = a[p]
    i +=1

print(p+1)



### FIXED CODE ###

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

for i in range(len(a)):
    a[i] -= 1

visited = [-1] * n
now = 0
visited[0] = 0
pre_roop = 0
pos = 0
i = 1
r = 1
while i <= k:
    next = a[now]
    #print('roop:',i,now+1,next+1)
    if visited[next] >= 0:
        r = i-visited[next]
        pre_roop = visited[next]
        pos = next
        #print(i,r,pre_roop,next)
        #print(visited)
        break
    else:
        visited[next] = i
        now = next
        #print(i,visited)
        i += 1

if i > k:
    print(now + 1)
else:
    l = (k - pre_roop) % r
    #print(l)
    i = 0
    p = pos
    while i < l:
        p = a[p]
        i +=1

    print(p+1)
k=0
ind=0
l=[]
i=int(input())
l.append(i)
def guusuu():
    k=l[ind]/2
    return int(k)
    
def kisuu():
    k=l[ind]*3+1
    return int(k)

while ind<500:
    if l[ind]%2==0:
        l.append(guusuu())
    else:
        l.append(kisuu())
    ind+=1       

print((l.index(4))+4)

### FIXED CODE ###

a,b,c =map(int, input().split())
print(int(a*b/2))
i = list(map(int, input().split()))
H=i[0]
W=i[1]
x=H*W 
if H==1 or W==1:
    print(1)
elif x%2==0:
    print(x//2)
else:
    print((x+1)//2)

### FIXED CODE ###

N=int(input())
i=[1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]
print(i[N-1])
def bin_search(array, num):
    if array[0] > num: return 0
    if array[-1] < num: return len(array)
    mx = len(array) - 1
    mn = 0
    while mx >= mn :
        median = mn + (mx - mn)//2 
        target = array[median]
        if target == num:
            return median + 1
        elif target > num:
            mx = median - 1
        else:
            mn = median + 1

    return median + 1

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

mn = -10 ** 18 - 1
mx = 10 ** 18 + 1

while mx >= mn:
    m = mn + (mx - mn)//2

    score = 0
    for a in arr:
        if a > 0:
            thres = m//a
            score += bin_search(arr, thres)
        
        elif a < 0:
            thres = m//a
            score += n - bin_search(arr, thres-1)
        
        else:
            if m >= 0:
                score += n

        if a <= m: score -= 1
    
    assert score % 2 == 0

    score /= 2    
    under = score
    if under < k:
        mn = m
    
    else:
        mx = m

print(m)



### FIXED CODE ###

import numpy as np
import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = np.array([int(a) for a in input().split()], dtype="int64")

A = np.sort(A)

A_pos = A[A > 0]
A_neg = A[A < 0]
A_zero = A[A == 0]

# 積がc以下となる組み合わせの数を求める
def n_comb_lt(c):
    n_comb = 0
    # A[i] > 0であるA[i]について
    target = c // A_pos  # target以下の値がA[i]の相方
    n_comb += np.searchsorted(A, target, side="right").sum()

    # A[i] == 0であるA[i]について
    n_comb += n * len(A_zero) if c >= 0 else 0

    # A[i] < 0であるA[i]について
    target = -(-c // A_neg)
    n_comb += (n - np.searchsorted(A, target, side="left")).sum()

    # 組み合わせのうち、A[i]*A[i]となっているものを引いて、2で割る
    n_comb -= A[A * A <= c].size
    n_comb //= 2

    return n_comb

ok = -10 ** 18 - 1
ng = 10 ** 18 + 1

# k番目の積は、積がm未満となる組み合わせがk個未満となる最大のm
# ←→積が(m-1)以下となる組み合わせがk個未満となる最大のm
while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid - 1) < k:
        ok = mid
    else:
        ng = mid

print(ok)
n, k = map(int, input().split())
s = input()
memo = []
c = 0
ps = ''
lens = len(s) - 1
b = 0
if s[0] == '1':
    b = 1

for i in range(lens + 1):
    if s[i] != ps:
        memo.append(c)
        c = 1
        ps = s[i]
        if i == lens:
            memo.append(1)
        continue
    if i == lens:
        memo.append(c+1)
    c += 1
    ps = s[i]
sum = 0
if  len(memo) < k * 2 + b + 1:
    print(sum(memo))
else:
    sum = sum(memo[: k * 2 + b + 1])
    temp = [sum]
    memo.append(0)
    # print(memo)
    # print(len(memo))
    for i in range(0, len(memo) - 2 * k  - 1, 2):
        sum = sum - memo[i] - memo[i + 1] + memo[i + 2 * k  + 1] + memo[i + 2 * k + 2]
        temp.append(sum)
    # print(temp)
    print(max(temp))


### FIXED CODE ###

n, k = map(int, input().split())
s = input()
memo = []
c = 0
ps = ''
lens = len(s) - 1
b = 0
if s[0] == '1':
    b = 1

for i in range(lens + 1):
    if s[i] != ps:
        memo.append(c)
        c = 1
        ps = s[i]
        if i == lens:
            memo.append(1)
        continue
    if i == lens:
        memo.append(c+1)
    c += 1
    ps = s[i]

if  len(memo) < k * 2 + b + 1:
    print(sum(memo))
else:
    sumi = 0
    sumi = sum(memo[: k * 2 + b + 1])
    temp = [sumi]
    memo.append(0)
    # print(memo)
    # print(len(memo))
    for i in range(b, len(memo) - 2 * k  - 1, 2):
        last = 0
        if i + 2 * k + 2 <= len(memo) - 1:
            last = memo[i + 2 * k + 2]
        sumi = sumi - memo[i] - memo[i + 1] + memo[i + 2 * k  + 1] +last
        temp.append(sumi)
    # print(temp)
    print(max(temp))
import math
N = int(input())
list_N = list(range(1,N+1))
max = -999999999
sqrt_N = []
for i in range(N):
    if max < int(math.sqrt(list_N[i])):
        max = int(math.sqrt(list_N[i]))

print(max*max)

### FIXED CODE ###

import math 
N = int(input())
print(math.floor(math.sqrt(N))**2)
from collections import defaultdict
N = int(input())
XYH = [list(map(int,input().split())) for _ in range(N)]

Cxy = defaultdict(int)

#-1 NG
# 0 default
#1+ ok
for x,y,h in XYH:
    for cx in range(101):
        for cy in range(101):
            val = Cxy[(cx,cy)]
            if val<0:
                continue
            tmp_H = abs(x-cx)+abs(y-cy)+h
            if h==0 and tmp_H<0:
                continue #????

            if val==0:
                Cxy[(cx,cy)] = tmp_H
            elif val != tmp_H:
                Cxy[(cx, cy)] =-1

def find(d):
    for key in d.keys():
        if d[key] >0:
            return key,d[key]
(X,Y),H = find(Cxy)
print(X,Y,H)

### FIXED CODE ###

from collections import defaultdict
N = int(input())
XYH = [list(map(int,input().split())) for _ in range(N)]

Cxy = defaultdict(int)

#-1 NG
# 0 default
#1+ ok
verify =[]
XYH.sort(key=lambda x:-x[2])

for x,y,h in XYH:
    for cx in range(101):
        for cy in range(101):
            val = Cxy[(cx,cy)]
            if val<0:
                continue
            tmp_H = abs(x-cx)+abs(y-cy)+h
            if h==0:
                if tmp_H < Cxy[(cx,cy)]:
                    Cxy[((cx, cy))]=-1
                continue

            if val==0:
                Cxy[(cx,cy)] = tmp_H
            elif val != tmp_H:
                Cxy[(cx, cy)] =-1

def find(d):
    for key in d.keys():
        if d[key] >0:

            return key,d[key]

(X,Y),H = find(Cxy)
print(X,Y,H)
K, N = map(int,input().split())　
A = list(map(int, input().split()))

li = []
for i in range(N - 1):
  li.append(A[i + 1] - A[i]) 

li.append(abs(A[0] + (K - A[-1])))
print(sum(li) - max(li))

### FIXED CODE ###

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

    li = []
    for i in range(N - 1):
        li.append(A[i + 1] - A[i]) 

    li.append(abs(A[0] + (K - A[-1])))
    print(sum(li) - max(li))
except:
    pass
import sys
N=int(input())
A=list(map(int,input().split()))
total=0
for i in range(N):
  total+=A[i]
if total*2/((N+1)*N)%1!=0:
  print("NO")
  sys.exit()
times=int(total*2/((N+1)*N))
if (times-A[0]+A[N-1])/N%1! or times-A[0]+A[N-1]<0=0:
  print("NO")
  sys.exit()
B=(times-A[0]+A[N-1])/N
for i in range(N-1):
  B+=(times-A[i+1]+A[i])/N
  if (times-A[i+1]+A[i])/N%1!=0 or times-A[i+1]+A[i]<0:
    print("NO")
    sys.exit()
if B==times:
  print("YES")
else:
  print("NO")

### FIXED CODE ###

import sys
N=int(input())
A=list(map(int,input().split()))
total=0
for i in range(N):
  total+=A[i]
if total*2/((N+1)*N)%1!=0:
  print("NO")
  sys.exit()
times=int(total*2/((N+1)*N))
if (times-A[0]+A[N-1])/N%1!=0 or times-A[0]+A[N-1]<0:
  print("NO")
  sys.exit()
B=(times-A[0]+A[N-1])/N
for i in range(N-1):
  B+=(times-A[i+1]+A[i])/N
  if (times-A[i+1]+A[i])/N%1!=0 or times-A[i+1]+A[i]<0:
    print("NO")
    sys.exit()
if B==times:
  print("YES")
else:
  print("NO")
#ABC048.B
a,b,x = map(int,input().split())

print(b//x - (a-1)//x)

### FIXED CODE ###

#ABC048.A
A,B,C= input().split()
print(A[0]+B[0]+C[0])
M = 1000000007


def main(N=None, K=None):
    if not N or not K:
        N = int(input())
        K = int(input())
    ans = 0
    gcds = {}
    for X in range(K, 0, -1):
        gcds[X] = int(pow(K//X, N, M))
        n = 1
        while True:
            n += 1
            if n*X > K:
                break
            gcds[X] -= gcds[n*X]
        ans += gcds[X]*X
    ans %= M
    print(ans)
    return ans


if __name__ == "__main__":
    # assert main(3, 2) == 9
    # assert main(3, 200) == 10813692
    # assert main(100000, 100000) == 742202979
    main()


### FIXED CODE ###

M = 1000000007


def main(N=None, K=None):
    if not N or not K:
        N, K = map(int, input().split())
    ans = 0
    gcds = {}
    for X in range(K, 0, -1):
        gcds[X] = int(pow(K//X, N, M))
        n = 1
        while True:
            n += 1
            if n*X > K:
                break
            gcds[X] -= gcds[n*X]
        ans += gcds[X]*X
    ans %= M
    print(ans)
    return ans


if __name__ == "__main__":
    # assert main(3, 2) == 9
    # assert main(3, 200) == 10813692
    # assert main(100000, 100000) == 742202979
    main()
a, b = int(input())
print('Even' if a*b % 2 == 0 else 'Odd')

### FIXED CODE ###

a, b = map(int,input().split())
print('Even' if a*b % 2 == 0 else 'Odd')
h, w = map(int,input().split())
arr = [["."] * (w + 2)]
for i in range(h):
    arr += [["."] + list(input()) + ["."]]
arr += [["."] * (w + 2)]

flg = 0    

for j in range(1, h+1):
    for k in range(1, w+!):
        if arr[j][k] == "#":
            if (arr[j-1][k] == '.') and (arr[j][k-1] == '.') and (arr[j+1][k] == '.') and (arr[j][k+1] == '.'):
                flg = 1    
        
if flg == 0:
    print('Yes')
else:
    print('No')
        


### FIXED CODE ###

h, w = map(int,input().split())
arr = [["."] * (w + 2)]
for i in range(h):
    arr += [["."] + list(input()) + ["."]]
arr += [["."] * (w + 2)]

flg = 0    

for j in range(1, h+1):
    for k in range(1, w+1):
        if arr[j][k] == "#":
            if (arr[j-1][k] == '.') and (arr[j][k-1] == '.') and (arr[j+1][k] == '.') and (arr[j][k+1] == '.'):
                flg = 1    
        
if flg == 0:
    print('Yes')
else:
    print('No')
nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()
As = nl()

from math import gcd      #3.5
gcds_left = [0] * N
gcds_right = [0] * N
gcds_left[0] = As[0]
gcds_right[N-1] = As[N-1]

for i in range(1, N):
    gcds_left[i] = gcd(As[i], gcds_left[i-1])
    gcds_right[N-1-i] = gcd(As[N-1-i], gcds_right[N-i])

max_gcd = -1
for i in range(1, N-1):
    g = gcd(gcds_left[i-1], gcds_right[i+1])
    if g > max_gcd:
        max_gcd = g
print(max(max_gcd, gcds_left[1], gcds_right[N-2]))


### FIXED CODE ###

nl = lambda: list(map(int, input().split()))
sl = lambda: input().split()
n = lambda: int(input())
s = lambda: input()

N = n()
As = nl()

from fractions import gcd
gcds_left = [0] * N
gcds_right = [0] * N
gcds_left[0] = As[0]
gcds_right[N-1] = As[N-1]

for i in range(1, N):
    gcds_left[i] = gcd(As[i], gcds_left[i-1])
    gcds_right[N-1-i] = gcd(As[N-1-i], gcds_right[N-i])

max_gcd = -1
for i in range(1, N-1):
    g = gcd(gcds_left[i-1], gcds_right[i+1])
    if g > max_gcd:
        max_gcd = g
print(max(max_gcd, gcds_right[1], gcds_left[N-2]))
a, b = map(int, input().split())
result = a*500
if result >= b:
    print("yes")
else: 
    print("no")

### FIXED CODE ###

K, X = map(int, input().split())
result = K*500
if result >= X:
    print("Yes")
else:
    print("No")
A = input()
B = input()

if A > B:
    print("Alice")
if A == B:
    print("Draw")
if A < B:
    print("Bob")

### FIXED CODE ###

l = input().split()

A = int(l[0])
B = int(l[1])

if A == 1:
    A = 14
if B == 1:
    B = 14
    
if A > B:
    print("Alice")
if A == B:
    print("Draw")
if A < B:
    print("Bob")
n=int(input())
s=input()
l=[0]*n
for i in range(n):
  if s[i]==I:
    l[i]+=1
  else:
    l[i]-=1
print(max(l))
    

### FIXED CODE ###

n=int(input())
s=input()
i=0
m=i
for c in s:
	if c == 'I':
		i+=1
	else:
		i-=1
	m=max(m,i)
print(m)
a,b,k = map(int,input().split())
tmp = list(range(a,b+1))
ans = tmp[:k] + tmp[-k:]
for i in sorted(set(ans)):
	print(i)

### FIXED CODE ###

a,b,k=map(int,input().split())
if a+k-1>=b-k+1:
    for i in range(a,b+1):
        print(i)
else:
    for i in range(a,a+k):
        print(i)
    for i in range(b-k+1,b+1):
        print(i)
# -*- coding utf-8 -*-
hash = {'SUN':7, 'MON':6, 'TUE':5, 'WED':4, 'THU':3, 'FRI':2,'STA':1}
s = input()
print(hash[s])


### FIXED CODE ###

# -*- coding utf-8 -*-
hash = {'SUN':7, 'MON':6, 'TUE':5, 'WED':4, 'THU':3, 'FRI':2,'SAT':1}
s = input()
print(hash[s])
sanmoji=[]
for i in range(3):
    sanmoji[i] = input()[i]
print(sanmoji)

### FIXED CODE ###

sanmoji=[0]*3
for i in range(3):
    sanmoji[i] = input()[i]

moji=""
for i in range(3):
    moji += sanmoji[i]
print(moji)
x,y=map(int,input().split())
l=[0,300000,200000,100000]
if x==y==1:
 print(l[x]+l[y]+400000)
elif y>3:
    print(l[x])
elif x>3:
    print(l[y])
else:
    print(l[x]+l[y])

### FIXED CODE ###

x,y=map(int,input().split())
l=[0,300000,200000,100000]
if x==y==1:
 print(l[x]+l[y]+400000)
else:
    if y > 3:
        y=0
    if x>3:
        x=0
    print(l[x]+l[y])
import math

pages = input()
count = int(pages)

if count %2 = 0 :
    print(count/2)
else :
    print((count + 1)/2)


### FIXED CODE ###

import math

pages = input()
count = int(pages)

if count %2 == 0 :
    print(count/2)
else :
    print((count + 1)/2)
N=int(input())
a=input().split()
alice=0
bob=0

a2=sorted(a,reverse=true)

alice=sum(a2[1::2])
bob=sum(a2[0::2])
print(alice-bob)

### FIXED CODE ###

N=int(input())
a = list(map(int, input().split()))
a.sort(reverse=True)
S=0
for i in range(N):
  if i%2==0:
    S+=a[i]
  else:
    S-=a[i]
print(S)
N, K = map(int, input().split())
S = list(input())
l = len(S)
X = []
cnt0 = 0
cnt1 = 0
for i in S:
    if i == '0':
        if cnt1 != 0:
            X.append(cnt1)
            cnt1 = 0
            cnt0 += 1
        else:
            cnt0 += 1
    else:
        if cnt0 != 0:
            X.append(cnt0)
            cnt0 = 0
            cnt1 += 1
        else:
            cnt1 += 1
if cnt1 != 0:
    X.append(cnt1)
elif cnt0 != 0:
    X.append(cnt0)
ans = []
if S[0] == '1': #Xの奇数は1
    sum0 = sum(X[0:2*K+1])
    ans.append(sum0)
    i = 0
    if 2*K+1 >= len(X):
        ans = sum(X)
    else:
        while 2*K+i+1 < len(X):
            ans.append(ans[i] + X[2*K+i+1] - X[i])
            i += 1
else:
    sum0 = sum(X[0:2*K])
    ans.append(sum0)
    i = 0
    while 2*K+i < len(X):
        ans.append(ans[i] + X[2*K+i] - X[i])
        i += 1
print(max(ans))

### FIXED CODE ###

N, K = map(int, input().split())
S = list(input())
X = []
cnt = 1
for i in range(1, N):
    if S[i] != S[i-1]:
        X.append(cnt)
        cnt = 0
    cnt += 1
    if i == N-1:
        X.append(cnt)
l = len(X)

if S[0] == '0' and (l+1)//2 <= K:
    print(N)
    exit()
if S[0] ==  '1' and l//2 <= K:
    print(N)
    exit()

ans = 0
result = 0
if S[0] == '0':
    for j in range(2*K):
        result += X[j]
    ans = result
    for j in range(2*K, l):
        if j == 2*K:
            result -= X[0]
        elif j%2 == 0:
            result = result - X[j-2*K] - X[j-2*K-1]
        result += X[j]
        ans = max(ans,result)
else:
    for j in range(2*K+1):
        result += X[j]
    ans = result
    for j in range(2*K+1, l):
        if j%2 == 1:
            result = result - X[j-2*K-1] - X[j -2*K]
        result += X[j]
        ans = max(ans, result)
print(ans)
while True:
    x = int(input())
    if x == 0:
        break
    dcl = dict()
    for i in range(x):
        inp = list(map(str, input().split()))
        dcl[inp[0]] = inp[1]
    ans = ""
    x = int(input())
    y = str(input())
    for i in range(x):
        y = str(input())
        if y in dcl:
            ans += dcl[y]
        else:
            ans += y
    print(ans)

### FIXED CODE ###

while True:
    n = int(input())
    if n == 0:
        break
    converter = {}
    for _ in range(n):
        k, v = input().split()
        converter[k] = v

    m = int(input())
    ans = []
    for _ in range(m):
        v = input().strip()
        try:
            ans.append(converter[v])
        except:
            ans.append(v)

    print("".join(ans))
from itertools import accumulate
N, M = map(int, input().split())
A = list(map(int, input().split()))

B = [0] + A
C = {}
B = list(accumulate(B))
for i in range(1, N+1):
    if B[i]%M not in C:
        C[B[i]%M] = 1
    else:
        C[B[i]%M] += 1
ans = 0
for i in C.values():
    ans += i*(i-1)//2
ans += C[0]
print(ans)

### FIXED CODE ###

from itertools import accumulate
N, M = map(int, input().split())
A = list(map(int, input().split()))

B = [0] + A
C = {}
B = list(accumulate(B))
for i in range(1, len(B)):
    if B[i]%M not in C:
        C[B[i]%M] = 1
    else:
        C[B[i]%M] += 1
ans = 0
for i in C.values():
    ans += i*(i-1)//2
if 0 in C:
    ans += C[0]
print(ans)
n=int(input())
h=list(map(int,input().split()))
print(count(max(h[:i])<=h[i]for i in range(n)))

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
print(sum(max(h[:i]+[0])<=h[i]for i in range(n)))
# coding: utf-8
# Your code here!
n,k = map(int,input().split())

s = input()

now = s[0]
tmp = 0

h = []
if s[0]=="0":
    h.append(0)

for i in s:
    if i != now:
        now = i
        h.append(tmp)
        tmp=0
    tmp+=1
h.append(tmp)

ans = 0

for i in range(0,max(len(h),len(h)-k),2):
    ans = max(ans,sum(h[i:i+k*2+1]))

print(ans)


### FIXED CODE ###

# coding: utf-8
# Your code here!

a,b = map(int,input().split())

ans = 0

if a>b:
    ans+=a
    a-=1

else:
    ans+=b
    b-=1


if a>b:
    ans+=a

else:
    ans+=b

print(ans)
a = input()
b = a.replace("ST","")
if a[0] =="S" and b[-1] =="T":
    print(0)
while "ST" in b:
    b = b.replace("ST","")
print(len(b))

### FIXED CODE ###

a = input()
s,t = 0,0
for i in a:
    if i == "S":
        s += 1
    else:
        if s==0:
            t += 1
        else:
            s -=1
print(s+t)