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

from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
new=[0]*N
A.sort()
insuu=[0]*(A[N-1]+1)
pf={}
l=[]
ans=A[0]
cnt=0
p=(10**9)+7
"""
for i in range(N):
    m = A[i]
    for j in range(2,int(m**0.5)+1):
        while m%j==0:
            pf[j]=pf.get(j,0)+1
            m//=j
    if m>1:pf[m]=1
    #print(pf)
    keys=list(pf.keys())
    values=list(pf.values())
    pf={}
    for j in range(len(keys)):
        if insuu[keys[j]]<values[j]:
            insuu[keys[j]]=values[j]
        #print(insuu)
    #print(l)
for i in range(1,A[N-1]+1,1):
    if insuu[i]>0:
        ans=ans*pow(i,insuu[i])
for i in range(N):
    new[i]=ans//A[i]
#print(ans,new)
for i in range(N):
    cnt=(cnt+new[i])%p
print(cnt)

#print(l)	#これでlistになった
"""
for i in range(N-1):
    ans=(ans*A[i+1])//gcd(ans,A[i+1])
#print(ans)
for i in range(N):
    cnt=(cnt+(ans//A[i])%p)%p
print(cnt%p)

### FIXED CODE ###

def modpow(a,n,p):
    if n==0:
        return 1
    x=modpow(a,n//2,p)
    x=(x*x)%p
    if (n%2)==1:
        x=(x*a)%p
    return x%p
def modinv(a,p):
    return modpow(a,p-2,p)
from fractions import gcd
N=int(input())
A=list(map(int,input().split()))
new=[0]*N
A.sort()
insuu=[0]*(A[N-1]+1)
pf={}
l=[]
ans=1
cnt=0
p=(10**9)+7

for i in range(N):
    m = A[i]
    for j in range(2,int(m**0.5)+1):
        while m%j==0:
            pf[j]=pf.get(j,0)+1
            m//=j
    if m>1:pf[m]=1
    #print(pf)
    keys=list(pf.keys())
    values=list(pf.values())
    pf={}
    for j in range(len(keys)):
        if insuu[keys[j]]<values[j]:
            insuu[keys[j]]=values[j]
        #print(insuu)
    #print(l)
for i in range(1,A[N-1]+1,1):
    if insuu[i]>0:
        ans=ans*pow(i,insuu[i])
#print(ans)
for i in range(N):
    #print((ans*modinv(A[i],p))%p)
    cnt=(cnt+(ans*modinv(A[i],p))%p)%p
print(cnt%p)
### BUGGY CODE ###

n = int(input())
li = []
for i in range(n):
  li.append(input())
li_a = sorted(list(set(li)))
li_ans = [0 for i in range(len(li_a))]
for x in li:
  b = li_a.index(x)
  li_ans[b] += 1
for i in range(len(li_ans)):
  if li_ans[i] == max(li_ans):
    print(li_a[i])

### FIXED CODE ###

n = int(input())
li = []
for i in range(n):
  li.append(input())
from collections import Counter
s = Counter(li)
a = list(s.values())
b = list(s.keys())
ans = []
m = 0
for x in a:
  m = max(m, x)
for i in range(len(a)):
  if a[i] == m:
    ans.append(b[i])
ans_a = sorted(ans)
ans_b = "\n".join(ans_a)
print(ans_b)
### BUGGY CODE ###

n = int(input())
dig_sum = 0
while n != 0:
    dig_sum += n % 10 
    n = n // 10
# print(dig_sum)
if dig_sum % 9 == 0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

def digitSum(n):
    s = str(n)
    array = list(map(int, s))
    return sum(array)

n = int(input())
d_s = digitSum(n)
# print(d_s)
if d_s % 9 == 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

N = int(input())
XYP = [list(map(int, input().split())) for _ in range(N)]

bits = 1 << N

xmemo = [[float('inf')]*N for _ in range(bits)]
ymemo = [[float('inf')]*N for _ in range(bits)]

for b in range(bits):
  for i in range(N):
    xmemo[b][i] = min(XYP[i][2]*abs(XYP[i][0]), xmemo[b][i])
    ymemo[b][i] = min(XYP[i][2]*abs(XYP[i][1]), ymemo[b][i])
    if not (b & (1<<i)):
      continue
    for j in range(N):
      xmemo[b][j] = min(XYP[j][2]*abs(XYP[i][0]-XYP[j][0]), xmemo[b][j])
      ymemo[b][j] = min(XYP[j][2]*abs(XYP[i][1]-XYP[j][1]), ymemo[b][j])
      
ans = [float('inf')]*(N+1)

pos = 3**N
for t in range(pos):
  l = []
  for _ in range(N):
    l.append(t%3)
    t //= 3
  xi = 0
  yi = 0
  cnt = 0
  for i in range(N):
    if l[i] == 0:
      xi += 1 << i
      cnt += 1
    elif l[i] == 1:
      yi += 1 << i
      cnt += 1
  tmp = 0
  for i in range(N):
    tmp += min(xmemo[xi][i], ymemo[yi][i])
  ans[cnt] = min(ans[cnt], tmp)
  
for i in range(N+1):
  print(ans[i])

### FIXED CODE ###

import sys

N = int(input())
XYP = [list(map(int, input().split())) for _ in range(N)]

bits = 1 << N

xmemo = [sys.maxsize]*(N*bits)
ymemo = [sys.maxsize]*(N*bits)

for b in range(bits):
  for i in range(N):
    xmemo[b*N+i] = min(XYP[i][2]*abs(XYP[i][0]), xmemo[b*N+i])
    ymemo[b*N+i] = min(XYP[i][2]*abs(XYP[i][1]), ymemo[b*N+i])
    if not (b & (1<<i)):
      continue
    for j in range(N):
      xmemo[b*N+j] = min(XYP[j][2]*abs(XYP[i][0]-XYP[j][0]), xmemo[b*N+j])
      ymemo[b*N+j] = min(XYP[j][2]*abs(XYP[i][1]-XYP[j][1]), ymemo[b*N+j])
      
ans = [sys.maxsize]*(N+1)

for b in range(bits):
  b_ = b
  cnt = bin(b_).count('1')
  while b_ >= 0:
    b_ &= b
    yi = b - b_
    tmp = 0
    for i in range(N):
      tmp += min(xmemo[b_*N+i], ymemo[yi*N+i])
    ans[cnt] = min(ans[cnt], tmp)
    b_ -= 1
  
for i in range(N+1):
  print(ans[i])
### BUGGY CODE ###


def main():
    H, N = map(int, input().split())
    AB = [tuple(map(int, input().split())) for i in range(N)]

    dp = [-1]*(H+1)
    dp[H] = 0

    for i in range(H, 0, -1):
        for a, b in AB:

            if dp[i] >= 0:
                next = max(i-a, 0)
                if dp[next] < 0:
                    dp[next] = dp[i] + b
                else:
                    if dp[next] > dp[i] + b:
                        dp[next] = dp[i] + b

    print(dp[0])
main()

### FIXED CODE ###

import math
import sys
input = sys.stdin.readline
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]

dp = [[10**10, 0] for i in range(H+1)]
dp[0][0] = 0
# i 減らすのに最小で必要なMP

for i in range(1, H+1):
    if dp[i-1][1] > 0:
        dp[i][0] = dp[i-1][0]
        dp[i][1] = dp[i-1][1] - 1
    else:
        for A, B in AB:
            if A > i:
                if dp[i][0] > B:
                    dp[i][0] = B
                    dp[i][1] = A - i
            else:
                if dp[i][0] > dp[i - A][0] + B:
                    dp[i][0] = dp[i-A][0] + B
                    dp[i][1] = dp[i-A][1] + A - i

print(dp[H][0])
### BUGGY CODE ###

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

s = input()

for i in range(q):
    l,r = map(int, input().split())
    print(s[l-1:r].count("AC"))

### 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 ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    if g != 1:
        raise Exception('modular inverse does not exist')
    else:
        return x % m
s=list(input())
mod=10**9+7
K=modinv(10,13)
dp=[[0 for k in range(13)] for i in range(len(s))]
#dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
num=s[0]
if s[0]=="?":
    for i in range(10):
        dp[0][i]=1
else:
    number=int(s[0])
    dp[0][number]=1

for i in range(1,len(s)):
    if s[i]=="?":
        for k in range(13):
            for j in range(10):
                dp[i][k]+=dp[i-1][((k-j)*K)%13]
        dp[i][k]=dp[i][k]%mod
    else:
        number=int(s[i])
        for k in range(13):
            dp[i][k]=dp[i-1][((k-number)*K)%13]%mod
print(dp[len(s)-1][5]%mod)


### FIXED CODE ###

def xgcd(a, b):
    x0, y0, x1, y1 = 1, 0, 0, 1
    while b != 0:
        q, a, b = a // b, b, a % b
        x0, x1 = x1, x0 - q * x1
        y0, y1 = y1, y0 - q * y1
    return a, x0, y0
def modinv(a, m):
    g, x, y = xgcd(a, m)
    return x % m
def main():
    s=list(input())
    mod=10**9+7
    K=modinv(10,13)
    U=[[0 for i in range(10) ]for k in range(13)]
    for i in range(13):
        for j in range(10):
            U[i][j]=((i-j)*K)%13

    dp=[[0 for k in range(13)] for i in range(len(s))]
    #dp[i][j]=初めのindex=i番目まで見たときに、あまりがjになるような方法の総数
    num=s[0]
    if s[0]=="?":
        for i in range(10):
            dp[0][i]=1
    else:
        number=int(s[0])
        dp[0][number]=1

    for i in range(1,len(s)):
        for k in range(13):
            if s[i]=="?":
                for j in range(10):
                    dp[i][k]+=dp[i-1][U[k][j]]%mod
            else:
                number=int(s[i])
                dp[i][k]=dp[i-1][U[k][number]]%mod
    print(dp[len(s)-1][5]%mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

import sys
from operator import itemgetter
from itertools import accumulate
from collections import defaultdict
import bisect
input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

dp_dict = [defaultdict(lambda: 0)]
dp_dict[0][0] = 0
dp_dict[0][vws[0][1]] = vws[0][0]

for i in range(1, min(2**14, N)):
    v, w = vws[i]
    dp_dict.append(dp_dict[(i-1)//2].copy())
    for w_sum, v_sum in dp_dict[(i-1)//2].items():
        dp_dict[i][w_sum + w] = max(v_sum + v, dp_dict[i][w_sum + w])

values_list = []
weights_list = []
for d in dp_dict:
    ls = sorted(d.items(), key = itemgetter(0))
    weights, values = zip(*ls)
    values = list(accumulate(values, max))
    values_list.append(values)
    weights_list.append(weights)
        
Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    if V-1 < len(dp_dict):
        index = bisect.bisect_right(weights_list[V-1], L) - 1
        print(values_list[V-1][index])
    else:
        V -= 1
        d = defaultdict(lambda: 0)
        d[0] = 0
        while V >= len(dp_dict):
            v, w = vws[V]
            iterator = list(d.items())
            for w_sum, v_sum in iterator:
                d[w_sum + w] = max(v_sum + v, d[w_sum + w])
            V = (V-1) // 2

        v_max = 0
        for w1, v1 in d.items():
            index = bisect.bisect_right(weights_list[V], L-w1) - 1
            if index == -1:
                continue
            v_max = max(v_max, v1 + values_list[V][index])
        print(v_max)


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

import itertools

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

cnt =0
for c in itertools.combinations(a, 3):
    if c[0] ^ c[1] ^ c[2] == 0:
        cnt =cnt+1
        
if cnt == N/3:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

a = [input() for i in range(2)]
 
N = int(a[0])
data = a[1].split(' ')
 
data = [int(i) for i in data]
 
result = []
a = 0
for i in range(N):
    a = a ^ data[i]
    
if a == 0:
    print('Yes')
    exit()
    
print('No')
### BUGGY CODE ###

N, M, K = map(int, input().split())

MOD = 10 ** 9 + 7

def combination(n, m):
    c = 1
    for i in range(m):
        c *= n-i
    for i in range(1, m+1):
        c //= i
    return c

pattern = combination(M*N-2, K-2) % MOD

ans = 0
for d in range(1, N):
    ans += M * M * (N - d) * d
for d in range(1, M):
    ans += N * N * (M - d) * d
print((ans*pattern)%MOD)


### FIXED CODE ###

N, M, K = map(int, input().split())

MOD = 10 ** 9 + 7

def combination(n, m):
    c = 1
    m = min(n-m, m)
    for i in range(m):
        c = c * (n-i) * pow(m-i, MOD-2, MOD) % MOD
    return c

pattern = combination(N*M-2, K-2)

def diff_x_pattern(val):
    ret = 0
    for d in range(1, val):
        ret += ((val - d) * d) % MOD
    return ret

ans = (M * M * diff_x_pattern(N)) % MOD
ans += (N * N * diff_x_pattern(M)) % MOD
print((ans*pattern)%MOD)
### BUGGY CODE ###

import collections
n = int(input())
s = [collections.Counter(input()) for i in range(n)]
ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if s[i] == s[j]:
            ans += 1
print(ans)

### FIXED CODE ###

def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import copy
from itertools import permutations
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7

from itertools import permutations
from math import factorial, hypot

#############
# Main Code #
#############

N = getN()
S = [''.join(sorted(list(input()))) for i in range(N)]
ans = 0
for i in Counter(S).items():
    ans += i[1] * (i[1] - 1) // 2
print(ans)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n=int(input())
mod=10**9+7
a=list(map(int,input().split()))
s=[0]*61
for i in range(n):
  c=format(a[i], 'b')
  L=len(c)
  for j in range(L)[::-1]:
    s[L-j-1]+=int(c[j])
ans=0
for i in range(61):
  ans+=2**(i)*(s[i])*(n-s[i])
  ans%=mod
print(ans)


### FIXED CODE ###

import sys
input=sys.stdin.readline
n=int(input())
mod=10**9+7
a=list(map(int,input().split()))
s=[0]*61
for i in range(n):
  c=format(a[i], 'b')
  L=len(c)
  for j in range(L)[::-1]:
    s[L-j-1]+=int(c[j])
ans=0
for i in range(61):
  ans+=2**(i)*(s[i])*(n-s[i])
  ans%=mod
print(ans)
### BUGGY CODE ###

N = int(input())
S = list(input())
ba = ord("a")
for i in range(N):
  S[i] = ord(S[i]) - ba + 1
B = 27
mod = 10 ** 11 + 7
def contain(a, b):
  al = len(a)
  bl = len(b)
  #print(al, a)
  if al > bl: return False
  t = pow(B, al)
  ah = 0; bh = 0
  for i in range(al):
    ah = ah * B + a[i]
    bh = bh * B + b[i]
  for i in range(bl - al + 1):
    if ah == bh: return True
    if i + al < bl:
      #print(i, i + al)
      bh = bh * B + b[i + al] - b[i] * t
  return False
res = 0
for i in range(N):
  r = min(i + N // 2, N + 1)
  l = i + 1
  m = (l + r) // 2
  while r - l > 3:
    r = min(i + N // 2, N + 1)
    l = i + 1
    m = (l + r) // 2
    if contain(S[i: m], S[m: ]):
      l = m
      res = max(res, m - i)
    else:
      r = m
  if m <= N:
    if contain(S[i: m + 1], S[m + 1: ]):
      res = max(res, m + 1 - i)
  if m + 1 <= N:
    if contain(S[i: m + 2], S[m + 2: ]):
      res = max(res, m + 2 - i)
  if m + 2 <= N:
    if contain(S[i: m + 3], S[m + 3: ]):
      res = max(res, m + 3 - i)
print(res)

### FIXED CODE ###

N = int(input())
S = list(input())
#LCSRe i番目とj番目でそれぞれ終わるような共通文字列の長さ
#i < j であるi文字目とj文字目が等しいならLCSRe[i + 1][j + 1] = LCSRe[i][j] + 1
#res_lengthよりLCSReの更新した値が大なら、その時のindexをiへ、res_lengthも更新

def longestRepeatedSubstring(s): 
  n = len(s) 
  LCSRe = [[0 for _ in range(n + 1)] for _ in range(n + 1)] 
  res = "" 
  res_length = 0
  index = 0
  for i in range(1, n + 1): 
    for j in range(i + 1, n + 1): 
      if s[i - 1] == s[j - 1] and LCSRe[i - 1][j - 1] < j - i: 
        LCSRe[i][j] = LCSRe[i - 1][j - 1] + 1
        if LCSRe[i][j] > res_length: 
          res_length = LCSRe[i][j] 
          index = max(i, index) 
      else: 
        LCSRe[i][j] = 0
  #print(LCSRe)
  if res_length > 0: 
    for i in range(index - res_length + 1, index + 1): 
      res = res + s[i - 1] 
  return res_length
print(longestRepeatedSubstring(S))
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.empty((0,2),int)
for i in range(n):
    b = np.array([[int(i) for i in input().split()]])
    a = np.append(a,b,axis=0)

a = a[np.argsort(a[:, 1])]

ans = "Yes"
for i in range(len(a)):
    if np.sum(a[0:i+1,0]) > a[i,1]:
        ans = "No"
        break
print(ans)

### FIXED CODE ###

import sys
from operator import itemgetter
def input():
    return sys.stdin.readline()[:-1]
n = int(input())
a = [list(map(int, input().split())) for i in range(n)]
a.sort(key=itemgetter(1))
ans = "Yes"
k = 0
for i in range(len(a)):
    k += a[i][0]
    if k > a[i][1]:
        ans = "No"
        break
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

N = int(input())
d = [int(input()) for i in range(N)]

M = max(d)
D = d[:]
d.remove(M)
m = max(d)

for j in range(N):
    if D[j]==M:
        print(m)
    else:
        print(M)
### BUGGY CODE ###

N = int(input())
AB = [list(map(int, input().split())) for _ in range(N)]

a = b = 0
for i in range(N):
  if i % 2 == 0:
    AB.sort(key=lambda x:x[1])
    a += AB[-1][0]
  else:
    AB.sort()
    b += AB[-1][1]
  AB[-1] = [0, 0]
print(a-b)

### FIXED CODE ###

import numpy as np
n = int(input())
A,B = np.array([input().split() for _ in range(n)], dtype=np.int64).T

ans = A.sum() #全部先手が取る
improve = A+B #後手がとると改善する量
improve.sort()
ans -= improve[::-1][1::2].sum()
print(ans)
### BUGGY CODE ###

H, W = map(int, input().split())
S = []
for i in range(H):
    s = input()
    S.append(s)

ansList = []

def dfs(h, w, root):
    root.append(S[h][w])
    if (h == H - 1 and w == W - 1):
        ansList.append(root.copy())
        return
    else:
        if (h+1 < H):
            dfs(h+1, w, root.copy())
        if (w+1 < W):
            dfs(h, w+1, root.copy())
dfs(0, 0, [])

ans = H * W
for a in ansList:
    ans = min(ans, a.count("#"))

print(ans)


### FIXED CODE ###

H, W = map(int, input().split())
dp = [[H*W for __ in range(W)] for _ in range(H)]
dh = [1, 0]
dw = [0, 1]
S = []
for i in range(H):
    s = input()
    S.append(s)

if (S[0][0] == '#'):
    dp[0][0] = 1
else:
    dp[0][0] = 0


for i in range(H):
    for j in range(W):
        for k in range(2):
            nh = i + dh[k]
            nw = j + dw[k]
            if nh >= H or nw >= W:
                continue
            add = 0
            if (S[nh][nw] == "#" and S[i][j] == "."):
                add = 1
            dp[nh][nw] = min(dp[nh][nw], dp[i][j] + add)


print(dp[H-1][W-1])
### BUGGY CODE ###

N,W = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for item in range(N) :
    w_i,v_i = L[item]
    for weight in range(W+1) :
        if weight - w_i >= 0 :
            dp[item+1][weight] = max(dp[item][weight], dp[item][weight-w_i] + v_i)
        else :
            dp[item+1][weight] = dp[item][weight]

ans = dp[N][W]

print(ans)


### FIXED CODE ###

N,W = map(int,input().split())
L = list(list(map(int,input().split())) for i in range(N))

dp = [[0 for i in range(W+1)] for j in range(N+1)]

for item in range(N) :
    w_i,v_i = L[item]
    for weight in range(W+1) :
        if weight - w_i >= 0 :
            dp[item+1][weight] = max(dp[item][weight], dp[item][weight-w_i] + v_i)
        else :
            dp[item+1][weight] = dp[item][weight]

ans = dp[N][W]

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

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4
    dp = [INF] * MAX_LEN
    dp[0] = 0
    for _ in range(n):
        v, w = map(int, input().split())
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

if __name__ == "__main__":
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
INF = 10**9

def main(): 
    h, n = [int(item) for item in input().split()]
    MAX_LEN = h + 10**4 - 2
    dp = [INF] * MAX_LEN
    dp[0] = 0
    vw = []
    for _ in range(n):
        v, w = map(int, input().split())
        vw.append((v, w))
    vw.sort(reverse=True, key=lambda x:x[0])
    for v, w in vw:
        for j in range(h):
            if dp[j] == INF:
                continue
            tmp = dp[j] + w
            if tmp < dp[j+v]:
                dp[j+v] = tmp
    print(min(dp[h:]))

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

import copy
def calc(n):
    d = copy.deepcopy(h)
    d = [dd - (b * n) for dd in d if (dd - (b*n)) > 0]
    a_num = sum([dd // (a - b) if (dd % (a - b) == 0) else (dd // (a - b)) + 1 for dd in d])
    if a_num <= n:
        return True
    return False

n, a, b = map(int, input().split())
h = []
for _ in range(n):
    h.append(int(input()))
ans = 0


left = 1
right = (max(h) + 1) // (b)
middle = (left + right) // 2
middle_1 = middle - 1
while not ((calc(middle)) & (not calc(middle_1))):
    if not calc(middle):
        left = middle
        middle = (left + right) // 2
        middle_1 = middle - 1
    else:
        right = middle
        middle = (left + right) // 2
        middle_1 = middle - 1
print(middle)

### FIXED CODE ###

def calc(n):
    damage = (b * n)
    d = [max(dd - damage, 0) for dd in h]
    a_num = 0
    for i in range(len(d)):
        a_num += max(0, 1 + (d[i]-1) // (a - b))
    if a_num <= n:
        return True
    return False

n, a, b = map(int, input().split())
h = []
for _ in range(n):
    h.append(int(input()))
ans = 0
h.sort()

left = 0
right = 10000000000

while (right - left) > 1:
    middle = (left + right) // 2
    if calc(middle):
        right = middle
    else:
        left = middle
print(right)
### BUGGY CODE ###

A, B, K = map(int, input().split())
for i in range(A, B+1):
  if i-A<K or B-i<K:
    print(i)

### FIXED CODE ###

A, B, K = map(int, input().split())
if K>(B-A)//2:
  for i in range(A, B+1):
    if i-A<K or B-i<K:
      print(i)
else:
  for i in range(A, A+K):
    print(i)
  for i in range(B-K+1, B+1):
    print(i)
### BUGGY CODE ###

import heapq

n = int(input())
list_score = []
for i in range(n):
    list_score.append(int(input()))

list_ans = list_score.copy()
list_ans.sort()
heapq.heapify(list_ans)

for i in range(n):
    a = list_score[i]
    list_ans.remove(a)
    print(list_ans[-1])
    heapq.heappush(list_ans, a)

### FIXED CODE ###

import heapq

n = int(input())
list_score = []
for i in range(n):
    list_score.append(int(input()))

list_ans = list_score.copy()
list_ans.sort()


for i in range(n):
    a = list_score[i]
    if a == list_ans[-1]:
        print(list_ans[-2])
    else:
        print(list_ans[-1])
### BUGGY CODE ###

h, n  = map(int,input().split())
am = [list(map(int, input().split())) for i in range(n)] 

dp = [float('inf')]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp_val = dp[i]
    for a, m in am:
        if a >= i:#overkill
            dp_val = min(dp_val, m)
        else:
            dp_val = min(dp_val, dp[i-a]+m)
    dp[i] = dp_val
print(dp[h])
    


### FIXED CODE ###

h, n  = map(int,input().split())
am = [list(map(int, input().split())) for i in range(n)] 

dp = [float('inf')]*(h+1)
dp[0] = 0
for i in range(1,h+1):
    dp_val = dp[i]
    for a, m in am:
        if a >= i:#overkill
            dp_val = min(dp_val, m)
        else:
            dp_val = min(dp_val, dp[i-a]+m)
    dp[i] = dp_val
print(dp[h])
### BUGGY CODE ###

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

for lr in LR:
    l, r = lr[0], lr[1]
    s = S[l-1: r]
    i = 0
    I = len(s)
    cnt = 0
    while i < len(s) - 1 :
        if s[i] == "A" and s[i + 1] == "C":
            cnt += 1
            i += 2
        else:
            i += 1
    #cnt = s.count("AC")
    print(cnt)

### FIXED CODE ###

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

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 = LR[i][0], LR[i][1]
    cnt = t[r - 1] - t[l -1]
    print(cnt)