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

from sys import stdout,stdin
def knapsack(C,n,wei,val,mat):
    if(C==0 or n==0):
        return 0
    else:
        if(C>=wei[n-1]):
            a=mat[C-wei[n-1]][n-1]
            b=mat[C][n-1]
            if(a==-1):
                a=knapsack(C-wei[n-1],n-1,wei,val,mat)
                mat[C-wei[n-1]][n-1]=a
            if(b==-1):
                b=knapsack(C,n-1,wei,val,mat)
                mat[C][n-1]=b
            mat[C][n]=max(a+val[n-1],b)
            return (max(a+val[n-1],b))
        else:
            alp=matrix[C][n-1]
            if(alp==-1):
                alp=knapsack(C,n-1,wei,val,mat)
                mat[C][n-1]=alp
                mat[C][n]=alp
            return(alp)
N,W=map(int,stdin.readline().split())
matrix=[[-1 for i in range(0,N+1)]for j in range(0,W+1)]
for i in range(0,len(matrix)):
    matrix[i][0]=0
for i in range(0,len(matrix[0])):
    matrix[0][i]=0
weights=[]
values=[]
for i in range(0,N):
    w,v=map(int,stdin.readline().split())
    weights.append(w)
    values.append(v)
knapsack(W,N,weights,values,matrix)
stdout.write(str(matrix[W][N]))

### FIXED CODE ###

from sys import stdin,stdout
N,W=map(int,stdin.readline().split())
matrix=[[-1 for i in range(0,W+1)]for j in range(0,N+1)]
for i in range(0,len(matrix)):
    matrix[i][0]=0
for i in range(0,len(matrix[0])):
    matrix[0][i]=0
weights=[]
values=[]
for i in range(0,N):
    w,v=map(int,stdin.readline().split())
    weights.append(w)
    values.append(v)
for item in range(1,N+1):
    for weight in range(1,W+1):
        if(weights[item-1]<=weight):
            matrix[item][weight]=max(values[item-1]+matrix[item-1][weight-weights[item-1]],matrix[item-1][weight])
        else:
            matrix[item][weight]=matrix[item-1][weight]
print(matrix[N][W])
### BUGGY CODE ###

N,K = map(int,input().split())
arr = []
a = abs(N-K)
if N%K==0: print (0)
else:
    while True:
        c = abs(N-K)
        if c > a: break
        a = c
        N = c
    print(a)

### FIXED CODE ###

N,K = map(int, input().split())
N = N%K
absolute = abs(K-N)
print(absolute if absolute < N else N)
### BUGGY CODE ###

#模範解答の通りにやってみる
N,K=map(int,input().split())
P=list(map(int,input().split()))
if K==1:
	print((max(P)+1)/2)
elif N==K:
	print((sum(P)+N)/2)
else:
	T=sum(P[0:(K)])
	for k in range(1,N-K+1):
		if T<=sum(P[k:k+K]):
			T=sum(P[k:k+K])
	print((T+K)/2)


### FIXED CODE ###

#模範解答の通りにやってみる
N,K=map(int,input().split())
P=list(map(int,input().split()))
if K==1:
	print((max(P)+1)/2)
elif N==K:
	print((sum(P)+N)/2)
else:
	T=sum(P[0:(K)])
	S=sum(P[0:(K)])
	for k in range(0,N-K):
		S=S-P[k]+P[k+K]
		if T<=S:
			T=S
		else:
			continue
	print((T+K)/2)
### BUGGY CODE ###

import fractions
def main():
  _=input()
  a=tuple(map(int,input().split()))
  a1=a[0]
  fgcd=fractions.gcd
  for i in a:
    a1=(i*a1)//fgcd(i,a1)
  x=[a1//i for i in a]
  print(sum(x)%(10**9+7))
  
if __name__ == '__main__':
    main()

### FIXED CODE ###

import fractions
from functools import reduce
def main():
  _=input()
  a=tuple(map(int,input().split()))
  fgcd=fractions.gcd
  def lcm_base(x, y):
    return (x * y) // fgcd(x, y)
  def lcm(numbers):
    return reduce(lcm_base, numbers, 1)
  q=lcm(a)
  x=[q//i for i in a]
  print(sum(x)%(10**9+7))
  
if __name__ == '__main__':
    main()
### BUGGY CODE ###

from bisect import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ret = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ret += bisect(L[j+1:],L[i]+L[j]-1)
print(ret)

### FIXED CODE ###

from bisect import bisect
N = int(input())
L = list(map(int, input().split()))
L.sort()
ret = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ret += bisect(L,L[i]+L[j]-1)-j-1
print(ret)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np
import sys
input = sys.stdin.readline


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

    SUM = sum(a)

    ans = list()
    for i in range(1, n):
        ans.append(abs(2 * sum(a[:i]) - SUM))

    print(min(ans))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import numpy as np
import sys
input = sys.stdin.readline


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

    SUM = sum(a)

    ans = list()
    left = a[0]
    for i in range(1, n):
        ans.append(abs(2 * left - SUM))
        left += a[i]

    print(min(ans))


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

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

height = list(map(int, input().split(' ')))
height_all = height

for i in range(M):
  a, b = map(int, input().split(' '))
  #print(a, b, height[a - 1], height[b - 1])
  
  if height[a - 1] == height[b - 1]:
    #print(i)
    height_all = [item for item in height_all if item is not height[a - 1]]
    #height_all = height_all[height_all != height[a - 1]]
    
  elif height[a - 1] > height[b - 1]:
    #print(i)
    height_all = [item for item in height_all if item is not height[b - 1]]
    #height_all = height_all[height_all != height[b - 1]]
    
  else:
    height_all = [item for item in height_all if item is not height[a - 1]]
    #height_all = height_all[height_all != height[a - 1]]
  
    
print(len(height_all))

### FIXED CODE ###

import numpy as np
N, M = map(int, input().split(' '))

height = np.array(list(map(int, input().split(' '))))
height_all = np.array(list(height))

for i in range(M):
  a, b = map(int, input().split(' '))
  #print(a, b, height[a - 1], height[b - 1])
  if height[a - 1] > height[b - 1]:
    height_all[b - 1] = 0
  
  elif height[a - 1] == height[b - 1]:
    height_all[a - 1] = 0
    height_all[b - 1] = 0
    
  else:
    height_all[a - 1] = 0
    
  #print(height_all)
  
print(len(np.nonzero(height_all)[0]))
### BUGGY CODE ###

N = int(input())
y = 10**18
x = 1

for i in map(int,input().split()):
    x *= i
if x > y:
    print("-1")
else:
    print(x)

### FIXED CODE ###

N = int(input())
l = list(map(int,input().split()))
l.sort()
ans = 1
rec = True
for i in range(N):
    ans = ans * l[i]
    if ans > 10**18:
        rec = False
        break

if rec:
    print(ans)
else:
    print('-1')
### BUGGY CODE ###

n = int(input())

nlll = {}
s = []
for i in range(1000000000):
    s.append(0)
    
for i in range(n):
    aaa = int(input())
    if s[aaa] == 0:
        s[aaa] = 1
    elif s[aaa] == 1:
        s[aaa] = 0
    else:
        None

sums = 0
for i in s:
    sums = sums + i
print(sums)

### FIXED CODE ###

n = int(input())

nlll = {}
    
for i in range(n):
    aaa = int(input())
    if aaa in nlll:
        del nlll[aaa]
    else:
        nlll.update({aaa:1})

sums = 0
for i in nlll.values():
    sums = sums + i
print(sums)
### BUGGY CODE ###

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[0]*h
for i in range(h):
  st=str(input())
  st=list(st)
  s[i]=st
  
from collections import deque
temp=[[999999]*w for i in range(h)]
temp[ch-1][cw-1]=0
queue = deque([[ch-1, cw-1]])
while queue:  
  x,y=queue.popleft()
  for i,j in [[1,0],[-1,0],[0,1],[0,-1],[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]:
    xtemp,ytemp=x+i,y+j
    if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
      continue
    if temp[xtemp][ytemp]<=temp[x][y]:
      continue
    if (i==1 and j==0) or (i==-1 and j==0) or (i==0 and j==1) or (i==0 and j==-1):
      temp[xtemp][ytemp]=min(temp[xtemp][ytemp],temp[x][y])
    else:
      temp[xtemp][ytemp]=min(temp[xtemp][ytemp],temp[x][y]+1)
    queue.append([xtemp,ytemp])
if temp[dh-1][dw-1]==999999:
  print(-1)
else:
  print(temp[dh-1][dw-1])

### FIXED CODE ###

h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[0]*h
for i in range(h):
  st=str(input())
  st=list(st)
  s[i]=st
  
from collections import deque
temp=[[999999]*w for i in range(h)]
temp[ch-1][cw-1]=0
queue0 = deque([[ch-1, cw-1, 0]])
queue1 = deque()
while queue0:  
  x,y,c=queue0.popleft()
  queue1.append((x,y,c))
  for i,j in [[1,0],[-1,0],[0,1],[0,-1]]:
    xtemp,ytemp=x+i,y+j
    if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
      continue
    if temp[xtemp][ytemp]<=c:
      continue
    temp[xtemp][ytemp]=c
    queue0.append([xtemp,ytemp,temp[xtemp][ytemp]])
    
  if len(queue0)==0:      
    while queue1:
      x,y,c=queue1.popleft()
      for i,j in [[2,2],[2,1],[2,0],[2,-1],[2,-2],[1,2],[1,1],[1,-1],[1,-2],[0,2],[0,-2],[-1,2],[-1,1],[-1,-1],[-1,-2],[-2,2],[-2,1],[-2,0],[-2,-1],[-2,-2]]:
        xtemp,ytemp=x+i,y+j
        if xtemp<0 or h<=xtemp or ytemp<0 or w<=ytemp or s[xtemp][ytemp]!=".":
          continue
        if temp[xtemp][ytemp]<=c+1:
          continue
        temp[xtemp][ytemp]=c+1
        queue0.append([xtemp,ytemp,temp[xtemp][ytemp]])
        
if temp[dh-1][dw-1]==999999:
  print(-1)
else:
  print(temp[dh-1][dw-1])
### BUGGY CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N)]
    if S[N-1] == '?':
        for m in range(10):
            dp[0][m] = 1
    else:
        tm = int(S[N-1])%13
        dp[0][tm] = 1
    for i in range(1,N):
        if S[N-1-i] == '?':
            for j in range(13):
                for k in range(10):
                    dp[i][j] =(dp[i][j] + dp[i-1][(j-(k*10**i)%13)%13]) % MOD
        else:
            m = (int(S[N-1-i])*10**i) % 13
            for l in range(13):
                dp[i][l] += dp[i-1][(l-m)%13]
    print(dp[N-1][5]%MOD)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    MOD = 7 + 10**9
    S = tuple(input())
    N = len(S)
    dp = [[0]*13 for _ in range(N+1)]
    dp[0][0] += 1
    s=[1]
    for n in range(1,N):
        s.append((s[n-1]*10)%13)
    for i in range(N):
        for k in range(13):
            if S[-(i+1)] != '?':
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] += dp[i][k] 
                dp[i+1][(k+int(S[-(i+1)])*s[i])%13] %= MOD
            else:
                for l in range(10):
                    dp[i+1][(k+l*s[i])%13] += dp[i][k]
                    dp[i+1][(k+l*s[i])%13] %= MOD
    print(dp[-1][5])

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

N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [min(i/2,(T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i in range(N):
    te += t[i]*2
    vi = v[i]
    vt = [min(vt[j],vi+max(0,-(j-ts)/2,(j-te)/2)) for j in range(T+1)]
    ts = te
print(sum(vt)/2)

### FIXED CODE ###

N = int(input())
t = list(map(int,input().split()))
v = list(map(int,input().split()))
T = sum(t)*2
vt = [min(i/2,(T-i)/2) for i in range(T+1)]
ts = 0
te = 0
for i in range(N):
    te += t[i]*2
    for j in range(T+1):
        vt[j] = min(vt[j],v[i]+max(0,-(j-ts)/2,(j-te)/2))
    ts = te
print(sum(vt)/2)
### BUGGY CODE ###

import sys
S = input().strip()

for i in range(2,len(S)+1):
    for j in range(0,len(S)+1-i):
        s = S[j:j+i]
        for k in set(s):
            if s.count(k)*2 > len(s):
                print(j+1,j+i)
                sys.exit(0)

print(-1,-1)


### FIXED CODE ###

import sys
S = input().strip()

for i in range(2,4):
    for j in range(0,len(S)+1-i):
        s = S[j:j+i]
        for k in set(s):
            if s.count(k)*2 > len(s):
                print(j+1,j+i)
                sys.exit(0)

print(-1,-1)
### BUGGY CODE ###

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
def solve(N, ga, gb, sa, sb, ba, bb):
    V = [gb, sb, bb]
    W = [ga, sa, ba]
    dp = [i for i in range(N+1)]
    for v, w in zip(V, W):
        if v <= w:
            continue
        for k in range(w, N+1):
            dp[k] = max(dp[k], dp[k-w] + v)
    return max(dp)

A = solve(N, ga, gb, sa, sb, ba, bb)
B = solve(A, gb, ga, sb, sa, bb, ba)
print(B)

### FIXED CODE ###

N = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())
def solve(N, P):
    V = []; W = []
    for w, v in P:
        if w < v:
            V.append(v); W.append(w)
    if len(V) == 1:
        v = V[0]; w = W[0]
        k = N // w
        return N - k*w + k*v
    if len(V) == 2:
        w1, w2 = W
        M = w1 * w2
        dp = [i for i in range(M+1)]
        for v, w in zip(V, W):
            if v <= w:
                continue
            for k in range(w, M+1):
                dp[k] = max(dp[k], dp[k-w] + v)
        for i in range(M):
            dp[i+1] = max(dp[i+1], dp[i])
        ans = 0
        for i in range(M):
            k, r = divmod(N, (i+1))
            ans = max(ans, dp[i+1] * k + dp[r])
        return ans
    dp = [i for i in range(N+1)]
    for v, w in zip(V, W):
        if v <= w:
            continue
        for k in range(w, N+1):
            dp[k] = max(dp[k], dp[k-w] + v)
    return max(dp)

A = solve(N, [[ga, gb], [sa, sb], [ba, bb]])
B = solve(A, [[gb, ga], [sb, sa], [bb, ba]])
print(B)
### BUGGY CODE ###

N = int(input())
S = []
ans = 0
ANS = {}
for i in range(N):
  si = input()
  new_str_list = sorted(si)
  s = "".join(new_str_list)
  if s in S:
    if s not in ANS:
      ANS[s] = 1
    else:
      ANS[s] += 1
    ans += ANS[s]
  else:
    S.append(s)
print(ans)

### FIXED CODE ###

N = int(input())
ans = 0
ANS = {}
for i in range(N):
  si = input()
  new_str_list = sorted(si)
  s = "".join(new_str_list)
  if s not in ANS.keys():
    ANS[s] = 1
  else:
    ANS[s] += 1
  ans += ANS[s]
      
print(ans-N)
### BUGGY CODE ###

from collections import defaultdict
N, Q = map(int, input().split())
S = input()
lr = [list(map(int, input().split())) for _ in range(Q)]
memo = defaultdict(int)
for i in range(1, N+1):
    memo[i] = S[:i].count('AC')
for l, r in lr:
    print(memo[r] - memo[l])


### FIXED CODE ###

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

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Feb 10 10:05:08 2019

@author: shinjisu
"""


# ARC 077 C
def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def dmp(x):
    global debug
    if debug:
        print(x)


def probC():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    b = []
    for i in range(N):
        b.append(A[i])
        b.reverse()
        dmp(b)
    return b


debug = False
for n in probC():
    print(n, end=' ', flush=True)


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Feb 10 10:05:08 2019

@author: shinjisu
"""


# ARC 077 C
def getInt(): return int(input())


def getIntList(): return [int(x) for x in input().split()]


def zeros(n): return [0]*n


def dmp(x):
    global debug
    if debug:
        print(x)


def probC_TLE():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    b = []
    for i in range(N):
        b.append(A[i])
        b.reverse()
        dmp(b)
    return b


def probC_TLE2():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    former, latter = [], []
    for i in range(-1, -N-1, -1):
        if i % 2 == 0:
            latter = [A[i]] + latter
        else:
            former.append(A[i])
        full = former + latter
        dmp((former, latter, full))
    return full


def probC_TLE3():
    N = getInt()
    A = [x for x in input().split()]
    dmp((N, A))
    former, latter = '', ''
    for i in range(-1, -N-1, -1):
        if i % 2 == 0:
            latter = A[i] + ' ' + latter
        else:
            former = former + ' ' + A[i]
        dmp((former, latter))
    return former[1:] + ' ' + latter


def probC():
    N = getInt()
    A = getIntList()
    dmp((N, A))
    b = zeros(N)
    for i in range(-1, -N-1, -1):
        if i % 2 == 0:
            b[i//2] = A[i]
        else:
            b[-i//2] = A[i]
        dmp(b)
    return b


debug = False
# print(probC())
for n in probC():
    print(n, end=' ', flush=True)
### BUGGY CODE ###

N = int(input())

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

d = 10**9+7
s = 0

for i in range(N):
  for j in range(i+1,N):
    s += A[i]*A[j] % d
    
print(s % d)

### FIXED CODE ###

from itertools import accumulate

N = int(input())

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

B = list(accumulate(A))

d = 10**9+7
s = 0

for i in range(N):
    s += (A[i]*(B[-1]-B[i])) % d
    
print(s % d)
### BUGGY CODE ###

# coding: utf-8
 
a,b=list(map(int,input().split()))
 
mouse_tot = a
mouse_cnt = 1
wa = a-1
 
while True:
    if mouse_tot == b:
        break
    elif mouse_tot < b:
        mouse_tot += wa
        mouse_cnt += 1
 
print(mouse_cnt)

### FIXED CODE ###

# coding: utf-8
 
a,b=list(map(int,input().split()))
 
mouse_tot = 1
mouse_cnt = 0
add_mouse = a-1
 
while mouse_tot <  b:
    mouse_tot += add_mouse
    mouse_cnt += 1
 
if b==0:
    mouse_cnt = 0
 
print(mouse_cnt)
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def group_count(self):
        temp = [(-self.parents[i])*(-self.parents[i]-1)//2 for i in range(len(self.parents)) if self.parents[i] < -1]
        a = sum(temp)
        if a == init:
            end = True
            return a
        else:
            return a
N,M = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
uf = UnionFind(N)
init = N*(N-1)//2
ans = []
temp = []
end = False
b = 0
for i in range(1, M+1):
    if b == init:
        ans.append(0)
    else:
        uf.union((AB[-i][0]-1), (AB[-i][1]-1))
        b = uf.group_count()
        ans.append(init-b)
for i in range(1, M):
    print(ans[-i-1])
print(init)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        a = self.parents[x]
        b = self.parents[y]
        self.parents[x] += self.parents[y]
        self.parents[y] = x
        return(a*b)
N,M = (int(x) for x in input().split())
AB = [list(map(int, input().split())) for _ in range(M)]
uf = UnionFind(N)
init = N*(N-1)//2
ans = []
temp = init
for i in range(1, M+1):
    temp -= uf.union((AB[-i][0]-1), (AB[-i][1]-1))
    ans.append(temp)
for i in range(1, M):
    print(ans[-i-1])
print(init)
### BUGGY CODE ###

N = int(input())
p_f = [0.0]
p_b = [0.0]
for p in list(map(float,input().split())):
    p_f.append(p)
    p_b.append(1.0-p)

#一次軸：コイントスの回数、二次軸：勝ち数、値：発生確率
dp = [[0.0] * (N+1) for i in range(N+1)]
dp[0][0] = 1.0

def cointoss(n_toss):
    global p_majority
    for i in range(n_toss):
        dp[n_toss][i+1] += dp[n_toss-1][i] * p_f[n_toss]
        dp[n_toss][i  ] += dp[n_toss-1][i] * p_b[n_toss]

for i in range(1,N+1):
    cointoss(i)

p_majority = 0.0
n_majority = N // 2 + 1

for i in range(n_majority,N+1):
    p_majority += dp[N][i]

print(p_majority)

### FIXED CODE ###

N = int(input())
p_f = [0.0]
p_b = [0.0]
for p in list(map(float,input().split())):
    p_f.append(p)
    p_b.append(1.0-p)

#一次軸：コイントスの回数、二次軸：勝ち数、値：発生確率
dp = [[0.0] * (N+1) for i in range(N+1)]
dp[0][0] = 1.0

def cointoss(n_toss):
    global p_majority
    for i in range(n_toss):
        dp[n_toss][i+1] += dp[n_toss-1][i] * p_f[n_toss]
        dp[n_toss][i  ] += dp[n_toss-1][i] * p_b[n_toss]

for i in range(1,N+1):
    cointoss(i)

p_majority = 0.0
n_majority = N // 2 + 1

for i in range(n_majority,N+1):
    p_majority += dp[N][i]

print(p_majority)
### BUGGY CODE ###

n,q = [int(i) for i in input().split()]
s = input()

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

### FIXED CODE ###

n,q = [int(i) for i in input().split()]
s = input()
cumsum = [0]*n
ans = 0
flag = False

for i in range(n):
    if flag:
        if s[i] == "C":
            ans += 1

    cumsum[i] = ans     

    flag = False

    if s[i] == "A":
        flag = True
    


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

input_str = input().split()
N = int(input_str[0])
Y = int(input_str[1])

x_quo = Y//10000

flag = False
for x in range(0,min([x_quo+1,N+1])):
  Y_x = Y - 10000*x
  N_x = N - x
  y_quo = Y_x // 5000
  for y in range(0,min([y_quo+1,N_x+1])):
    Y_xy = Y_x - 5000*y
    N_xy = N_x - y
    z_quo = Y_xy // 1000
    for z in range(0,min([z_quo+1,N_xy+1])):
      if 10000*x + 5000*y + 1000*z == Y and x+y+z == N:
        flag = True;
        break;
    else:
      continue
    break
  else:
    continue
  break

if flag == True:
  print(str(x) + " " + str(y) + " " + str(z))
else:
  print("-1 -1 -1")

### FIXED CODE ###

input_str = input().split()
N = int(input_str[0])
Y = int(input_str[1])

x_quo = Y//10000

flag = False
for x in range(min([x_quo,N]),-1,-1):
  Y_x = Y - 10000*x
  N_x = N - x
  y_quo = Y_x // 5000
  for y in range(min([y_quo,N_x]),-1,-1):
    z = N-x-y
    if 10000*x + 5000*y + 1000*z == Y and x+y+z == N:
      flag = True;
      break;
  else:
    continue
  break

if flag == True:
  print(str(x) + " " + str(y) + " " + str(z))
else:
  print("-1 -1 -1")
### BUGGY CODE ###

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
ans = list(map(lambda x: s.count(x)-1, set(s)))
ans = sum(list(map(lambda x: int(x*(x+1)/2), ans)))

print(ans)

### FIXED CODE ###

n = int(input())
s = [''.join(sorted(input())) for _ in range(n)]
t = {}

for i in range(n):
    if s[i] in t:
        t[s[i]] += 1
    else:
        t[s[i]] = 1
ans = sum((i * (i - 1)) // 2 for i in t.values())

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

n = int(input())
h = list(map(lambda x: int(x), input().split()))

max_len = 0

for i in range(n-2):
    j = i
    cur_len = 0
    while True:
        if j == n-1:
            break
        cur = h[j]
        next = h[j + 1]
        j += 1
        if cur >= next:
            cur_len += 1
        else:
            break

    max_len = max(max_len, cur_len)

print(max_len)


### FIXED CODE ###

n = int(input())
h = list(map(lambda x: int(x), input().split()))

d = []

for i in range(1, n):
    if h[i-1] >= h[i]:
        d.append(1)
    else:
        d.append(0)

max_len = 0
cur_len = 0

for i in range(len(d)):
    if d[i] == 0:
        cur_len = 0
    else:
        cur_len += 1
    max_len = max(max_len, cur_len)

print(max_len)
### BUGGY CODE ###

s=input()
x=[]
for i in range(len(s)):
    for j in range(1,len(s)):
        if s[i]=="A" and s[j]=="Z":
           x.append(int(j-i+1))
print(max(x))

### FIXED CODE ###

s = input()
print(s.rfind('Z') - s.find('A') + 1)