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

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    S = S[::-1]
    N = len(S)
    dp = [0 for j in range(13)]
    dp2 = [0 for j in range(13)]

    for i, c in enumerate(S):
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[j] = 1
            else:
                dp[int(c)] = 1
        else:
            for k in range(13):
                if c == '?':
                    for j in range(10):
                        amari = (j * pow(10, i, 13)) % 13
                        dp2[k] = (dp2[k] + dp[(k-amari)%13]) % MOD
                else:
                    amari = (int(c) * pow(10, i, 13)) % 13
                    dp2[k] = (dp2[k] + dp[(k-amari) % 13]) % MOD

            dp = dp2
            dp2 = [0 for j in range(13)]

    dprint(dp)
    print(dp[5])

solve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return sys.stdin.readline().strip()
INF = 10 ** 18
MOD = 10 ** 9 + 7

debug = True
debug = False

def dprint(*objects):
    if debug == True:
        print(*objects)

def solve():
    S = SI()
    S = S[::-1]
    N = len(S)
    dp = [0 for j in range(13)]
    dp2 = [0 for j in range(13)]

    for i, c in enumerate(S):
        if i == 0:
            if c == '?':
                for j in range(10):
                    dp[j] = 1
            else:
                dp[int(c)] = 1
        else:
            if c == '?':
                for j in range(10):
                    amari = (j * pow(10, i, 13)) % 13
                    for k in range(13):
                        dp2[k] = (dp2[k] + dp[(k-amari)%13]) % MOD
            else:
                for k in range(13):
                    amari = (int(c) * pow(10, i, 13)) % 13
                    dp2[k] = (dp2[k] + dp[(k-amari) % 13]) % MOD

            dp = dp2
            dp2 = [0 for j in range(13)]

    dprint(dp)
    print(dp[5])



solve()
### BUGGY CODE ###

def waru(a,b):
  if a%b==0:
    return a//b
  else:
    return(a//b)+1
N,M=map(int,input().split())
L2=list(map(int,input().split()))
L=[i for i in L2]
R=[1]*N
for i in range(M):
  R[L.index(max(L))]+=1
  c=zip(L2,R)
  L=[waru(x,y) for (x,y) in c]
print(max(L))

### FIXED CODE ###

def waru(a,b):
  if a%b==0:
    return a//b
  else:
    return (a//b)+1
N,K=map(int,input().split())
A=list(map(int,input().split()))
ue=sum(A)
sita=1
for i in range(50):
  n=(ue+sita)//2
  L=[waru(i,n)-1 for i in A]
  if sum(L)>K:
    sita=n
  else:
    ue=n
  if ue==sita:
    print(ue)
    exit()
  elif ue-sita==1:
    n=sita
    L=[waru(i,n)-1 for i in A]
    if sum(L)>K:
      print(n+1)
      exit()
    else:
      print(n)
      exit()
### BUGGY CODE ###

# K, N = map(int, input().split())
# a = list(map(int, input().split()))

# N = int(input())

def gcd(a, b):
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    return gcd(r, b)

K = int(input())

ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        n = gcd(a, b)
        for c in range(1, K+1):
            ans += gcd(n, c)

print(ans)

### FIXED CODE ###

# K, N = map(int, input().split())
# a = list(map(int, input().split()))

# N = int(input())

def gcd(a, b):
    if a < b:
        a, b = b, a
    r = a % b
    if r == 0:
        return b
    return gcd(r, b)

K = int(input())

ans = 0
for a in range(1, K+1):
    for b in range(1, K+1):
        n = gcd(a, b)
        for c in range(1, K+1):
            ans += gcd(n, c)

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

n = int(input())
s = [int(input()) for _ in range(n)]
t = list(range(1,n+1))
i = 1
count = 0

while(i in t):
    count += 1
    t.remove(i)
    i = s[i-1]
    if i==2:
        print(count)
        break
else:
    print(-1)

### FIXED CODE ###

n = int(input())
s = [int(input()) for _ in range(n)]
t = set()
i = 1
count = 0

while(i not in t):
    count += 1
    t.add(i)
    i = s[i-1]
    if i==2:
        print(count)
        break
else:
    print(-1)
### BUGGY CODE ###

N = int(input())

arr = map(int,input().split())
arr = sorted(arr,reverse=True)

to_multiply = []
while len(to_multiply) < 2 and len(arr) > 1:
    if arr[0] == arr[1]:
        to_multiply.append(arr[0])
    arr = arr[2:]
if len(to_multiply) == 2:
    print(to_multiply[0] * to_multiply[1])
else:
    print("0")


### FIXED CODE ###

N = int(input())
freq = {}
arr = map(int,input().split())
for i in arr:
    try:
        freq[i] += 1
    except KeyError:
        freq[i] = 1

to_multiply = []      
for i in sorted(freq.keys(),reverse=True):
    if freq[i] >= 4:
        to_multiply.append(i)
        to_multiply.append(i)
    elif freq[i] >= 2:
        to_multiply.append(i)
if len(to_multiply) >= 2:
    print(to_multiply[0] * to_multiply[1])
else:
    print("0")
### BUGGY CODE ###

n = int(input())
dList = list(map(int,input().split()))
result = []

for i in range(n):
  if i % 2 == 0:
   result.insert(0,dList[i])
  else:
   result.append(dList[i])

if n % 2 == 0:
  for i in range(len(result)-1,-1,-1):
    print(result[i],end=" ")
else:
  for i in result:
    print(i)



### FIXED CODE ###

from collections import deque
n = int(input())
dList = list(map(int,input().split()))
result = deque()

for i in range(n):
  if (i % 2 == 0 and n % 2 == 0) or (i % 2 != 0 and n % 2 != 0):
   result.append(dList[i])
  else:
   result.appendleft(dList[i])

for i in result:
  print(i,end=" ")

print()
### BUGGY CODE ###

#!/usr/bin/env python3
k = int(input())
if k % 2 < 1 or k % 5 < 0:
    print(-1)
else:
    c = 1
    mod = 7 % k
    while mod > 0:
        mod += pow(10, c, k)*7
        mod %= k
        c += 1
    print(c)


### FIXED CODE ###

#!/usr/bin/env python3
k = int(input())
if k % 2 < 1 or k % 5 < 1:
    print(-1)
else:
    c = 1
    mod = 7 % k
    mop = 7 % k
    while mod > 0:
        mop = mop*10%k
        mod += mop
        mod %= k
        c += 1
    print(c)
### BUGGY CODE ###

# floor(Ax/B) - A floor(x/B) の最大値Mを求める
# xはN以下の非負整数
# floor(Ax / B) = M + A floor(x / B)
# x / B = k + r
# Ax / B = Ak + Ar

# floor(Ak + Ar) = M + A floor(k + r)
# Ak + floor(Ar) = M + Ak + A floor(r)
# floor(Ar) = M

# r = x / B - k
# M = floor(A * (x / B - k))
#   = floor(A * x /B) - Ak
#   = floor(A/B * x) - Ak
#   = floor(A/B * x) - A * (x // B) 

# A B N
# 5 7 4

# M = floor(5/7 * x) - 5 * (x // 7)


# A B N 
# 11 10 9
# M = floor(11 / 10 * x) - 11 * (x // 10)

import math

def calcM(A, B, x):
        return math.floor(A / B * x) - A * math.floor(x / B)    

def resolve_v1(A, B, N):
    maxM = 0
    for x in range(N+1): # O(N)
        M = calcM(A, B, x)
        maxM = max(maxM, M)

    return maxM

def resolve_v2(A, B, N):
    # x == kB - 1
    maxM = 0
    for x in filter(lambda x: (x + 1) % B == 0, range(N+1)): # O(N/B)
        maxM = max(maxM, calc(A, B, x))
    return maxM


if __name__ == '__main__':
    A, B, N = map(int, input().split())
    M = resolve_v1(A, B, N)
    print(M)




### FIXED CODE ###

# floor(Ax/B) - A floor(x/B) の最大値Mを求める
# xはN以下の非負整数
# floor(Ax / B) = M + A floor(x / B)
# x / B = k + r
# Ax / B = Ak + Ar

# floor(Ak + Ar) = M + A floor(k + r)
# Ak + floor(Ar) = M + Ak + A floor(r)
# floor(Ar) = M

# r = x / B - k
# M = floor(A * (x / B - k))
#   = floor(A * x /B) - Ak
#   = floor(A/B * x) - Ak
#   = floor(A/B * x) - A * (x // B) 

# A B N
# 5 7 4

# M = floor(5/7 * x) - 5 * (x // 7)


# A B N 
# 11 10 9
# M = floor(11 / 10 * x) - 11 * (x // 10)

import math

def calcM(A, B, x):
        return math.floor(A / B * x) - A * math.floor(x / B)    

def resolve_v1(A, B, N):
    maxM = 0
    for x in range(N+1): # O(N)
        M = calcM(A, B, x)
        maxM = max(maxM, M)

    return maxM

def resolve_v2(A, B, N):
    # x == kB - 1
    maxM = calcM(A, B, N)

    for x in filter(lambda x: (x + 1) % B == 0, range(N+1)): # O(N/B)
        maxM = max(maxM, calcM(A, B, x))
    return maxM


def resolve_v3(A, B, N):
    maxM = calcM(A, B, N)

    k, r = divmod(N, B)
    if k and B * k -1 <= N:
        # k * B - 1で調査
        maxM = max(maxM, calcM(A, B, k * B - 1))
    # if r == 0:
    #     maxM = max(maxM, calcM(A, B, N - 1))

    maxM = calcM(A, B, min(N, B - 1))


    return maxM

if __name__ == '__main__':
    A, B, N = map(int, input().split())
    M = resolve_v3(A, B, N)
    print(M)
### BUGGY CODE ###

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

ans = list(S)
rev = 0
head = []
foot = []
for i in range(Q) :
    query = input()
    if query == "1" :
        rev += 1
    else :
        a, F, C = query.split()
        if F == "1" and rev%2 == 0:
            head.insert(0, C)
        elif F == "1" and rev%2 == 1:
            foot.append(C)
        elif F == "2" and rev%2 == 0:
            foot.append(C)
        else :
            head.insert(0, C)

if rev%2 == 0 :
    print("".join(head + ans + foot))
else :
    print("".join((reversed(head + ans + foot))))

### FIXED CODE ###

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

rev = 0
head = ""
foot = ""
for i in range(Q) :
    query = input()
    if query == "1" :
        rev += 1
    else :
        a, F, C = query.split()
        if F == "1" and rev%2 == 0:
            head = C + head
        elif F == "1" and rev%2 == 1:
            foot = foot + C
        elif F == "2" and rev%2 == 0:
            foot = foot + C
        else :
            head = C + head

if rev%2 == 0 :
    print("".join(list(head + S + foot)))
else :
    print("".join(list(reversed(head + S + foot))))
### BUGGY CODE ###

import itertools
def main():
    k,s = list(map(int, input().split()))
    count = 0
    for x,y,z in itertools.product(range(0, k+1),range(0, k+1),range(0, k+1)):
        count += 1 if x+y+z == s else 0
    print(count)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import itertools
url = "https://atcoder.jp//contests/abc057/tasks/abc057_a"

def main():
    k, s = list(map(int, input().split()))
    count = 0
    for x, y in itertools.product(range(k+1), range(k+1)):
        z = s - x - y
        if 0 <= z <= k:
            count += 1
    print(count)


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

import sys
import functools
INF = float("inf")


@functools.lru_cache(maxsize=None)
def power(b, p):
    if p == 0:
        return 1
    elif p == 1:
        return b
    elif p % 2 == 1:
        return b*power(b, p-1)
    else:
        return power(b*b, p//2)


def solve(p: int, a: "List[int]"):
    N = p
    MOD = p

    fac = [0]*N
    finv = [0]*N
    inv = [0]*N

    def cmb_init():
        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, N):
            fac[i] = fac[i-1]*i % MOD
            inv[i] = -inv[MOD % i]*(MOD//i) % MOD
            finv[i] = finv[i-1]*inv[i] % MOD

    @functools.lru_cache(maxsize=None)
    def cmb(n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k]*finv[n-k] % MOD) % MOD

    cmb_init()

    b = [0]*p
    for ai, av in enumerate(a):
        if av == 1:
            for i in range(p):
                b[i] += -cmb(p-1, i) * power(-ai, p-i-1)
                b[i] %= p
            b[0] += 1
            b[0] %= p
    print(*b, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    p = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(p-1-0+1)]  # type: "List[int]"
    solve(p, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import functools
INF = float("inf")


def solve(p: int, a: "List[int]"):
    N = p+1
    MOD = p

    inv = [0]*N
    inv[1] = 1
    for i in range(2, N):
        inv[i] = -inv[MOD % i]*(MOD//i) % MOD

    b = [0]*p
    for ai, av in enumerate(a):
        if av == 0:
            continue

        c = 1
        d = 1
        for i in range(p-1, -1, -1):
            b[i] += - c * d
            b[i] %= p
            c = c * i * inv[p-i] % p
            d = -d*ai % p
        b[0] += 1
        b[0] %= p
    print(*b, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    p = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(p-1-0+1)]  # type: "List[int]"
    solve(p, a)


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

from collections import deque

H,W=map(int,input().split())
sy,sx=[int(i)-1 for i in input().split()]
gy,gx=[int(i)-1 for i in input().split()]

c=[]
for i in [0]*H:
    c.append(input())

dic=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dic.append((i,j))
    
INF=10**9
vis=[[INF]*W for _ in [0]*H]

q=deque()
q.appendleft((sx,sy))
vis[sy][sx]=0
res=-1
while q:
    x,y=q.popleft()
    if (x,y)==(gx,gy):
        res=vis[y][x]
    for dx,dy in dic:
        nx,ny=x+dx,y+dy
        if 0<=nx<=W-1 and 0<=ny<=H-1:
            if vis[ny][nx]>vis[y][x] and c[ny][nx]!='#':
                if dx**2+dy**2<2:
                    vis[ny][nx]=vis[y][x]
                    q.appendleft((nx,ny))
                else:
                    vis[ny][nx]=vis[y][x]+1
                    q.append((nx,ny))
        if res>-1:
            break
    if res>-1:
            break
                
print(res)

### FIXED CODE ###

from collections import deque

H,W=map(int,input().split())
sy,sx=[int(i)-1 for i in input().split()]
gy,gx=[int(i)-1 for i in input().split()]

c=[]
for i in [0]*H:
    c.append(input())

dic=[]
for i in range(-2,3):
    for j in range(-2,3):
        if i!=0 or j!=0:
            dic.append((i,j))
    
INF=10**9
vis=[[INF]*W for _ in [0]*H]

q=deque()
q.appendleft((sx,sy))
vis[sy][sx]=0
res=-1
while q:
    x,y=q.popleft()
    if (x,y)==(gx,gy):
        res=vis[y][x]
    for dx,dy in dic:
        nx,ny=x+dx,y+dy
        if 0<=nx<=W-1 and 0<=ny<=H-1:
            if vis[ny][nx]>vis[y][x] and c[ny][nx]!='#':
                if dx**2+dy**2<2:
                    vis[ny][nx]=vis[y][x]
                    q.appendleft((nx,ny))
                else:
                    vis[ny][nx]=vis[y][x]+1
                    q.append((nx,ny))
        if res>-1:
            break
    if res>-1:
            break
                
print(res)
### BUGGY CODE ###

n=int(input())
v=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
ans=0
for i in range(1 << n):
    sum=0
    for j in range(n):
        if ((i>>j)&1)==1:
            sum += v[j] - c[j]
    ans = max(ans, sum)
print(ans)

### FIXED CODE ###

n=int(input())
v=[int(i) for i in input().split()]
c=[int(i) for i in input().split()]
dif=[]
for i in range(n):
  if v[i]>c[i]:
    dif.append(v[i]-c[i])
print(sum(dif))
### BUGGY CODE ###

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

for i in range(n):
    A[i] = (A[i] + 1) / 2

for i in range(n - k + 1):
    p = sum(A[i : i + k])
    ans = max(ans, p)

print(ans)

### FIXED CODE ###

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

for i in range(n):
    A[i] = (A[i] + 1) / 2

for i in range(n - k + 1):
    if i == 0:
        p = sum(A[i : i + k])
    else:
        p = p + A[i + k - 1] - A[i - 1]
    ans = max(ans, p)

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

from enum import Enum
from queue import Queue
import collections

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

N = int(input())
L = list(map(int,input().split()))

ans = 0
for i in range(N-2):
    A = L[i]
    for j in range(i+1,N-1):
        B = L[j]
        for k in range(j+1,N):
            C = L[k]
            if A < B + C and B < C + A and C < A + B:
                ans += 1
print(ans)


### FIXED CODE ###

from enum import Enum
from queue import Queue
import collections
import bisect

import sys
import math

BIG_NUM = 2000000000
MOD = 1000000007
EPS = 0.000000001

N = int(input())
L = list(map(int,input().split()))

L.sort()
ans = 0
for i in range(N):
    for j in range(i+1,N):
        key = bisect.bisect_left(L,L[j]-L[i]+1)
        ans += max([0,i-key])

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

from itertools import combinations
n = int(input())
l = list(map(int, input().split()))
combination_line = list(combinations(l, 3))
count = 0
for i in combination_line:
    line1 = i[0]
    line2 = i[1]
    line3 = i[2]
    if line1 < line2 + line3 and line2 < line1 + line3 and line3 < line1 + line2:
        count += 1

print(count)


### FIXED CODE ###

import bisect
n = int(input())
l = list(map(int, input().split()))
sort_l = sorted(l)
count = 0

for a in range(n):
    for b in range(a+1, n):
        c = bisect.bisect_left(sort_l, sort_l[a] + sort_l[b])
        if c > b:
            count += c - b -1
        else:
            pass     
        

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

N, M = map(int, input().split())
A = list(map(int, input().split()))
A.sort()

for _ in range(M):
	a = A.pop()
	a //= 2
	for i in range(len(A)):
		if A[i] > a:
			A.insert(i, a)
			break
	else:
		A.append(a)
			

sum = 0
for a in A: sum += a
print(sum)

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(int, input().split()))
h = []

for a in A: heapq.heappush(h, -a)
for _ in range(M):
	a = heapq.heappop(h) * -1
	a //= 2
	heapq.heappush(h, -a)

sum = 0
for _ in range(N): 
	sum -= heapq.heappop(h)
print(sum)
### BUGGY CODE ###


def f(k):
  c = 0
  x = 0
  sx = 0
  while c < k:
    x+=1
    sx = str(x)
    c+=1
    for i in range(len(sx)-1):
      if abs(int(sx[i]) - int(sx[i+1])) > 1:
        c-=1
        break
  return x
import sys
sys.setrecursionlimit(1000000)
k = int(input())

print(f(k))

### FIXED CODE ###

kk = int(input())
if kk < 10:
    print(kk)
    exit()
 
 
dp = [[0] * 10 for _ in range(15)]
dp[0] = [1] * 10
for i in range(14):
    #dp[i+1][0] += sum(dp[i])
    for j in range(10):
        for k in range(-1, 2):
            if not (0 <= j + k < 10):
                continue
            dp[i + 1][j + k] += dp[i][j]
 
a = 0
for i in range(15):
    if a+sum(dp[i][1:]) >= kk:
        break
    a += sum(dp[i][1:])
 
ii = i
 
 
for j in range(1, 10):
    if a + dp[i][j] >= kk:
        kk -= a
        break
    a += dp[i][j]
 
ans = j
for i in reversed(range(ii)):
    a = 0
    for k in range(-1, 2):
        if not (0 <= j + k < 10):
            continue
        if a + dp[i][j + k] >= kk:
            kk -= a
            j = j + k
            ans = ans * 10 + j
 
            break
        a += dp[i][j + k]
 
 
print(ans)
### BUGGY CODE ###

N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)
ans = 0
for a in range(N):
    for b in range(a + 1, N):
        for c in range(b + 1, N):
            if L[c] < L[b] + L[a]:
                if L[a] < L[b] + L[c] and L[b] < L[c] + L[a]:
                    ans += 1
            else:
                break
print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right
N = int(input())
L = list(map(int, input().split()))
L.sort()
ans = 0
for i in range(N-1, 1, -1):
    for j in range(i - 1, 0, -1):
        x = L[i] - L[j]
        bottom = bisect_right(L, x)
        if j > bottom:
            ans += j - bottom
print(ans)
### BUGGY CODE ###

x,k,d=map(int,input().split())
x=abs(x)
sa=x//d
ans=x
pbk,mbk=0,0
bk1,bk2,bk3=1,1,1
mansbk,pansbk=0,0
if sa>=k:
  ans=x-d*k
else:
  ans=x-d*sa
  k=k-sa
  for i in range(k):
    mansbk=abs(ans-d)
    pansbk=abs(ans+d)
    if mansbk!=pansbk:
      ans=min(mansbk,pansbk)
      if bk3!=1:
        bk1=min(mansbk,pansbk)
        bk2=max(mansbk,pansbk)
        ans=1 if (k-i)%2==1 else bk1
        break
      elif ans==1:
        bk3=max(mansbk,pansbk) 
      elif 2*x==d:
        ans=0 if (k-i)%2==1 else x
        break
    else:
      ans=0 if (k-i)%2==0 else d
      break
    pbk=max(mansbk,pansbk)
    mbk=min(mansbk,pansbk)
print(ans)

### FIXED CODE ###

x,k,d=map(int,input().split())
x=abs(x)
sa=x//d
ans=x
pbk,mbk=0,0
bk1,bk2,bk3=1,1,1
mansbk,pansbk=0,0
if sa>=k:
  ans=x-d*k
else:
  ans=x-d*sa
  k=k-sa
  for i in range(k):
    mansbk=abs(ans-d)
    pansbk=abs(ans+d)
    if mansbk!=pansbk:
      ans=min(mansbk,pansbk)
      if bk3!=1:
        bk1=min(mansbk,pansbk)
        bk2=max(mansbk,pansbk)
        ans=mbk if (k-i)%2==0 else bk1
        break
      else:
        bk3=max(mansbk,pansbk) 
    else:
      ans=0 if (k-i)%2==0 else d
      break
    pbk=max(mansbk,pansbk)
    mbk=min(mansbk,pansbk)
print(ans)
### BUGGY CODE ###

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


def solve(i, m): 
    if m == 0:
        return True
    elif i >= n:
        return False
    res = solve(i + 1, m) or solve(i + 1, m - A[i])
    return res
 
for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')

### FIXED CODE ###

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

table = [[-1 for i in range(max(M)+1)] for j in range(n)]

def solve(i, m):
    if m == 0:
        return True
    elif i >= n:
        return False
    elif table[i][m] != -1:
        return table[i][m]
    elif m - A[i] >= 0:
        res = solve(i + 1, m) or solve(i + 1, m - A[i])
        table[i][m] = res
        return res
    else:
        res = solve(i + 1, m)
        table[i][m] = res
        return res

for m in M:
    if solve(0, m):
        print('yes')
    else:
        print('no')
### BUGGY CODE ###


n,q = map(int, input().split())
s = input()
a = [0 for i in range(q)]
for k in range(q):
    i,j = map(int, input().split())
    a[k] = [i,j]
for nums in a:
    check = s[nums[0]-1:nums[1]]
    count = 0
    for i in range(len(check)-1):
        if check[i]+check[i+1] == "AC":
            count += 1
    print(count)

### FIXED CODE ###

def get_ac_count(S):
    buf = None
    temp = []
    count = 0
    for c in S:
        if c == "A":
            buf = "A"
        elif buf == "A" and c == "C":
            buf = None
            count += 1
        elif buf == "A":
            buf = None
        temp.append(count)
    return temp
N, Q = map(int, input().split())
S = input()
ac_count = get_ac_count(S)
for i in range(Q):
    l,r = map(int, input().split())
    print(ac_count[r-1]-ac_count[l-1])