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

N,Q=map(int,input().split())
S=str(input().strip())
lr=[]
for i in range(Q):
    l,r=map(int,input().split())
    lr.append([l,r])

for i in lr:
    print(S[i[0]-1:i[1]].count("AC"))

### FIXED CODE ###

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

cnt=0
cntlist=[0]
for i in range(N-1):
    if S[i:i+2]=='AC':
        cnt+=1
    cntlist.append(cnt)
for i in range(Q):
    l,r=map(int,input().split())
    print(cntlist[r-1]-cntlist[l-1])
### BUGGY CODE ###

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]
ab.sort(key=lambda x: (x[0], x[1]))
px.sort(key=lambda x: (x[0], x[1]))
ans = [0] * n

for i in px:
  ans[i[0] - 1] += i[1]

for i in ab:
  ans[i[1] - 1] += ans[i[0] - 1]
  
print(*ans)

### FIXED CODE ###

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]
ab.sort(key=lambda x: x[0])
ans = [0] * n

for i in px:
  ans[i[0] - 1] += i[1]

for i in ab:
  ans[i[1] - 1] += ans[i[0] - 1]
  
print(*ans)
### BUGGY CODE ###

import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    dp[0][0] = 1

    for i,s in enumerate(s[::-1],start = 1):
        p10 = pow(10,i-1,13)
        if s!= "?":
            for k in range(13):
                dp[i][(int(s)*p10 + k)%13] += dp[i-1][k]
                dp[i][(int(s)*p10 + k)%13] %= MOD
        else:
            for j in range(10):
                for k in range(13):
                    dp[i][(j*p10 + k)%13] += dp[i-1][k]
                    dp[i][(j*p10 + k)%13] %= MOD
    print(dp[n][5] % MOD)



if __name__=="__main__":
    main()


### FIXED CODE ###

import math
from math import gcd,pi,sqrt
INF = float("inf")
MOD = 10**9 + 7

import sys
sys.setrecursionlimit(10**6)
import itertools
from collections import Counter,deque
def i_input(): return int(input())
def i_map(): return map(int, input().split())
def i_list(): return list(i_map())
def i_row(N): return [i_input() for _ in range(N)]
def i_row_list(N): return [i_list() for _ in range(N)]
def s_input(): return input()
def s_map(): return input().split()
def s_list(): return list(s_map())
def s_row(N): return [s_input for _ in range(N)]
def s_row_str(N): return [s_list() for _ in range(N)]
def s_row_list(N): return [list(s_input()) for _ in range(N)]

def main():
    s = input()
    n = len(s)
    dp = [[0]*13 for i in range(n+1)]
    dp[0][0] = 1

    for i,s in enumerate(s[::-1],start = 1):
        p10 = pow(10,i-1,13)
        if s!= "?":
            for k in range(13):
                dp[i][(int(s)*p10 + k)%13] += dp[i-1][k]
                dp[i][(int(s)*p10 + k)%13] %= MOD
        else:
            for j in range(10):
                for k in range(13):
                    dp[i][(j*p10 + k)%13] += dp[i-1][k]
                    dp[i][(j*p10 + k)%13] %= MOD
    print(dp[n][5] % MOD)


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

class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    def print(self):
        for order in ['Inorder', 'Preorder']:
            print('', *[node.key for node in self.root.walk(order)])
    
class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    def walk(self, order):
        orders = {'Preorder':[self, self.left, self.right], 'Inorder':[self.left, self, self.right], 'Postorder':[self.left, self.right, self]}
        
        for node in orders[order]:
            if node == self:
                yield node
            elif node:
                for childnode in node.walk(order):
                    yield childnode

                    
                    
tree = Tree()
func = {'insert':tree.insert, 'print':tree.print}

n = int(input())
for _ in range(n):
    command = input().split()
    func[command[0]](*map(int, command[1:]))

### FIXED CODE ###

import sys
class Tree():
    def __init__(self):
        self.root = None
    def insert(self, key):
        z = Node(key)
        y = None
        x = self.root
        while x:
            y = x
            if z.key < x.key:
                x = x.left
            else:
                x = x.right
        z.parent = y
        if y == None:
            self.root = z
        elif z.key < y.key:
            y.left = z
        else:
            y.right = z
    def print(self):
        print('',' '.join(map(str, self.root.inwalk())))
        print('',' '.join(map(str, self.root.prewalk())))
    
class Node():
    def __init__(self, key):
        self.key = key
        self.parent = self.left = self.right = None
    def prewalk(self):
        ret = [self.key]
        if self.left:
            ret += self.left.prewalk()
        if self.right:
            ret += self.right.prewalk()
        return ret
    def inwalk(self):
        ret = []
        if self.left:
            ret += self.left.inwalk()
        ret += [self.key]
        if self.right:
            ret += self.right.inwalk()
        return ret
tree = Tree()
n = sys.stdin.readline()
for line in sys.stdin:
    if line[0] == 'i':
        tree.insert(int(line.split()[1]))
    else:
        tree.print()
### BUGGY CODE ###

from queue import Queue


def main():
    H, W = map(int, input().split())

    l = 0
    q = Queue()
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.put((h, w))
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append((h-1, w))
            if h != H-1:
                Next[h][w].append((h+1, w))
            if w != 0:
                Next[h][w].append((h, w-1))
            if w != W-1:
                Next[h][w].append((h, w+1))

    c = -1
    while True:
        nl = 0
        if q.empty():
            break
        for _ in range(l):
            (h, w) = q.get()
            for nh, nw in Next[h][w]:
                if not checked[nh][nw]:
                    q.put((nh, nw))
                    checked[nh][nw] = True
                    nl += 1
        l = nl
        c += 1
    print(c)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

B = int(1E8)

def main():

    H, W = map(int, input().split())
    
    l = 0
    q = []
    checked = []
    for h in range(H):
        S = input()
        L = []
        for w in range(W):
            if S[w] == '#':
                l += 1
                L.append(True)
                q.append(B*h+w)
            else:
                L.append(False)
        checked.append(L)

    Next = [[[] for _ in range(W)] for _ in range(H)]
    for h in range(H):
        for w in range(W):
            if h != 0:
                Next[h][w].append(B*(h-1) + w)
            if h != H-1:
                Next[h][w].append(B*(h+1) + w)
            if w != 0:
                Next[h][w].append(B*h + w-1)
            if w != W-1:
                Next[h][w].append(B*h + w+1)

    c = -1
    for _ in range(H+W+2):
        qq = []
        if len(q) == 0:
            break
        for hw in q:
            h, w = hw//B, hw%B
            for nhw in Next[h][w]:
                nh, nw = nhw//B, nhw%B
                if not checked[nh][nw]:
                    qq.append(B*nh + nw)
                    checked[nh][nw] = True
        q = qq
        c += 1

    print(c)


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

# 解説みたよ
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
l, r, d = [0] * m, [0] * m, [0] * m
for i in range(m):
    l[i], r[i], d[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1
    es[l[i]].append((r[i], d[i]))
    es[r[i]].append((l[i], -d[i]))
INF = 1000000000000
value = [INF] * n


def dfs(v):
    for i, di in es[v]:
        if value[i] == INF:
            value[i] = value[v] + di
            dfs(i)


for i in range(n):
    if value[i] == INF:
        value[i] = 0
        dfs(i)

for i, j, k in zip(l, r, d):
    if value[j] - value[i] != k:
        print("No")
        exit()
print("Yes")


### FIXED CODE ###

# 解説みたよ
import sys
sys.setrecursionlimit(10000000)
input = sys.stdin.readline
n, m = map(int, input().split())
es = [[] for i in range(n)]
l, r, d = [0] * m, [0] * m, [0] * m
for i in range(m):
    l[i], r[i], d[i] = map(int, input().split())
    l[i] -= 1
    r[i] -= 1
    es[l[i]].append((r[i], d[i]))
    es[r[i]].append((l[i], -d[i]))
INF = 1000000000000
value = [INF] * n


def dfs(v):
    for i, di in es[v]:
        if value[i] == INF:
            value[i] = value[v] + di
            dfs(i)


for i in range(n):
    if value[i] == INF:
        value[i] = 0
        dfs(i)

for i, j, k in zip(l, r, d):
    if value[j] - value[i] != k:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

n = int(input())
word = [input() for _ in range(n)]
count = 0

for i in range(n):
    word[i] = sorted(word[i])

for i in range(n-1):
    for j in range(i+1,n):
        if word[i] == word[j]:
            count += 1

print(count)


### FIXED CODE ###

import itertools,math
n = int(input())
word = [input() for _ in range(n)]
count = 0

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(n):
    word[i] = sorted(word[i])

new_word = list(sorted(word))

x = 1

for i in range(n-1):
    if new_word[i] == new_word[i+1]:
        x += 1
    elif x >= 2:
        count += combinations_count(x,2)
        x = 1
if x >= 2:
    count +=  combinations_count(x,2)

print(count)
### BUGGY CODE ###

import math

def cost_compare(v,w,L,K,Z):
    if w in L:
        return min(K[v]+Z,K[w])
    elif w in K:
        return K[w]
    else:
        return K[v]+Z

T=int(input())


f=True
for t in range(T):
    N,A,B,C,D=map(int,input().split())

    K={0:0} #最小のコストの辞書
    L={0:0} #Kのうち未確定のものへの制限

    g=0
    while g<=10:
        v=min(L.items(),key=lambda x:x[1])[0]

        del L[v]
        
        m=cost_compare(v,2*v,L,K,A)
        if (2*v in L) or (2*v not in K):
            L[2*v]=m
        K[2*v]=m

        m=cost_compare(v,3*v,L,K,B)
        if (3*v in L) or (3*v not in K):
            L[3*v]=m
        K[3*v]=m

        m=cost_compare(v,5*v,L,K,C)
        if (5*v in L) or (5*v not in K):
            L[5*v]=m
        K[5*v]=m

        m=cost_compare(v,v+1,L,K,D)
        if (v+1 in L) or (v+1 not in K):
            L[v+1]=m
        K[v+1]=m

        if v>=1:
            m=cost_compare(v,v-1,L,K,D)
            if (v-1 in L) or (v-1 not in K):
                L[v-1]=m
            K[v-1]=m

        if v==N:g=1
        if g!=0:
            g+=1
        
    print(K[N])


### FIXED CODE ###

T=int(input())
for i in range(T):
    N,A,B,C,D=map(int,input().split())

    M={0:0,1:D}

    def f(N):
        if N in M:
            return M[N]
        
        p,q=N//2*2,(N+1)//2*2
        r,s=N//3*3,(N+2)//3*3
        t,u=N//5*5,(N+4)//5*5
        R=min(D*N,
              D*abs(N-p)+A+f(p//2),
              D*abs(N-q)+A+f(q//2),
              
              D*abs(N-r)+B+f(r//3),
              D*abs(N-s)+B+f(s//3),
              
              D*abs(N-t)+C+f(t//5),
              D*abs(N-u)+C+f(u//5),
              )

        M[N]=R
        return R
    
    print(f(N))
### BUGGY CODE ###

a,b,c,k = map(int,input().split())
ans = 0
for i in range(a):
  if k == 0:
    print(ans)
    exit()
  ans += 1
  k -= 1
for i in range(b):
  if k == 0:
    print(ans)
    exit()
  k -= 1
for i in range(c):
  if k == 0:
    print(ans)
    exit()
  ans -= 1
  k -= 1

### FIXED CODE ###

a,b,c,k = map(int,input().split())
ans = 0
if k <= a:
    print(k)
elif k <= a+b:
    print(a)
else:
    print(a-(k-a-b))
### BUGGY CODE ###

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

for i in range(min(21, k)):
    DP = [0] * (n+1)
    for j in range(n):
        light = A[j]
        DP[max(0, j-light)] += 1
        DP[min(n, j+light+1)] -= 1

    for j in range(1, n):
        DP[j] += DP[j-1]

    A = DP[:-1]

print(*A)

### FIXED CODE ###

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

for i in range(min(50, k)):
    DP = [0] * (n+1)
    for j in range(n):
        light = A[j]
        DP[max(0, j-light)] += 1
        DP[min(n, j+light+1)] -= 1

    for j in range(1, n):
        DP[j] += DP[j-1]

    A = DP[:-1]

print(*A)
### BUGGY CODE ###

n, k = map(int, input().split())
mod = 10 ** 9 + 7
graph = {i + 1:set() for i in range(n)}
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a] |= set([b])
    graph[b] |= set([a])
com = 1
check_list = [1]
count = {i + 1:0 for i in range(n)}
while check_list:
    check = check_list.pop(0)
    next_check = list(graph[check])
    for i in range(len(next_check)):
        count[next_check[i]] += i
        check_list.append(next_check[i])
        graph[next_check[i]] -= set([check])
    if check == 1:
        com *= k
    elif check in graph[1]:
        com *= k - 1 - count[check]
        com %= mod
    else:
        com *= k - 2 - count[check]
        com %= mod
print(com)

### FIXED CODE ###

import collections

n, k = map(int, input().split())
mod = 10 ** 9 + 7
graph = [[] for i in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
flag = [False for i in range(n + 1)]
flag[1] = True
queue = collections.deque([1])
ans = k
while queue:
    test = queue.popleft()
    temp = [flag[graph[test][i]] for i in range(len(graph[test]))].count(True)
    num = 0
    for i in range(len(graph[test])):
        if flag[graph[test][i]] == True:
            continue
        ans *= (k - temp - num - 1)
        ans %= mod
        num += 1
        queue.append(graph[test][i])
        flag[graph[test][i]] = True
print(ans)
### BUGGY CODE ###

def main():
  S=input()
  N=int(input())
  for i in range(N):
    tmp=[i for i in input().split() ]
    if tmp[0]=='1':
      S=S[::-1]
    else:
      if tmp[1]=='1':
        new=tmp[2]+S
        S=new
      else:
        new=S+tmp[2]
        S=new
  print(S)
if __name__=='__main__':
  main()
   


### FIXED CODE ###

def main():
  S=input()
  N=int(input())
  cnt=0
  f=''
  b=''
  for i in range(N):
    tmp=[i for i in input().split() ]
    if tmp[0]=='1':
      cnt+=1
    else:
      if (cnt+int(tmp[1]))%2==1:
        f=tmp[2]+f
        
      else:
        b=b+tmp[2]
  ans=f+S+b        
  if cnt%2!=0:
    ans=''.join(list(reversed(ans)))

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

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

ans = 0
for a in set(A):
    if a == A.count(a): continue
    elif a < A.count(a): ans += A.count(a)-a
    elif a > A.count(a): ans += A.count(a)
print(ans)

### FIXED CODE ###

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

ans = 0
cnt = 1

if n ==1:
    if a[0] == 1: 
        print(0)
        exit()
    else:
        print(1)
        exit()
 

for i in range(n-1):
    if a[i] == a[i+1]:cnt+=1
    else:
        if cnt < a[i]: ans += cnt
        elif cnt > a[i]: ans += cnt-a[i]
        cnt = 1
    if i+1 == n-1:
        if cnt < a[i]: ans += cnt
        elif cnt > a[i]: ans += cnt-a[i]
print(ans)
### BUGGY CODE ###

while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break
    y = 0
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            if i == j:
                continue
            for k in range(1, n + 1):
                if j == k or k == i:
                    continue
                elif i + j + k == x:
                    y += 1
    print(y // 6)
    

### FIXED CODE ###

while True:
    n, x = map(int, input().split())
    if n == x == 0:
        break
    y = 0
    for i in range(1, n - 1):
        for j in range(i + 1, n):
            for k in range(j + 1, n + 1):
                if i + j + k == x:
                    y += 1
    print(y)
### BUGGY CODE ###

N, Q = list(map(int, input().split()))
S = input()
li = [list(map(int, input().split())) for i in range(Q)]

for num in range(Q):
    st = S[li[num][0] - 1:li[num][1]]
    count = 0
    for i in range(len(st)-1):
        if st[i] == "A":
            if st[i+1] == "C":
                count += 1
    print(count)

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t = [0] * (N + 1)
for i in range(N):
	t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])
### BUGGY CODE ###

#!/usr/bin/env python3
import sys, math


def solve(N: int, K: int, A: "List[int]", F: "List[int]"):
    A = sorted(A)
    F = sorted(F, reverse=True)
    B = [a*f for a, f in zip(A, F)]
    b = max(B)
    left = -1
    right = b

    def ok(mid):
        r = 0
        for i in range(N):
            a, f = A[i], F[i]
            r += max(0, a - mid//f)
        if r > K:
            return True
        else:
            return False

    while right - left > 1:
        mid = (right + left) // 2
        if ok(mid):
            left = mid
        else:
            right = mid
    print(right)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    F = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A, F)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys, math


def solve(N: int, K: int, A: "List[int]", F: "List[int]"):
    A = sorted(A)
    F = sorted(F, reverse=True)
    B = [a*f for a, f in zip(A, F)]
    b = max(B)
    left = -1
    right = b

    def ok(mid):
        r = 0
        for i in range(N):
            a, f = A[i], F[i]
            r += max(0, a - mid//f)
        if r > K:
            return True
        else:
            return False

    while right - left > 1:
        mid = (right + left) // 2
        if ok(mid):
            left = mid
        else:
            right = mid
    print(right)
    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    F = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A, F)

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

def warshall_floyd(graph):
    num_v = len(graph)

    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph

N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
import copy
a_list = copy.deepcopy(graph)
from scipy.sparse.csgraph import floyd_warshall
w_graph = floyd_warshall(graph, directed=False)
result = 0
for i in range(N):
     w_graph[i][i] = float("inf")
for i in range(N):
    for j in range(i):
        if i == j:
            continue
        if w_graph[i][j] != a_list[i][j]:
            print(-1)
            exit()
        d = []
        for k in range(N):
            d.append(w_graph[i][k] + w_graph[j][k])
        if min(d) > w_graph[i][j]:
            result += w_graph[i][j]
print(int(result))


### FIXED CODE ###

def warshall_floyd(graph):
    num_v = len(graph)

    for k in range(num_v):
        for i in range(num_v):
            for j in range(num_v):
                if graph[i][j] > graph[i][k] + graph[k][j]:
                    graph[i][j] = graph[i][k] + graph[k][j]
    return graph

N = int(input())
graph = [[float("inf") for _ in range(N)] for _ in range(N)]
for i in range(N):
    a_list = list(map(int, input().split()))
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = a_list[j]
import copy
a_list = copy.deepcopy(graph)
w_graph = warshall_floyd(graph)
result = 0
for i in range(N):
    for j in range(i+1, N):
        if i == j:
            continue
        if w_graph[i][j] != a_list[i][j]:
            print(-1)
            exit()
        d = []
        for k in range(N):
            d.append(w_graph[i][k] + w_graph[j][k])
        if min(d) > w_graph[i][j]:
            result += w_graph[i][j]
print(result)
### BUGGY CODE ###

N = int(input())
Ss = input()

def getZArray(Ss):
    lenS = len(Ss)
    As = [lenS] * lenS
    i, j = 1, 0
    while i < lenS:
        while i+j < lenS and Ss[j] == Ss[i+j]:
            j += 1
        As[i] = j
        if j == 0:
            i += 1
        else:
            k = 1
            while i+k < lenS and k+As[k] < j:
                As[i+k] = As[k]
                k += 1
            i += k
            j -= k
    return As

ans = 0
for i in range(N):
    ZArray = getZArray(Ss[i:])
    for i, Z in enumerate(ZArray):
        L = min(Z, i)
        ans = max(ans, L)

print(ans)


### FIXED CODE ###

N = int(input())
Ss = input()

def isOK(k):
    strAs = ['' for _ in range(N)]
    strBs = ['' for _ in range(N)]
    for L in range(N-k+1):
        R = L+k-1
        ss = Ss[L:R+1]
        strAs[R] = ss
        strBs[L] = ss

    strCands = set()
    for iEn in range(N-1):
        if strAs[iEn] != '':
            strCands.add(strAs[iEn])
        if strBs[iEn+1] != '' and strBs[iEn+1] in strCands:
            return True

    return False


ng, ok = N//2 + 1, 0
while abs(ok-ng) > 1:
    mid = (ng+ok) // 2
    if isOK(mid):
        ok = mid
    else:
        ng = mid

print(ok)