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

def main():
    S = input()
    T = input()
    N = len(S)
    M = len(T)

    dp = [[[] for _ in range(M+1)] for _ in range(N+1)]
    for i in range(N):
        for j in range(M):
            if S[i] == T[j]:
                dp[i+1][j+1] = dp[i][j] + [S[i]]
            else:
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], key=len)
    print("".join(dp[N][M]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    X = input()
    Y = input()
    N = len(X)
    M = len(Y)
    dp = [[0]*(M+1) for _ in range(N+1)]
    for i, x in enumerate(X):
        for j, y in enumerate(Y):
            if x == y:
                dp[i+1][j+1] = dp[i][j] + 1
            else:
                dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j])
    res = ""
    while N > 0 and M > 0:
        if dp[N][M] == dp[N-1][M]:
            N -= 1
        elif dp[N][M] == dp[N][M-1]:
            M -= 1
        else:
            res = X[N-1] + res
            N -= 1
            M -= 1
    print(res)


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

n = int(input())
a = [int(input()) for i in range(n)]
for j in range(n):
	b = a[:]
	b[j] = 0
	print(max(b))

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m1 = max(a)
c = a.count(m1)
if len(set(a)) == 1:
	for i in range(n):
		print(m1)
else:
	m2 = sorted(set(a))[-2]
	for i in range(n):
		if a[i] < m1:
			print(m1)
		elif a[i] == m1:
			if c > 1:
				print(m1)
			else:
				print(m2)
		else:
			print(m2)
### BUGGY CODE ###

n = int(input())
A = [int(input()) for _ in range(n)]

def isort(n, g):
    global A
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j -= g
            cnt += 1
        A[j + g] = v

def ssort(n):
    global cnt
    global A
    cnt = 0
    m = max(min(int(n / 3), 100), 1)
    G = [m * 3 - 3 * (i + 1) + 1 for i in range(m - 1)]
    G.append(1)
    print(m)
    print(" ".join([str(g) for g in G]))
    for g in G:
        isort(n, g)

ssort(n)
print(cnt)
print("\n".join([str(a) for a in A]))

### FIXED CODE ###

import sys

def isort(A, n, g):
    cnt = 0
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j -= g
            cnt += 1
        A[j + g] = v
    return cnt

def ssort(A, n):
    cnt = 0
    G = []
    h = 1
    while h <= n:
        G.append(h)
        h = 3 * h + 1
    m = len(G)
    G.reverse()
    print(m)
    print(*G, sep = " ")
    for g in G:
        cnt += isort(A, n, g)
    return cnt

n = int(input())
A = list(map(int, sys.stdin.readlines()))
cnt = ssort(A, n)
print(cnt)
print(*A, sep = "\n")
### BUGGY CODE ###

N,K = (int(x) for x in input().split())
A = [int(x) for x in input().split()]

#print(N)
#print(K)
#print(A)

preX = -1
nowX = 1

for i in range(K,N+1):
#  print(str(i)+'学期')
  if i == K:
    for x in range(K):
      nowX *= A[x]
  else:
    nowX = int(preX / A[i-K-1] * A[i-1])
#    print(str(preX) +', '+ str(nowX))
    if preX < nowX:
      print('Yes')
    else:
      print('No')
  preX = nowX
  

### FIXED CODE ###

N,K = (int(x) for x in input().split())
A = [int(x) for x in input().split()]

#print(N)
#print(K)
#print(A)

preX = 0
nowX = 1

for i in range(K+1,N+1):
#  print(str(i)+'学期')
#  if i == K:
#    for x in range(K):
#      nowX *= A[x]
#  else:
#    nowX = int(preX / A[i-K-1]) * A[i-1]
#    print(str(preX) +', '+ str(nowX))
#    if preX < nowX:
#      print('Yes')
#    else:
#      print('No')
#  preX = nowX

  if A[i-K-1] < A[i-1]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

from collections import Counter
n = int(input())
ls = []
for _ in range(n):
    ls.append(input())
res = []
counter = Counter(ls).most_common(1)
for x in set(ls):
    if ls.count(x) == counter[0][1]:
        res.append(x)
r = sorted(res)
print("\n".join(r))

### FIXED CODE ###

from collections import Counter
n = int(input())
ls = []
for _ in range(n):
    ls.append(input())
res = []
counter = Counter(ls).most_common()
for x in counter:
    if x[1] == counter[0][1]:
        res.append(x[0])
print("\n".join(sorted(res)))
### BUGGY CODE ###

s = input().rstrip()
t = input().rstrip()
len_s = len(s)
len_t = len(t)

# Get longest LCS num
dp = [[0] * (len_t+1) for _ in range(len_s+1)]
for i in range(1, len_s+1):
    for j in range(1, len_t+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

# Restore LCS
h, w = len_s, len_t
ans = ""
while dp[h][w] != 0:
    while dp[h][w] == dp[h-1][w]:
        h -= 1
    while dp[h][w] == dp[h][w-1]:
        w -= 1
    h -= 1
    w -= 1
    ans += t[w]

print(ans[::-1])

### FIXED CODE ###

s = input().rstrip()
t = input().rstrip()
len_s = len(s)
len_t = len(t)

# Get longest LCS num
dp = [[0] * (len_t+1) for _ in range(len_s+1)]
for i in range(1, len_s+1):
    for j in range(1, len_t+1):
        if s[i-1] == t[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i][j-1], dp[i-1][j])

# Restore LCS
h, w = len_s, len_t
ans = ""
while dp[h][w] != 0:
    while dp[h][w] == dp[h-1][w]:
        h -= 1
    while dp[h][w] == dp[h][w-1]:
        w -= 1
    h -= 1
    w -= 1
    ans += t[w]

print(ans[::-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000) 

def resolve():
    (N, M) = list(map(int, input().split(" ")))
    As = [int(input()) for i in range(M)]
    # mems = [False] * (N+1)

    cnts = [False] * (N+1)
    for i in range(N+1):
        c = 0
        if i in As:
            c = 0
        elif i == 0:
            c = 1
        elif i == 1:
            c = 1
        elif i == 2:
            c = 2 if 1 not in As else 1
        else:
            c = cnts[i-2] + cnts[i-1]
        cnts[i] = c
        # print("cnt[{}] = {}".format(str(i), str(c)))

    print(cnts[N]%1000000007)
    # for i in range(N-1):
    #     if i in As and i+1 in As:
    #         return 0 

    # def rec(target):
    #     if target in As:
    #         return 0
        
    #     if target == 1:
    #         return 1
        
    #     if target == 2:
    #         return 2 if 1 not in As else 1

    #     if not mems[target]:
    #         one = rec(target-1)
    #         two = rec(target-2)
    #         mems[target] = one + two
        
    #     return mems[target]
    # print(rec(N)%1000000007)

if '__main__' == __name__:
    resolve()

### FIXED CODE ###

def resolve():
    (N, M) = list(map(int, input().split(" ")))
    As = [int(input()) for i in range(M)]
    As.sort()

    cnts = [False] * (N+1)
    ptr = 0
    for i in range(N+1):
        c = 0
        if ptr < len(As) and i == As[ptr]:
            c = 0
            ptr = ptr + 1
        elif i == 0:
            c = 1
        elif i == 1:
            c = 1
        elif i == 2:
            c = 2 if 1 not in As else 1
        else:
            c = (cnts[i-2] + cnts[i-1])%1000000007
        cnts[i] = c

    print(cnts[N])

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

S = input()


table = {}
pairs = [[((i*10 + j)%13, i) for i in range(13)] for j in range(13)]
mod = 10**9 + 7
for i in range(13):
    table[i] = tuple((i + j*13)//10 for j in range(10))

dp =[[0 for i in range(13)] for i in range(len(S))]

if S[0] == "?":
    for i in range(10):
        dp[0][i] = 1
else:
    s = int(S[0])
    dp[0][s] = 1

for i in range(1, len(S)):
    s = S[i]
    if s == "?":
        for j in range(13):
            for k in table[j]:
                dp[i][j] += dp[i-1][k] % mod
    else:
        s = int(s)
        for pair in pairs[s]:
            dp[i][pair[0]] = dp[i-1][pair[1]] % mod

print(dp[len(S)-1][5] % mod)


### FIXED CODE ###

S = input()


table = {}
pairs = [[((i*10 + j)%13, i) for i in range(13)] for j in range(13)]
mod = 10**9 + 7
for i in range(13):
    table[i] = tuple((i + j*13)//10 for j in range(10))

dp =[[0 for i in range(13)] for i in range(len(S))]

if S[0] == "?":
    for i in range(10):
        dp[0][i] = 1
else:
    s = int(S[0])
    dp[0][s] = 1

for i in range(1, len(S)):
    s = S[i]
    if s == "?":
        for j in range(13):
            for k in table[j]:
                dp[i][j] += dp[i-1][k]
            dp[i][j] %= mod
    else:
        s = int(s)
        for pair in pairs[s]:
            dp[i][pair[0]] = dp[i-1][pair[1]] % mod

print(dp[len(S)-1][5] % mod)
### BUGGY CODE ###

n,q = map(int,input().split())
s = list(input())
def ac(s,l,r):
    cnt = 0
    for i in range(r-l):
        if s[l-1+i] == "A" and s[l+i] == "C":
            cnt+= 1
    return cnt

for j in range(q):
    l,r = map(int,input().split())
    print(ac(s,l,r))


### FIXED CODE ###

n,q = map(int,input().split())
s = input()
cnt = [0]*(n+1)
p = s[0]
for i in range(1,n+1):
    if p == "A" and s[i-1] == "C":
            cnt[i] = cnt[i-1] +1
    else:
        cnt[i] = cnt[i-1]
    p = s[i-1]

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

from heapq import heappush, heappop
from collections import deque
N, M = map(int, input().split())
S, T = map(int, input().split())
S -= 1; T -= 1
G = [[] for i in range(N)]
for i in range(M):
    u, v, d = map(int, input().split())
    G[u-1].append((v-1, d))
    G[v-1].append((u-1, d))

INF = 10**18
MOD = 10**9 + 7

dist = [INF]*N
dist[S] = 0
que = [(0, S)]
while que:
    cost, v = heappop(que)
    if dist[v] < cost:
        continue
    for w, c in G[v]:
        if cost + c < dist[w]:
            dist[w] = cost + c
            heappush(que, (cost + c, w))

que = deque()
mi = [0]*N
que.append(T)
mi[T] = 1
H = [[] for i in range(N)]
RH = [[] for i in range(N)]

D = dist[T]

V = []
E = []
while que:
    v = que.popleft()
    d = dist[v]
    if d*2 == D:
        V.append(v)
    for w, c in G[v]:
        if d == dist[w] + c:
            if dist[w]*2 < D < d*2:
                E.append((w, v))
            H[v].append(w)
            RH[w].append(v)
            if mi[w] == 0:
                mi[w] = 1
                que.append(w)

def bfs(G, RG, s):
    *deg, = map(len, RG)
    que = deque([s])
    res = [0]*N
    res[s] = 1
    while que:
        v = que.popleft()
        for w in G[v]:
            deg[w] -= 1
            res[w] += res[v]
            if deg[w] == 0:
                que.append(w)
                res[w] %= MOD
    return res
CT = bfs(H, RH, T)
CS = bfs(RH, H, S)

ans = CS[T] * CT[S] % MOD
for v in V:
    ans -= (CS[v] * CT[v]) ** 2
    ans %= MOD
for v, w in E:
    ans -= (CS[v] * CT[w]) ** 2
    ans %= MOD
print(ans)

### FIXED CODE ###

from heapq import heappush, heappop
from collections import deque
N, M = map(int, input().split())
S, T = map(int, input().split())
S -= 1; T -= 1
G = [[] for i in range(N)]
for i in range(M):
    u, v, d = map(int, input().split())
    G[u-1].append((v-1, d))
    G[v-1].append((u-1, d))

INF = 10**18
MOD = 10**9 + 7

dist = [INF]*N
dist[S] = 0
que = [(0, S)]
while que:
    cost, v = heappop(que)
    if dist[v] < cost:
        continue
    for w, c in G[v]:
        if cost + c < dist[w]:
            dist[w] = cost + c
            heappush(que, (cost + c, w))

que = deque()
mi = [0]*N
que.append(T)
mi[T] = 1
H = [[] for i in range(N)]
RH = [[] for i in range(N)]

D = dist[T]

V = []
E = []
while que:
    v = que.popleft()
    d = dist[v]
    if d*2 == D:
        V.append(v)
    for w, c in G[v]:
        if d == dist[w] + c:
            if dist[w]*2 < D < d*2:
                E.append((w, v))
            H[v].append(w)
            RH[w].append(v)
            if mi[w] == 0:
                mi[w] = 1
                que.append(w)

def bfs(G, RG, s):
    *deg, = map(len, RG)
    que = deque([s])
    res = [0]*N
    res[s] = 1
    while que:
        v = que.popleft()
        for w in G[v]:
            deg[w] -= 1
            res[w] += res[v]
            if deg[w] == 0:
                que.append(w)
                res[w] %= MOD
    return res
CT = bfs(H, RH, T)
CS = bfs(RH, H, S)

ans = CS[T] * CT[S] % MOD
for v in V:
    ans -= (CS[v] * CT[v]) ** 2
    ans %= MOD
for v, w in E:
    ans -= (CS[v] * CT[w]) ** 2
    ans %= MOD
print(ans)
### BUGGY CODE ###

import sys
from itertools import combinations
from collections import Counter

N, X, Y = map(int, sys.stdin.readline().rstrip().split())

nodes = list(range(1, N + 1))
distance_counter = Counter()
a = Y - X - 1
p = (Y - X) // 2 + X
ans = []
for i, j in combinations(nodes, 2):
    if j - i == 1:
        distance = 1
        distance_counter[distance] += 1
        continue
    if i <= X:
        if j < Y:
            jtoX = min(Y - j + 1, j - X)
            distance = X - i + jtoX
        else:
            distance = j - i - a
    else:
        if j < Y:
            d1 = j - i
            d2 = i - X + Y - j + 1
            distance = min(d1, d2)
        else:
            itoY = min(i - X + 1, Y - i)
            distance = j - Y + itoY
    distance_counter[distance] += 1

for k in range(1, N):
    if k == 1:
        ans.append(N)
    else:
        ans.append(distance_counter.get(k, 0))

print('\n'.join(map(str, ans)))


### FIXED CODE ###

import sys

N, X, Y = map(int, sys.stdin.readline().rstrip().split())

nodes = list(range(1, N + 1))
ans = [0] * N
for i in range(1, N):
    for j in range(i + 2, N + 1):
        distance = min(abs(X - i) + abs(Y - j) + 1, j - i)
        ans[distance] += 1

for k in range(1, N):
    if k == 1:
        print(N)
    else:
        print(ans[k])
### BUGGY CODE ###

import fractions
import sys
input = sys.stdin.readline


P = 10**9 + 7
N = (10**6)+1
inv_t = [0]+[1]
for i in range(2, N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]
N = int(input())
A = tuple(map(int, input().split()))

mod = 10**9+7
lcm = 1
B = [0]*N

for i in range(N):
    lcm = (lcm // fractions.gcd(lcm, A[i])) * A[i]

ans = 0

for i in range(N):
    ans += (lcm * inv_t[A[i]]) % mod
    ans %= mod

print(ans)


### FIXED CODE ###

import fractions
import sys
input = sys.stdin.readline


P = 10**9 + 7
N = (10**6)+1
inv_t = [0]+[1]
for i in range(2, N):
    inv_t += [inv_t[P % i] * (P - int(P / i)) % P]

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

mod = 10**9+7
lcm = 1
B = [0]*N

for i in range(N):
    lcm = (lcm // fractions.gcd(lcm, A[i])) * A[i]

ans = 0

lcm %= mod
for i in range(N):
    ans += (lcm * inv_t[A[i]]) % mod
    ans %= mod

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

N = int(input())
A = list(map(int, input().split()))
T = 1
for i in A:
    T *= i
if T > 10 ** 18:
    print(-1)
else:
    print(T)

### FIXED CODE ###

def t():
    N = int(input())
    A = list(map(int, input().split()))
    T = 1
    if 0 in A:
        return 0
    for i in A:
        T *= i
        if T > 10 ** 18:
            return -1
    return T
print(t())
### BUGGY CODE ###

N,X=map(int,input().split())
inputcities=list(map(int, input().split()))
cities=[abs(inputcities[i]-X) for i in range(N)]
count=0
flag=0
minimum=min(cities)
for j in range(minimum+1)[::-1]:
  for i in range(N):
    if sum(cities)%j==0:
      if cities[i]%j==0:
        count+=1
      else:
        count=0
        break
      if count==N:
        print(j)
        flag=1
        break
    else:
      break
  if flag==1:
    break

### FIXED CODE ###

def gcd(a,b):
    if a < b:
        a,b = b,a
    if a % b == 0:
        return b
    else:
        return gcd(b,(a % b))
 
N,X=map(int,input().split())
inputcities=list(map(int, input().split()))
cities=[abs(inputcities[i]-X) for i in range(N)]
cities.sort()
D=cities[0]
for i in range(N):
  D=gcd(D,cities[i])
print(D)
### BUGGY CODE ###

# coding: utf-8
# Your code here!
R, G, B, N = map(int, input().split())
answer = 0
for x in range(N // R + 1):
	for y in range(N // G + 1):
		if (N - R * x - G * y) % B == 0 & 0 <= (N - R * x - G * y) // B <= N // B:
			answer += 1
print(answer)

### FIXED CODE ###

# coding: utf-8
# Your code here!
R, G, B, N = list(map(int, input().split()))

answer = 0
for r in range(N//R + 1):
    for g in range((N - r*R)//G + 1):
        if (N-r*R-g*G) % B == 0:
            answer += 1

print(answer)
### BUGGY CODE ###

n,m,s=map(int,input().split())
s=min(s,2500)
edge=[[] for i in range(n*50*51)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2501):
        edge[u-1+j*n].append((v-1+(j-a)*n,b))
        edge[v-1+j*n].append((u-1+(j-a)*n,b))
for i in range(n):
    c,d=map(int,input().split())
    for j in range(2501-c):
        edge[i+j*n].append((i+(j+c)*n,d))
    for j in range(2500):
        edge[i+(j+1)*n].append((i+j*n,0))
from heapq import heappush,heappop,heapify
d = [float('inf') for i in range(n*50*51)]
pq = []
heappush(pq,(0,s*n))
while pq:
    weight,u = heappop(pq)
    if d[u]>weight:
        d[u]=weight
        for v,weight in edge[u]:
            heappush(pq,(d[u]+weight,v))
for i in range(1,n):
    print(d[i])

### FIXED CODE ###

n,m,s=map(int,input().split())
s=min(s,2500)
edge=[[] for i in range(n*50*51)]
for i in range(m):
    u,v,a,b=map(int,input().split())
    for j in range(a,2501):
        edge[u-1+j*n].append((v-1+(j-a)*n,b))
        edge[v-1+j*n].append((u-1+(j-a)*n,b))
for i in range(n):
    c,d=map(int,input().split())
    for j in range(2501-c):
        edge[i+j*n].append((i+(j+c)*n,d))
    for j in range(2500):
        edge[i+(j+1)*n].append((i+j*n,0))
from heapq import heappush,heappop,heapify
d = [float('inf') for i in range(n*50*51)]
pq = []
heappush(pq,(0,s*n))
while pq:
    weight,u = heappop(pq)
    if d[u]>weight:
        d[u]=weight
        for v,weight in edge[u]:
            heappush(pq,(d[u]+weight,v))
for i in range(1,n):
    print(d[i])
### BUGGY CODE ###

s = (input()[::-1]) # 入力文字列を逆順でsに格納
n = len(s)
counts = [0]*2019
counts[0]=1
b = 1
num = 0
for i in s:
    num += int(i)*b
    num %=2019
    b *=10
    b %2019
    counts[num]+=1

# print(counts)
ans = 0
for j in counts:
    ans +=j*(j-1)/2


print(int(ans))

### FIXED CODE ###

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

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

num, d = 0, 1

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

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

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

def main():
    k,q = map(int, input().split())
    D=list(map(int, input().split()))
    for _ in range(q):
        n,x,m=map(int, input().split())
        mods=[d%m for d in D]
        S=sum(mods)*((n-1)//k)+x%m
        S+=sum(mods[:(n-1)%k])
        through=S//m
        ans=n-through-1
        c = mods[:(n-1)%k].count(0)
        ans-=(c+mods[(n-1)%k:].count(0))*((n-1)//k)+c
        print(ans)
main()

### FIXED CODE ###

import sys
import numpy as np
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

k,q=map(int,readline().split())
D=np.array(readline().split(),dtype=np.int64)
NXM = map(int, read().split())

NXM=iter(NXM)
NXM=zip(NXM,NXM,NXM)

for n,x,m in NXM:
    tmpD=D%m
    SD=np.hstack((np.zeros(1,dtype=np.int64), tmpD))#結合
    SD=np.cumsum(SD)
    n-=1
    x=x%m
    x+=SD[-1]*(n//k)
    x+=SD[n%k]
    count=(k-np.count_nonzero(tmpD))*(n//k)
    count+=n%k-np.count_nonzero(tmpD[:n%k])
    ans=n-x//m-count
    print(ans)
### BUGGY CODE ###

#C - Sum of gcd of Tuples (Easy)
K = int(input())
sum = 0

import fractions
def N_gcd(ans):
    ans2 = ans[0]
    for n in range(1, 3):
        ans2 = fractions.gcd(ans2, ans[n])
    return ans2

for i in range(1,K+1):
    for j in range(1,K+1):
            for k in range(1,K+1):
                a = [i,j,k]
                sum += N_gcd(a)


print(sum)

### FIXED CODE ###

#C - Sum of gcd of Tuples (Easy)
K = int(input())
DP =[]
ans = 0
import math
# from functools import reduce
# def gcd(*numbers):
#     return reduce(math.gcd, numbers)


# def gcd_list(numbers):
#     return reduce(math.gcd, numbers)

for i in range(1, K + 1):
    for j in range(1, K + 1):
        a = math.gcd(i,j)
        for k in range(1,K+1):
            b = math.gcd(a,k)
            ans += b

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

n,_,*a=map(int,open(0).read().split())
c,d=1,0
for i in range(n):n=(c+d)%(10**9+7)*(not-~i in set(a));c,d=n,c
print(n)

### FIXED CODE ###

n,_,*a=map(int,open(0).read().split())
a=set(a)
c,d=1,0
for i in range(n):n=(c+d)%(10**9+7)*(not-~i in a);c,d=n,c
print(n)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
#ABC122C
import sys
import copy
tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))
n=hoge[0]
q=hoge[1]

s = input()

l=[]
r=[]
sum=0
for i in range(0,q):
	tmp = input().split()
	hoge = list(map(lambda a: int(a), tmp))
	for j in range(hoge[0]-1,hoge[1]-1):
		#print(j)
		#print(hoge[0]-1)
		#print(hoge[1])
		if(s[j]=="A")and(s[j+1]=="C"):
			sum+=1
	print(sum)
	sum=0

### FIXED CODE ###

# -*- coding: utf-8 -*-
#ABC122C
import sys
import copy
tmp = input().split()
hoge = list(map(lambda a: int(a), tmp))
n=hoge[0]
q=hoge[1]

s = input()

ans=[]
sum=0
#print(s)

for j in range(0,n-1):
	if(s[j]=="A")and(s[j+1]=="C"):
		sum+=1
	ans.append(sum)
	#print(s[j])
ans.append(sum)
ans.append(0)
#ans[n-1]=sum
#print(ans)
#print(ans)

l=[]
r=[]
sum=0
for i in range(0,q):
	tmp = input().split()
	hoge = list(map(lambda a: int(a), tmp))

	print(ans[hoge[1]-2]-ans[hoge[0]-2])
### BUGGY CODE ###

n, m = map(int, input().split())
h_array = list(map(int, input().split()))
ab = []
sum = 0

for i in range(m):
  ab.append(list(map(int, input().split())))

for i in range(1, n + 1):
  result = True
  for j in range(len(ab)):
    if ab[j][1] == i:
      if h_array[ab[j][0]- 1] >= h_array[i - 1]:
        result = False

    elif ab[j][0] == i:
      if h_array[ab[j][1]- 1] >= h_array[i - 1]:
        result = False  
  
  if result:
    sum += 1

print(sum)

### FIXED CODE ###

n, m = map(int, input().split())
h_array = list(map(int, input().split()))
ab = []
sum = 0
answer = [True for i in range(n)]

for i in range(m):
  ab.append(list(map(int, input().split())))

for i in range(len(ab)):
  if h_array[ab[i][0]- 1] >= h_array[ab[i][1]- 1]:
    answer[ab[i][1] - 1] = False
  if h_array[ab[i][1]- 1] >= h_array[ab[i][0]- 1]:
      answer[ab[i][0] - 1] = False

print(answer.count(True))
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()
F = LIST()

A.sort(reverse=True)
F.sort()

time = [A[i]*F[i] for i in range(N)]
# print(F)
# print(time)

def is_ok(x):  # 時間をx以下にできるか？
	tmp = 0
	for i in range(N):
		if time[i] <= x:
			pass
		else:
			tmp += ceil((time[i]-x)/F[i])
	if tmp > K:
		return False
	else:
		return True

min_ = -1
max_ = 10**18
while min_ + 1 != max_:
	search = (min_+max_)//2
	# print(min_, max_, search)
	if is_ok(search):
		max_ = search
	else:
		min_ = search

print(max_)


### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, atan, degrees
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
from bisect import bisect
import heapq

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, K = MAP()
A = LIST()
F = LIST()

A.sort(reverse=True)
F.sort()

time = [A[i]*F[i] for i in range(N)]
# print(F)
# print(time)

def is_ok(x):  # 時間をx以下にできるか？
	tmp = 0
	for i in range(N):
		if time[i] <= x:
			pass
		else:
			tmp += ceil((time[i]-x)/F[i])
	if tmp > K:
		return False
	else:
		return True

min_ = -1
max_ = 10**18
while min_ + 1 != max_:
	search = (min_+max_)//2
	# print(min_, max_, search)
	if is_ok(search):
		max_ = search
	else:
		min_ = search

print(max_)