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

r,g,b,n = map(int,input().split())
cnt = 0
for i in range(0,n+1,r):
    for j in  range(0,n+1,g):
        ch = (n- i - j)/b
        if ch.is_integer() == True and ch >= 0:
            cnt += 1
print(cnt)

### FIXED CODE ###

r,g,b,n = map(int,input().split())
cnt = 0
for i in range(0,n+1,r):
    for j in range(0,n+1-i,g):
        if (n - i - j)%b == 0 and (n - i - j)%b >= 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

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

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

### FIXED CODE ###

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

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

s = list(input())
r = 0

def rec(a, b, s):
    global r
    if len(s) == 0:
        return [a] + [b]
    if a == '0' and b == '0':
        b = '1'
        r += 1
    elif a == '1' and b == '1':
        b = '0'
        r += 1
    return [a] + [b] + rec(b, s[0], s[1:])

if len(s) == 1:
    print(0)
else:
    rec(s[0], s[1], s[2:])
    print(r)

### FIXED CODE ###

S = input()
n = len(S)
s = int(S, 2)
b = ''.join(map(str, [i % 2 for i in range(n)]))
p = int(b, 2)
q = int(b[1:] + str(int(b[-1]) ^ 1), 2)
print(min(bin(s ^ n).count('1') for n in [p, q]))
### BUGGY CODE ###

S = str(input())
S = S.replace("BC","D")
ans = 0
while S.count("AD") > 0:
  ans += S.count("AD")
  S = S.replace("AD","DA")

print(ans)

### FIXED CODE ###

S = str(input())
S = S.replace("BC","D")
A_count = 0
ans = 0

for i in range(len(S)):
  if S[i] == 'A':
    A_count += 1
  elif S[i] == 'D':
    ans += A_count
  else:
    A_count = 0
print(ans)
### BUGGY CODE ###

from collections import deque
r, c = list(map(int, input().split()))
sy, sx = [0, 0]
gy, gx = [r-1, c-1]

s = [list(map(str, list(input()))) for i in range(r)]

N = r*c
G = [[] for _ in range(N)]
for i in range(r):
    for j in range(c):

        for x, y in ([0, 1], [0, -1], [1, 0], [-1, 0]):
            if 0 <= i+y <= r-1 and 0 <= j+x <= c-1:
                G[i*c+j].append((i+y)*c+j+x)


# G[v]: 頂点vに隣接する頂点list
# N: 頂点数
# print(G)
dist = [-1]*N
que = deque()
for i in range(r):
    for j in range(c):
        if s[i][j] == '#':
            que.append(i*c+j)
            dist[i*c+j] = 0

while que:
    v = que.popleft()
    d = dist[v]
    for w in G[v]:
        if dist[w] > -1:
            continue
        dist[w] = d + 1
        que.append(w)

ans = max(dist)
print(ans)


### FIXED CODE ###

# import numpy as np
# import scipy as sp
# print(a,b,c,sep="") # 半角スペースなしで出力(abc)
# n=int(input())  #数値入力 「N」だけの入力のとき
# a,b=map(int, input().split())  #複数数値入力　「A B」みたいなスペース空いた入力のとき
# c=list(map(int, input().split()))  #リスト入力 「a1 a2 a3 ...」みたいな配列のような入力のとき
# s=[list(map(int,list(input()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき
# import sys ; sys.exit() # プログラム終了
# from copy import deepcopy ; b=deepcopy(a)
# chr(ord('a') + 1)
# s.sort(key=lambda x: x[1], reverse=False) # 2番目の要素で昇順にソート（Trueなら降順）
#
from copy import deepcopy
from collections import deque

d = deque()
h, w = map(int, input().split())
s = [list(map(str, list(input()))) for i in range(h)]
used = [[True for j in range(w)] for i in range(h)]
# used = [[True]*w]*h
for i in range(h):
    for j in range(w):
        if (s[i][j] == "#"):
            d.append([i, j])
            used[i][j] = False


ans = -1
while (d):

    tmp = deque()
    while(d):
        i, j = d.popleft()

        if i+1 < h and used[i+1][j]:
            s[i+1][j] = "#"
            tmp.append([i+1, j])
            used[i+1][j] = False

        if i-1 >= 0 and used[i-1][j]:
            s[i-1][j] = "#"
            tmp.append([i-1, j])
            used[i-1][j] = False

        if j+1 < w and used[i][j+1]:
            s[i][j+1] = "#"
            tmp.append([i, j+1])
            used[i][j+1] = False

        if j-1 >= 0 and used[i][j-1]:
            s[i][j-1] = "#"
            tmp.append([i, j-1])
            used[i][j-1] = False

    d = tmp
    ans += 1

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

s = list(input())
n = int(input())

point = 0
for i in range(n):
  q = input().split()
  if q.pop(0)=='1':
    point = (point+1)%2
  else:
    _q = int(q.pop(0))-1
    if (point+_q)%2 == 0:
      s.insert(0,q.pop(0))
    else:
      s.append(q.pop(0))
      
if point == 1:
  s.reverse()

print(''.join(s))

### FIXED CODE ###

from collections import deque

s = deque(input())
n = int(input())

point = 0
for i in range(n):
  q = input().split()
  if q.pop(0)=='1':
    point = (point+1)%2
  else:
    _q = int(q.pop(0))-1
    if (point+_q)%2 == 0:
      s.appendleft(q.pop(0))
    else:
      s.append(q.pop(0))

if point == 1:
  s.reverse()

print(''.join(s))
### BUGGY CODE ###

import heapq
import sys
def solve():
    input = sys.stdin.readline

    N, M = map(int, input().rstrip('\n').split())
    A = list(map(int, input().rstrip('\n').split()))
    BC = []
    for i in range(M):
        tmp = list(map(int, input().rstrip('\n').split()))
        BC.append(tmp)
    BC.sort(reverse=True, key=lambda x: x[1])
        
    heapq.heapify(A)
    for i in range(M):
        for j in range(BC[i][0]):
            p = heapq.heappop(A)
            if BC[i][1] < p:
                heapq.heappush(A,p)
                break
            else:
                heapq.heappush(A, BC[i][1])
    
    print(sum(A))


if __name__ == '__main__':
    solve()


### FIXED CODE ###

def solve():
    N, M = map(int,input().split())
    A = list(map(int,input().split()))
    A.sort()
    operate = []
    for _ in range(M):
        b, c = map(int,input().split())
        operate.append([b,c])
    operate.sort(reverse=True, key=lambda x:x[1])    

    rewrite = [0] * N
    idx = 0
    for b,c in operate:
        for i in range(b):
            rewrite[idx] = c
            idx += 1
            if idx == N:
                break
        if idx == N:
            break
    
    ans = 0
    for i in range(N):
        ans += max(A[i],rewrite[i])
    
    print(ans)

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

import itertools,sys,collections,math,random,fractions,bisect;sys.setrecursionlimit(10**7)
sr = sys.stdin.readline; P = print; P2 = lambda x: print(*x, sep="\n")
def I(i=0): t = [int(x)-i for x in sr().split()];return t
def S(): t = sr().split(); return t if len(t) > 1 else t[0]
L1,L2,L3,L4, = [],[],[],[]

N, = I()
A = I()
d = dict()
def dd(a,b):
    if (a,b) in d:
        return d((a,b))
    else:
        return len(list(itertools.combinations(range(a),b)))
c = collections.Counter(A) 
total = 0
for e in c.items():
    total += dd(e[1],2)
for e in A:
    print(total -  dd(c[e],2) + dd(c[e]-1,2))


### FIXED CODE ###

import itertools,sys,collections,math,random,fractions,bisect;sys.setrecursionlimit(10**7)
sr = sys.stdin.readline; P = print; P2 = lambda x: print(*x, sep="\n")
def I(i=0): t = [int(x)-i for x in sr().split()];return t
def S(): t = sr().split(); return t if len(t) > 1 else t[0]
L1,L2,L3,L4, = [],[],[],[]

N, = I()
A = I()
d = dict()
def dd(n):
    if n in d:
        return d[n]
    else:
        if n < 2:
            return 0
        else:
            d[n] = math.factorial(n) // (math.factorial(n - 2) * math.factorial(2))
            return d[n]
c = collections.Counter(A)
total = 0
for e in c.items():
    total += dd(e[1])
for e in A:
    print(total -  dd(c[e]) + dd(c[e]-1))
### BUGGY CODE ###

# -*- coding: utf-8 -*-

n = int(input())
s = list(input())

needs = [n]
cnt = 0
for i in range(n):
    if s[i] == "#":
        need = 0
        cnt += 1
        for j in range(i,n):
            if s[j] == ".":
                need += 1
        needs.append(need + cnt - 1)
need = min(needs)

black = 0
for i in range(n):
    if s[i] == "#":
        black += 1

print(min(black,need))

### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(input())
s = list(input())

a = [0] * n

cnt = 0
for i in range(n-1,-1,-1):
    if s[i] == ".":
        cnt += 1
    a[i] = cnt

needs = [n]
cnt = 0
for i in range(n):
    if s[i] == "#":
        need = 0
        cnt += 1
        need += a[i]
        needs.append(need + cnt - 1)
need = min(needs)

black = 0
for i in range(n):
    if s[i] == "#":
        black += 1

print(min(black,need))
### BUGGY CODE ###

k = int(input())
s = input()
MOD = 10**9+7

FAC = [1]
INV = [1]
for i in range(1,len(s)+k+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

ans = 0
for i in range(len(s),len(s)+k+1):
  ans += nCr(i-1,len(s)-1)*pow(25,i-len(s),MOD)*pow(26,len(s)+k-i,MOD)
  ans %= MOD
print(ans)

### FIXED CODE ###

k = int(input())
s = input()
MOD = 10**9+7

FAC = [1]
INV = [1]
for i in range(1,len(s)+k+1):
  FAC.append((FAC[i-1]*i) % MOD)
  INV.append(pow(FAC[-1],MOD-2,MOD))

def nCr(n,r):
  return FAC[n]*INV[n-r]*INV[r]

p25 = [1]
for i in range(len(s)+k):
  p25.append((p25[-1]*25)%MOD)
p26 = [1]
for i in range(len(s)+k):
  p26.append((p26[-1]*26)%MOD)

ans = 0
for i in range(len(s),len(s)+k+1):
  tmp = nCr(i-1,len(s)-1)*p25[i-len(s)]
  tmp %= MOD
  tmp *= p26[len(s)+k-i]
  tmp %= MOD
  ans +=tmp
  ans %= MOD
print(ans)
### BUGGY CODE ###

# coding: utf-8
n = int(input())
lst = [input() for i in range(n)]
cnt = 0
for j in range(n - 1):
    for k in range(j + 1, n):
        if sorted(list(lst[j])) == sorted(list(lst[k])):
            cnt += 1

print(cnt)


### FIXED CODE ###

# coding: utf-8
from collections import Counter
n = int(input())
lst = [input() for i in range(n)]
cnt = Counter()
ans = 0
for i in lst:
    a = ''.join(sorted(list(i)))
    if a in cnt:
        ans += cnt[a]
    cnt[a] += 1

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

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    AB = []
    for i in range(X):
        for j in range(Y):
            AB.append(A[i] + B[j])
    AB.sort(reverse=True)

    res = []
    for i in range(min(K, len(AB))):
        for j in range(Z):
            res.append(AB[i] + C[j])
    res.sort(reverse=True)

    for i in range(K):
        print(res[i])


if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    X, Y, Z, K = map(int, input().split())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    AB = []
    for i in range(X):
        for j in range(Y):
            AB.append(A[i] + B[j])
    AB.sort(reverse=True)

    res = []
    for i in range(min(K, len(AB))):
        for j in range(Z):
            res.append(AB[i] + C[j])
    res.sort(reverse=True)

    for i in range(K):
        print(res[i])


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

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, q = read_line(int, int)
s, = read_line(str)

p = []
i = 0
while i < len(s) - 1:
    if s[i:i+2] == 'AC':
        p.append(i)
        i += 2
    else:
        i += 1

for i in range(q):
    l, r = read_line(int, int)
    l, r = l - 1, r - 1


    c = len(p)
    for j in range(len(p)):
        if not l <= p[j]:
            c -= 1
        if not (p[-j] + 1) <= r:
            c -= 1
        if j >= len(p) - j:
            break

    print(c)


### FIXED CODE ###

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, q = read_line(int, int)
s, = read_line(str)

m = [0 for _ in range(len(s) + 1)]

c = 0
for i in range(len(s)):
    if s[i:i+2] == 'AC':
        c += 1
    m[i + 1] = c

for i in range(q):
    l, r = read_line(int, int)

    if c == 0:
        print(0)
        continue
    print(m[r - 1] - m[l - 1])
### BUGGY CODE ###

M=10**9+7
n=int(input())
l=list(map(int,input().split()))
a=0
for i in range(60):
  t=sum((l[j]>>i)%2 for j in range(n))
  a+=(t*(n-t)<<i)%M
print(a%M)

### FIXED CODE ###

M=10**9+7
n=int(input())
l=list(map(int,input().split()))
a=0
for i in range(60):
  t=sum((l[j]>>i)%2 for j in range(n))
  a+=(t*(n-t)<<i)%M
print(a%M)
### BUGGY CODE ###

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

cad_sum = 0
cad_sum_ori = 0
for i in range(n-k+1):
    cad_p_list = p_list[i:i+k]

    if sum(cad_p_list) < cad_sum_ori:
        continue

    cad_sum_child_list = []
    for cad_p in cad_p_list:
        cad_sum_child = (cad_p+1)/2
        cad_sum_child_list.append(cad_sum_child)

    cad_sum_child = sum(cad_sum_child_list)
    if  cad_sum_child > cad_sum:
        cad_sum = cad_sum_child
        cad_sum_ori = sum(cad_p_list)
        
print(cad_sum)

### FIXED CODE ###

n, k = map(int, input().split())
p_list = list(map(lambda x: (float(x) + 1) / 2, input().split()))

S_i = [0]
for i in range(n):
    S_i.append(S_i[i] + p_list[i])    

# print(S_i)
result_max = 0
for j in range(k, n+1):
    cad_max = S_i[j] - S_i[j-k]
    result_max = max(cad_max, result_max)

print(result_max)
### BUGGY CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    S = SS()

    len_S = len(S)
    dp = [[0] * 13 for _ in range(len_S + 1)]
    dp[0][0] = 1

    for i in range(len_S):
        S_i = S[i]
        for j in range(13):
            if S_i == '?':
                for k in range(10):
                    dp[i+1][(j*10+k)%13] += dp[i][j]
                    dp[i+1][(j*10+k)%13] %= MOD
            else:
                dp[i+1][(j*10+int(S_i))%13] += dp[i][j]
                dp[i+1][(j*10+int(S_i))%13] %= MOD

    # for i in dp:
    #     print(i)
    print(dp[-1][5])

if __name__ == '__main__':
    resolve()


### FIXED CODE ###

import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda: sys.stdin.readline().rstrip() 
sys.setrecursionlimit(10**7)
INF = float('inf')
MOD = 10 ** 9 + 7
def I(): return int(input())
def F(): return float(input())
def SS(): return input()
def LI(): return [int(x) for x in input().split()]
def LI_(): return [int(x)-1 for x in input().split()]
def LF(): return [float(x) for x in input().split()]
def LSS(): return input().split()

def resolve():
    S = SS()

    len_S = len(S)
    dp = [[0] * 13 for _ in range(len_S + 1)]
    dp[0][0] = 1

    for i in range(len_S):
        S_i = S[i]
        for j in range(13):
            if S_i == '?':
                for k in range(10):
                    dp[i+1][(j*10+k)%13] += dp[i][j]
                    dp[i+1][(j*10+k)%13] %= MOD
            else:
                dp[i+1][(j*10+int(S_i))%13] += dp[i][j]
                dp[i+1][(j*10+int(S_i))%13] %= MOD

    # for i in dp:
    #     print(i)
    print(dp[-1][5])

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

from collections import Counter

N = int(input())

s = []
for i in range(N):
    c = Counter(input())
    s.append(sorted(list(c.items()))) 

result = 0
for elm in s:
    result += s.count(elm) - 1

print(int(result/2))


### FIXED CODE ###

N = int(input())

s = ["".join(sorted(input())) for i in range(N)]

count = 0
d = {}
for elm in s:
    if elm in d:
        count += d[elm]
        d[elm] += 1
    else:
        d[elm] = 1

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

MOD = 998244353

N, S = map(int, input().split(' '))
A = (0, *map(int, input().split(' ')))

dp = []
for _ in range(N + 1):
    dp.append([0] * (S + 1))

dp[0][0] = 1

for i in range(1, N + 1):
    a = A[i]
    for j in range(S + 1):
        dp[i][j] = 2 * dp[i - 1][j] % MOD
        if j >= a:
            dp[i][j] += dp[i - 1][j - a]
            dp[i][j] %= MOD

print(dp[N][S])


### FIXED CODE ###

import numpy as np

MOD = 998244353

N, S = map(int, input().split(' '))
A = (0, *map(int, input().split(' ')))

dp = np.zeros(shape=(N + 1, S + 1), dtype=int)
dp[0][0] = 1

for i in range(1, N + 1):
    a = A[i]
    dp[i] = 2 * dp[i - 1] % MOD
    dp[i][a:] += dp[i - 1][:-a]
    dp[i] %= MOD

print(dp[N][S])
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
    s.append(input())
res = 0
for index, j in enumerate(s):
    for k in s[index + 1:]:
        for l in j:
            k = k.replace(l, "", 1)
        if not k:
            res += 1

print(res)

### FIXED CODE ###

n = int(input())
dic = {}
res = 0
for i in range(n):
    s = ''.join(sorted(input()))
    if s in dic.keys():
        res += dic[s]
        dic[s] += 1
    else:
        dic[s] = 1
print(res)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    X = [list(map(int,input().split())) for _ in range(N-1)]
    Q,K = map(int,input().split())
    Y = [list(map(int,input().split())) for _ in range(Q)]

    tree = [[] for _ in range(N)]
    dif = [10**15 for _ in range(N)]
    dif[K-1] = 0
    for i in range(N-1):
        tree[X[i][0]-1].append(X[i][1])
        tree[X[i][1]-1].append(X[i][0])

    queue = [K]
    while queue:
        a = queue.pop()
        for i in range(N-1):
            if X[i][0] == a:
                dif[X[i][1]-1] = min(dif[X[i][1]-1],dif[a-1]+X[i][2])
                tree[X[i][1]-1].remove(a)
                queue[0:0] = tree[a-1]
            if X[i][1] == a:
                dif[X[i][0]-1] = min(dif[X[i][0]-1],dif[a-1]+X[i][2])
                tree[X[i][0]-1].remove(a)
                queue[0:0] = tree[a-1]
        queue = list(set(queue))

    for i in range(Q):
        print(dif[Y[i][0]-1]+dif[Y[i][1]-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    X = [list(map(int,input().split())) for _ in range(N-1)]
    Q,K = map(int,input().split())
    Y = [list(map(int,input().split())) for _ in range(Q)]

    tree = [[] for _ in range(N)]
    dif = [10**15 for _ in range(N)]
    dif[K-1] = 0
    for i in range(N-1):
        tree[X[i][0]-1].append((X[i][1]-1,X[i][2]))
        tree[X[i][1]-1].append((X[i][0]-1,X[i][2]))

    queue = [K-1]
    while queue:
        a = queue.pop()
        for i in tree[a]:
            s,t = i[0],i[1]
            if dif[s] == 10**15:
                dif[s] = dif[a]+t
                queue.append(s)

    for i in range(Q):
        print(dif[Y[i][0]-1]+dif[Y[i][1]-1])

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

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
from collections import Counter,defaultdict,deque
from itertools import permutations, combinations
from heapq import heappop, heappush
# input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

def main():
    h,w = inpm()
    c = [list(input()) for _ in range(h)]
    ans = 0
    for j in range(w-1):
        w = [[0 for _ in range(h+1)] for _ in range(h+1)]
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    for z in range(h-max(x,y)):
                        if c[x+z][j] == c[y+z][j+1]:
                            w[y][x] += 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    continue
                else:
                    if c[h-x][j] == c[h-y][j+1]:
                        w[x][y] = w[x-1][y-1]-1
                    else:
                        w[x][y] = w[x-1][y-1]
        dp = [[10**10 for _ in range(h+1)] for _ in range(h+1)]
        dp[0][0] = 0
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 and y == 0:
                    continue
                if x == 0:
                    dp[x][y] = dp[x][y-1]+w[x][y-1]
                elif y == 0:
                    dp[x][y] = dp[x-1][y]+w[x-1][y]
                else:
                    dp[x][y] = min(dp[x][y-1]+w[x][y-1],dp[x-1][y]+w[x-1][y])
        ans += dp[h][h]
    print(ans)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
    h,W = map(int,input().split())
    c = [tuple(input()) for _ in range(h)]
    c = tuple(c)
    ans = 0
    w = [0 for _ in range((h+1)**2)]
    dp = [0 for _ in range((h+1)**2)]
    for j in range(W-1):
        for x in range(h,0,-1):
            for y in range(h,0,-1):
                w[(x-1)*(h+1)+y-1] = w[x*(h+1)+y]
                if c[h-x][j] == c[h-y][j+1]:
                    w[(x-1)*(h+1)+y-1] += 1
        for x in range(h+1):
            for y in range(h+1):
                if x == 0 or y == 0:
                    if x == y:
                        dp[x*h+y] = 0
                    elif x == 0:
                        dp[x*(h+1)+y] = dp[x*(h+1)+y-1]+w[x*(h+1)+y-1]
                    else:
                        dp[x*(h+1)+y] = dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y]
                    continue
                dp[x*(h+1)+y] = min(dp[x*(h+1)+y-1]+w[x*(h+1)+y-1],dp[(x-1)*(h+1)+y]+w[(x-1)*(h+1)+y])
        ans += dp[-1]
    print(ans)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

#N
import copy
from collections import defaultdict
dd = defaultdict(int)

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

def rep(L):
    if len(L)==1:
        return 0
    S='-'.join(map(str, L))
    if dd[S]!=0:
        return dd[S]
    temp=10**15
    for i in range(len(L)-1):
        LL=copy.deepcopy(L)
        LL[i]+=LL[i+1]
        LL.pop(i+1)
        temp=min(temp,rep(LL)+L[i]+L[i+1])
    dd[S]=temp
    return temp
        
rep(a)
S='-'.join(map(str, a))
print(dd[S])





### FIXED CODE ###

#N

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

S=[0]*(N+1)
for i in range(N):
    S[i+1]=S[i]+a[i]


#dp[i][j]は[i,j)の範囲で全てをマージする最小コスト
inf=10**15
dp=[[inf]*(N+1) for _ in range(N+1)]

#区間[i,j)を[i,k)+[k,j)に分けて考える
for d in range(1,N+1):#dはj-i
    for i in range(N+1):
        j=i+d
        if j>N:
            break
        if d==1:
            dp[i][j]=0
        else:
            for k in range(i,j):
                dp[i][j]=min(dp[i][j] , dp[i][k]+dp[k][j]+S[j]-S[i])
            
print(dp[0][-1])
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for _ in range(q)]

ac = [1 if s[i]=='A' and s[i+1]=='C' else 0 for i in range(n-1)]
    
for l,r in lr:
  print(sum(ac[l-1:r-1]))

### FIXED CODE ###

n,q = map(int,input().split())
s = input()
lr = [list(map(int,input().split())) for _ in range(q)]

ac = [0]*(n+1)

for i in range(1,n+1):
  if s[i-1:i+2-1]=='AC':  
    ac[i]=ac[i-1] + 1
  else:
    ac[i]=ac[i-1]
    
for l,r in lr:
  print(ac[r-1]-ac[l-1])