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

import sys
input=sys.stdin.readline
def knapsack(N,W,weight,value):
  inf=float("inf")
  dp=[[-inf for i in range(W+1)] for j in range(N+1)]
  dp2=[[[] for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0

  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
          dp2[i+1][w]=dp2[i][w-weight[i]]+[i]
        else:
          dp[i+1][w]=dp[i][w]
          dp2[i+1][w]=dp2[i][w]
        
      else:
        dp[i+1][w]=dp[i][w]
        dp2[i+1][w]=dp2[i][w]
  return [dp[N][W],dp2[N][W]]

n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
z=knapsack(n,t-1,a,b)
x=z[0];y=z[1]
L=[0 for i in range(n)]
for i in range(len(y)):
  L[y[i]]=1
M=[]
for i in range(n):
  if L[i]==0:
    M.append(b[i])
if len(M)==0:
  print(x)
else:
  print(x+max(M))

### FIXED CODE ###

import sys
input=sys.stdin.readline
import copy
def knapsack(N,W,weight,value):
  dp=[[999999999999 for i in range(W+1)] for j in range(N+1)]
  for i in range(W+1): dp[0][i]=0
 
  for i in range(N):
    for w in range(W+1):
      if weight[i]<=w:
        if dp[i][w-weight[i]]+value[i]>dp[i][w]:
          dp[i+1][w]=dp[i][w-weight[i]]+value[i]
        else:
          dp[i+1][w]=dp[i][w]
      else:
        dp[i+1][w]=dp[i][w]
  return dp
 
n,t=map(int,input().split())
l=[list(map(int,input().split())) for i in range(n)]
l.sort()
a=[];b=[]
for i in range(n):
  a.append(l[i][0])
  b.append(l[i][1])
dp=knapsack(n,t-1,a,b)
ans=[]
for i in range(n):
  if i!=n:
    ans.append(dp[i][t-1]+b[i])
  else:
    ans.append(dp[n][t-i])
print(max(ans))
### BUGGY CODE ###

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
left = [[0 for i in range(W)] for j in range(H)]
right = [[0 for i in range(W)] for j in range(H)]
down = [[0 for i in range(W)] for j in range(H)]
up = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
    cnt = 0
    for j in range(W):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
        left[i][j] = cnt

for i in range(H):
    cnt = 0
    for j in range(W)[::-1]:
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
        right[i][j] = cnt

for j in range(W):
    cnt = 0
    for i in range(H):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
        down[i][j] = cnt
    
for j in range(W):
    cnt = 0
    for i in range(H)[::-1]:
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
        up[i][j] = cnt

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        ans = max(ans, left[i][j] + right[i][j] + down[i][j] + up[i][j] -3)

print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
S = []
for _ in range(H):
    S.append(input())
left = [[0 for i in range(W)] for j in range(H)]
right = [[0 for i in range(W)] for j in range(H)]
down = [[0 for i in range(W)] for j in range(H)]
up = [[0 for i in range(W)] for j in range(H)]

for i in range(H):
    cnt = 0
    for j in range(W):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
        left[i][j] = cnt

for i in range(H):
    cnt = 0
    for j in range(W)[::-1]:
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
        right[i][j] = cnt

for j in range(W):
    cnt = 0
    for i in range(H):
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
        down[i][j] = cnt
    
for j in range(W):
    cnt = 0
    for i in range(H)[::-1]:
        if S[i][j] == '#':
            cnt = 0
        else:
            cnt += 1
        up[i][j] = cnt

ans = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        ans = max(ans, left[i][j] + right[i][j] + down[i][j] + up[i][j] -3)

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

n,m=map(int,input().split())
a=[int(input()) for i in range(m)]
F = [1,1]
for i in range(1,n):
    F.append((F[i]%(10**9+7)+F[i-1]%(10**9+7))%(10**9+7))


if n==1:
    print(1)
elif n==2:
    if m==1:
        print(1)
    elif m==0:
        print(2)
else:
    for i in range(m):
        if a[i]+1 in a or a[i]-1 in a:
            print(0)
            exit()
    if m==0:
        print(F[n])
    else:
        x=F[min(a)-1]
        a.append(n+1)
        for i in range(1,len(a)):
            x=(x*F[a[i]-a[i-1]-2])%(10**9+7)
        print(x)


### FIXED CODE ###

n,m=map(int,input().split())
a=set(int(input()) for _ in range(m))
dp=[0]*(n+1)
dp[0]=1
for i in range(1,n+1):
    dp[i]=(dp[i-1]+dp[i-2])%(10**9+7)
    if i in a:
        dp[i]=0
print(dp[n])
### BUGGY CODE ###

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

exsit = []

ans = "YES"
for i in a:
  if i in exsit:
    ans = "NO"
    break
  else:
    exsit.append( i )

print( ans )

### FIXED CODE ###

n = int( input() )
a = set( map( int, input().split() ) )

if n == len(a):
  ans = "YES"
else:
  ans = "NO"

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

S = input()
if len(S) < 4:
    print(0)
    exit(0)
dp = [0]*2019
dp[0] = 1
s = int(S[-1])
dp[s] = 1
ans = 0
for k in range(len(S)-2,-1,-1):
    s = int(S[k])*(10**(len(S)-k-1)) + s
    s %= 2019
    if dp[s] > 0:
        ans += 1
    else:
        dp[s] = 1
print(ans)


### FIXED CODE ###

S = input()
if len(S) < 4:
    print(0)
    exit(0)
dp = [0]*2019
dp[0] = 1
s = int(S[-1])
dp[s] = 1
ans = 0
for k in range(len(S)-2,-1,-1):
    s = int(S[k])*(pow(10,len(S)-k-1,2019)) + s
    s %= 2019
    dp[s] += 1
for e in dp:
    ans += e*(e-1)//2
print(ans)
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    s = input()

    TF = 2, 5
    if p in TF:
        answer = 0
        for i, char in enumerate(s):
            if int(char) % p == 0:
                answer += i + 1
        print(answer)
        return

    # u = [int(s[i:]) for i in range(n)]
    u = []
    t = 0
    for i, char in enumerate(s[::-1]):
        t += 10 ** i * int(char)
        u.append(t)
    u = u[::-1]
    u.append(0)
    # The numbers to consider are int(s[i:j]) (0 <= i < j <= n)
    # u[i] := int(s[i:]) (u[n] = 0 for convenience)
    # int(s[i:j]) and u[i] - u[j] are congruent (unless p == 2 or 5)
    remainders = [number % p for number in u]
    d = {}
    for remainder in remainders:
        if remainder not in d:
            d[remainder] = 1
        else:
            d[remainder] += 1
    answer = 0
    for count in d.values():
        if count > 1:
            answer += count * (count - 1) // 2
    print(answer)

main()


### FIXED CODE ###

def main():
    n, p = map(int, input().split())
    s = input()

    TF = 2, 5
    if p in TF:
        answer = 0
        for i, char in enumerate(s):
            if int(char) % p == 0:
                answer += i + 1
        print(answer)
        return

    # u = [int(s[i:]) for i in range(n)]
    remainders = []
    t = 0
    for i, char in enumerate(s[::-1]):
        t += pow(10, i, p) * int(char)
        remainders.append(t % p)
    remainders = remainders[::-1]
    remainders.append(0)
    # The numbers to consider are int(s[i:j]) (0 <= i < j <= n)
    # u[i] := int(s[i:]) (u[n] = 0 for convenience)
    # int(s[i:j]) and u[i] - u[j] are congruent (unless p == 2 or 5)
    d = {}
    for remainder in remainders:
        if remainder not in d:
            d[remainder] = 1
        else:
            d[remainder] += 1
    answer = 0
    for count in d.values():
        if count > 1:
            answer += count * (count - 1) // 2
    print(answer)

main()
### BUGGY CODE ###

import math

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

m = 0

for x in range(1,n+1):
    y = math.floor(a*x/b) - a * math.floor(x/b)
    if m < y:
        m = y

print(m)

### FIXED CODE ###

import math

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

m = 0
x = n

while x >= n-b:
    if m > (a*x) // b:
        break
    else:
        y =  math.floor((a * (x / b - math.floor(x / b))))
        if m < y:
            m = y
            x = b * math.floor(x / b) - 1
        else:
            x-=1  

print(m)
### BUGGY CODE ###

n = int(input())
l_list = list(int(i) for i in input().split())
list.sort(l_list, reverse=True)
count = 0
for i in range(n):
    a = l_list[i]
    for j in range(i+1, n):
        b = l_list[j]
        for k in range(j+1, n):
            c = l_list[k]
            if a < b + c and b < c + a and c < a + b:
                count += 1
            else:
                break
print(count)

### FIXED CODE ###

import bisect

n = int(input())
l = list(int(i) for i in input().split())
list.sort(l)
count = 0

for i in range(n):
    a = l[i]
    for j in range(i+1, n):
        b = l[j]
        ab = a + b
        index_c = bisect.bisect_left(l, ab)
        count += index_c - j -1

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

# -*- coding: utf-8 -*-
import sys

def main():
	N, M = map(int, input().split(" "))
	
	bridge = []
	for _ in range(M):
		a, b = map(int, input().split(" "))
		bridge.append((a, b))
		
	bridge.reverse()
	uf = UnionFind(N)
	ans = []
	fuben = 0
	for i in range(N):
		for j in range(N):
			if i < j:
				if False == uf.is_same(i, j):
					fuben += 1
	ans.append(fuben)
	
	for i, val in enumerate(bridge):
		a, b = val
		a, b = a-1, b-1
		uf.union(a, b)
		fuben = 0
		for i in range(N):
			for j in range(N):
				if i < j:
					if False == uf.is_same(i, j):
						fuben += 1
		ans.append(fuben)
		
	ans.pop()
	ans.reverse()
	for val in ans:
		print(val)
	

class UnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		
	# x が属するグループを探索
	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]
		
	# x と y のグループを結合
	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			if self.rank[x] < self.rank[y]:
				x, y = y, x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
			self.par[y] = x
	
	# x と y が同じグループがどうか
	def is_same(self, x, y):
		return self.find(x) == self.find(y)
		

if __name__ == "__main__":
	main()
	

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
import collections

def main():
	N, M = map(int, input().split(" "))
	
	bridge = []
	for _ in range(M):
		a, b = map(int, input().split(" "))
		bridge.append((a, b))
		
	bridge.reverse()
	uf = UnionFind(N)
	ans = []
	fuben = 0
	ans.append(N * (N-1) // 2)
	
	for i, val in enumerate(bridge):
		a, b = val
		a, b = a-1, b-1
		if False == uf.is_same(a, b):
			child_a = uf.getCoun(a)
			child_b = uf.getCoun(b)
			ans.append(ans[i] - (child_a * child_b))
		else:
			ans.append(ans[i])
		uf.union(a, b)
		
	ans.pop()
	ans.reverse()
	for val in ans:
		print(val)
	

class UnionFind(object):
	def __init__(self, n=1):
		self.par = [i for i in range(n)]
		self.rank = [0 for _ in range(n)]
		self.size = [1 for _ in range(n)]
		
	# x が属するグループを探索
	def find(self, x):
		if self.par[x] == x:
			return x
		else:
			self.par[x] = self.find(self.par[x])
			return self.par[x]
		
	# x と y のグループを結合
	def union(self, x, y):
		x = self.find(x)
		y = self.find(y)
		if x != y:
			x_size = self.size[x]
			y_size = self.size[y]
			sum = x_size + y_size
			self.size[x] = sum
			self.size[y] = sum
			if self.rank[x] < self.rank[y]:
				x, y = y, x
			if self.rank[x] == self.rank[y]:
				self.rank[x] += 1
			self.par[y] = x
	
	# x と y が同じグループがどうか
	def is_same(self, x, y):
		return self.find(x) == self.find(y)
		
	def getCoun(self, a):
		x = self.find(a)
		return self.size[x]

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

import itertools

A, B, M = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

x = [0] * M
y = [0] * M
c = [0] * M

ans = []

for i in range(M):
    x[i], y[i], c[i] = [int(k) for k in input().split()]

temp = list(itertools.product(a, b))
for i,j in temp:
    ans.append(i+j)


for i in range(M):
    ans.append(a[x[i]-1] + b[y[i]-1] - c[i])

print(min(ans))

### FIXED CODE ###

A, B, M = [int(x) for x in input().split()]
a = [int(x) for x in input().split()]
b = [int(x) for x in input().split()]

x = [0] * M
y = [0] * M
c = [0] * M

ans = []
ans.append(min(a) + min(b))
for i in range(M):
    x[i], y[i], c[i] = [int(k) for k in input().split()]

for i in range(M):
    ans.append(a[x[i] - 1] + b[y[i] - 1] - c[i])

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

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    k = max(a).bit_length()
    mod = 10**9 + 7
    bk = [[0] * n for _ in range(k)]
    for kk in range(k):
        for i in range(n):
            bk[kk][i] = a[i] // 2**kk % 2
    bc = [[bk[kk][-1]] * n for kk in range(k)]
    for kk in range(k):
        for i in range(n - 1, 0, -1):
            bc[kk][i - 1] = bc[kk][i] + bk[kk][i - 1]
    c = 0
    for kk in range(k):
        kc = 0
        for i in range(n - 1):
            if bk[kk][i] == 0:
                kc = (kc + bc[kk][i + 1]) % mod
            else:
                kc = (kc + n - 1 - i - bc[kk][i + 1]) % mod
        kc = kc * pow(2, kk, mod) % mod
        c = (c + kc) % mod
    print(c)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    k = max(a).bit_length()
    mod = 10**9 + 7
    c = 0
    for kk in range(k):
        h, l = 0, 0
        for ai in a:
            if ai // 2**kk % 2:
                h += 1
            else:
                l += 1
        kc = h * l * pow(2, kk, mod) % mod
        c = (c + kc) % mod
    print(c)

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

from collections import deque
n, l, b = input(), raw_input().split(), deque()
for t in xrange(n):
    b.append(l[t])
    b.reverse()
print ' '.join(b)

### FIXED CODE ###

from collections import deque
n, l, b = input(), raw_input().split(), deque()
for t in xrange(n):
    if (t + 1) % 2:
        b.append(l[t])
    else:
        b.appendleft(l[t])
print ' '.join(reversed(b)) if n % 2 else ' '.join(b)
### BUGGY CODE ###

from collections import defaultdict, deque

n, m = [int(i) for i in raw_input().split()]

children = defaultdict(list)
parents = defaultdict(list)

for _ in range(m):
    u, v = [int(i) for i in raw_input().split()]
    children[u-1].append(v-1)
    parents[v-1].append(u-1)

# def longest_path(children, parents, n):
#     f = [None] * n
#     targets = [x for y in children.values() for x in y]
#     starts = [v for v in range(n) if v not in targets]

#     for v in starts:
#         f[v] = 0

#     # print f
#     for i in range(n):
#         get_f(children, parents, f, i)

#     # print f
#     return max(f)

def get_f(children, parents, f, i):
    if f[i] != None:
        return f[i]

    for v in parents[i]:
        f[i] = max(f[i], get_f(children, parents, f, v) + 1)

    return f[i]

def longest_path(children, parents, n):
    targets = [x for y in children.values() for x in y]
    starts = [v for v in range(n) if v not in targets]
    f = [None] * n
    

    Q = deque([])
    for v in starts:
        f[v] = 0
        Q.append((v, 0))

    output = 0
    while len(Q) > 0:
        node, length = Q.pop()
        output = max(output, length)
        for v in children[node]:
            Q.append((v, length+1))

    return output

print(longest_path(children, parents, n))

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(1000000)

n, m = [int(i) for i in raw_input().split()]
parents = defaultdict(list)

i = 0
while i < m:
    u, v = [int(x) for x in raw_input().split()]
    parents[v-1].append(u-1)
    i += 1

def calc_f(parents, f, i):
    if i < 0 or i >= len(f):
        return 0

    if f[i] != -1:
        return f[i]

    f[i] = 0
    for v in parents[i]:
        f[i] = max(f[i], calc_f(parents, f, v)+1)

    return f[i]

f = [-1] * n
j = 0
while j < n:
    calc_f(parents, f, j)
    j += 1

if len(f) == 0:
    print 0
else:
    print max(f)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=a[0]
i=1
while i<n:
    ans*=a[i]
    i+=1
if ans>1000000000000000000:
    ans=-1
print(ans)


### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=a[0]
i=1
if 0 in a:
    ans=0
else:
    while i<n:
        ans*=a[i]
        i+=1
        if ans>1000000000000000000:
            ans=-1
            break
print(ans)
### BUGGY CODE ###

N,X,Y = map(int,input().split())
S = [[0 for j in range(N)] for i in range(N)]
A = []
for i in range(N-1):
    a = i+1
    for j in range(i+1,N):
        b = j+1
        S[i][j] = min([b-a,abs(X-a)+abs(Y-b)+1])
for i in range(N-1):
    for j in range(i+1,N):
        A.append(S[i][j])
for i in range(1,N):
    print(A.count(i))

### FIXED CODE ###

N,X,Y = map(int,input().split())
A = [0 for i in range(N)]
for i in range(N-1):
    a = i+1
    for j in range(i+1,N):
        b = j+1
        A[min([b-a,abs(X-a)+abs(Y-b)+1])] += 1
for i in range(1,N):
    print(A[i])
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
  As = list(map(int, input().split()))
  As = list(reversed(list(map(lambda a: N-a, As))))
  A.append(As)
A.reverse()
#print(A)
d = 0
n = 0
while True:
  gs = []
  for i in range(N):
    if A[i] == []:
      continue
    j = A[i][-1]
    if j < i:
      continue
    if A[j] == []:
      continue
    if A[j][-1] == i:
      n += 1
      gs.append((i, j))
  if gs == []:
    if n == N*(N-1)//2:
      break
    print(-1)
    exit()
  for i, j in gs:
    A[i].pop()
    A[j].pop()
  d += 1
print(d)


### FIXED CODE ###

N = int(input())
A = []
for i in range(N):
  As = list(map(int, input().split()))
  As = list(reversed(list(map(lambda a: a-1, As))))
  A.append(As)
#print(A)
d = 0
n = 0
l = list(range(N))
while True:
  n2 = 0
  l2 = []
  s2 = set()
  for i in l:
    if A[i] == []:
      continue
    j = A[i][-1]
    if A[j] == []:
      continue
    if i in s2 or j in s2:
      continue
    if A[j][-1] == i:
      n += 1
      n2 += 1
      s2.add(i)
      s2.add(j)
      l2.append(i)
      l2.append(j)
      A[i].pop()
      A[j].pop()
  if n2 == 0:
    if n == N*(N-1)//2:
      break
    print(-1)
    exit()
  l = l2
  d += 1
print(d)
### BUGGY CODE ###

class SegT():
    def __init__(self, size):
        self.size = 1
        while self.size < size: self.size *= 2
        self.data = [set() for _ in range(self.size * 2 - 1)] 
    
    def update(self, i, x):
        i += (self.size - 1)
        self.data[i] = {x}
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self.data[i*2+1] | self.data[i*2+2]
        
    def get(self, a, b, node=0, l=0, r=-1):
        if r < 0: r = self.size
        if r <= a or b <= l: return set()
        if a <= l and r <= b: return self.data[node]
        vl = self.get(a, b, node*2+1, l, (l+r)//2)
        vr = self.get(a, b, node*2+2, (l+r)//2, r)
        return vl | vr

N = int(input())
S = input()
Q = int(input())

segt = SegT(N)
for i in range(N):
    segt.update(i, S[i])

for i in range(Q):
    t, l, r = input().split()
    if t == "1":
        segt.update(int(l)-1, r)
    else:
        x = segt.get(int(l)-1,int(r))
        print(len(x))


### FIXED CODE ###

class SegT():
    def __init__(self, size):
        self.size = 1
        while self.size < size: self.size *= 2
        self.data = [0] * (self.size * 2 - 1)
    
    def update(self, i, x):
        i += (self.size - 1)
        self.data[i] = x
        while i > 0:
            i = (i - 1) // 2
            self.data[i] = self.data[i*2+1] | self.data[i*2+2]
        
    def get(self, a, b, node=0, l=0, r=-1):
        if r < 0: r = self.size
        if r <= a or b <= l: return 0
        if a <= l and r <= b: return self.data[node]
        vl = self.get(a, b, node*2+1, l, (l+r)//2)
        vr = self.get(a, b, node*2+2, (l+r)//2, r)
        return vl | vr

N = int(input())
S = input()
Q = int(input())

segt = SegT(N)
for i in range(N):
    x = ord(S[i]) - ord('a')
    segt.update(i, (1<<x))

for i in range(Q):
    t, l, r = input().split()
    if t == "1":
        x = ord(r) - ord('a')
        segt.update(int(l)-1, (1<<x))
    else:
        x = segt.get(int(l)-1,int(r))
        ans = 0
        for i in range(26):
            if x>>i&1: ans += 1
        print(ans)
### BUGGY CODE ###

s = input()
t = input()

ls = len(s)
lt = len(t)
ans = ""
dp = [[0]*(ls+1) for i in range(lt+1)]
memo = [[""]*(ls+1) for i in range(lt+1)]

for i in range(1,lt+1):
    for j in range(1,ls+1):
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])
        memo[i][j] = memo[i-1][j-1]
        if s[j-1] == t[i-1]:
            dp[i][j] = dp[i-1][j-1]+1
            memo[i][j] = memo[i-1][j-1]+s[j-1]

i = lt
j = ls
while i-1>=0 and j-1>=0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
        continue
    if dp[i][j] == dp[i][j-1]:
        j -= 1
        continue

    i -= 1
    j -= 1
    ans = s[j] + ans

print(ans)



### FIXED CODE ###

s = input()
t = input()
N = len(s)
M = len(t)

dp = [[0]*(N+1) for i in range(M+1)]

for i in range(1,M+1):
  for j in range(1,N+1):
    if s[j-1] == t[i-1]:
      dp[i][j] = dp[i-1][j-1]+1
    else:
      dp[i][j] = max(dp[i-1][j],dp[i][j-1])
L = dp[-1][-1]
i = M
j = N
ans = [""]*L
cur = L-1
while i>=0 and j>=0:
  if dp[i][j] != dp[i-1][j] and dp[i][j] != dp[i][j-1]:
    ans[cur] = s[j-1]
    i -= 1
    j -= 1
    cur -= 1
  elif dp[i][j] == dp[i-1][j]:
    i -= 1
  else:
    j -= 1
print("".join(ans))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Sep 14 00:57:13 2020

@author: liang
"""

N, Q = map(int, input().split())
S = input()
lis = list()
for i in range(len(S) - 1):
    if S[i:i+2] == "AC":
        lis.append(i)
    #print(lis[i:i+2])
#print(lis)
for i in range(Q):
    l, r = map(int, input().split())
    l -= 1
    r -= 1
    ans = 0
    for t in lis:
        if l <= t < r:
            ans += 1
    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Mon Sep 14 00:57:13 2020

@author: liang
"""

N, Q = map(int, input().split())
S = input()
S += "a"
d = [0]*(N+1)
count = 0
for i in range(len(S)-1):
    if S[i:i+2] == "AC":
        count += 1
    #print(i)
    d[i+1] = count
#print(lis)
#print(d)
for i in range(Q):
    l, r = map(int, input().split())
    ans = d[r-1] - d[l-1]
    print(ans)
### BUGGY CODE ###

A,B,K = map(int,input().split())

for i in range(K):
    if A !=0:
        A = A-1
    else:
        B = B-1

print(A,B)

### FIXED CODE ###

A,B,K = map(int,input().split())

if A+B <= K:
    print(0,0)
elif A-K<=0:
    B = B-(K-A)
    A = 0
    print(A,B)
else:
    A = A-K
    print(A,B)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
L=list()
ans=0
for n in A:
  L.append(n)
  if n==min(L):
    ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
a=A[0]
ans=1
for n in range(1,N):
  if a>A[n]:
    ans+=1
    a=A[n]
print(ans)