Harryxun/stf_run huggingface dataset:
from sys import stdin, gettrace
import sys
 
if not gettrace():
    def input():
        return next(stdin)[:-1]
 
 
# def input():
#    return stdin.buffer.readline()

def maxcost(li,n,i,strt,dp):  
  if i==(n-1):
    return li[i][strt]
  mx=-sys.maxsize
  for l in range(3):
    if l!=strt:
      if dp[i+1][l]==-1:
        cost=maxcost(li,n,i+1,l,dp)
        dp[i+1][l]=cost
      else:
        cost=dp[i+1][l]
      mx=max(mx,cost+li[i][strt])
  return mx

def main():
  n=int(input())
  li=[]
  for i in range(n):
    temp=[int(x) for x in input().split()]
  li.append(temp)
  dp=[[-1 for j in range(3)] for i in range(n)]
  print(max(maxcost(li,n,0,0,dp),maxcost(li,n,0,1,dp),maxcost(li,n,0,2,dp)))
 
 
if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
def maxcost(li,n,i,strt,dp):
    if i==(n-1):
        return li[i][strt]
    mx=-sys.maxsize
    for l in range(3):
        if l!=strt:
            if dp[i+1][l]==-1:
                cost=maxcost(li,n,i+1,l,dp)
                dp[i+1][l]=cost
            else:
                cost=dp[i+1][l]
            mx=max(mx,cost+li[i][strt])
    return mx


n=int(input())
li=[]
for i in range(n):
    temp=[int(x) for x in input().split()]
    li.append(temp)
dp=[[-1 for j in range(3)] for i in range(n)]
print(max(maxcost(li,n,0,0,dp),maxcost(li,n,0,1,dp),maxcost(li,n,0,2,dp)))
m = int(input())
number_list = list(map(int,input().split()))
n = 0
while 1:
    f = False
    for i in range(0,m):
        if number_list[i] % 2 != 0:
            f = True
    if f == True:
        break
    for i in range(0,m):
        number_list[i] = number_list[i] / 2
    n += 1
print(n)

### FIXED CODE ###

s = input()
n = 0
for a in s:
    if a == '1':
        n += 1
print(n)
x,t=map(int.input())
print(x-t)

### FIXED CODE ###

x,t=map(int,input().split())
print(x-t if x >= t else 0)
# a, b = map(int, input().split())
a = input()
b = input()

if b is 'H':
  print('H') if a is 'H' else print('D')
else:
  print('D') if a is 'H' else print('H')

### FIXED CODE ###

a, b = input().split()
print('H') if a == b else print('D')
import sys
import math

for line in sys.stdin.readline():
    g = float(line.rstrip())
    ans = math.ceil(n/2)
    print(ans,end="")
    break

### FIXED CODE ###

import sys
import math

for line in sys.stdin.readlines():
    n = float(line)
    ans = math.ceil(n / 2)
    print(ans, end="")
    break
n = int(input())
A = list(map(int,input().split()))
ans = 0
for i in range(n):
  cnt = 0
  if A[i]%2:
    break
  else:
    A[i] = A[i]/2
    cnt +=1
  if cnt ==n
  ans +=1
print(ans)
    
  

### FIXED CODE ###

n = int(input())
A = list(map(int,input().split()))
ans = 0
cnt = 0
for j in range(31):
  cnt = 0
  for i in range(n):  
    if A[i]%2:
      break
    else:
      A[i] = A[i]/2
      cnt +=1
    if cnt ==n:
      ans +=1
print(ans)
x, a = input()

if x >= a:
  print(10)
elif x < a:
  print(0)
else:
  pass

### FIXED CODE ###

x, a = map(int,input().split())

if x >= a:
  print(10)
elif x < a:
  print(0)
else:
  pass
#include <stdio.h>

int abs(int j)
{
    return (j>0) ? j : -j;
}

int main()
{
    int N, M, i, j;
    int a[50], b[50], c[50], d[50],;
    int p[50] = {0};

    scanf("%d %d", &N, &M);
    
    for(i=0; i<N; i++)
    {
         scanf("%d %d", &a[i], &b[i]);
    }
    
    for(j=0; j<M; j++)
    {
         scanf("%d %d", &c[j], &d[j]);
    }
    
    for(i=0; i<N; i++)
    {
         for(j=0; j<M; j++)
         {
             if(abs(a[i] - c[j]) + abs(b[i] - d[j]) < abs(a[i] - c[p[i]]) + abs(b[i] - d[p[i]])
             {
                 p[i] = j;
             }
         }
         printf("%d\n", p[i]);
    }
}

### FIXED CODE ###

L = [int(i) for i in input().split(' ')]
print((L[0] + L[1]) % 24)
A, B, C = input()

if B+C <= 20
print(0)

else B+C > 20
print(C-A+B)

### FIXED CODE ###

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

answer = C-A+B

if answer >= 0:
	print(answer)

else :
	print(0)
from sys import stdin
import heapq
inf = 10**10
h,w = [int(x) for x in stdin.readline().rstrip().split()]
point = 0
li = [["#" for i in range(w)]for j in range(h)]
for i in range(h):
    s = stdin.readline().rstrip()
    for j in range(w):
        if s[j] == ".":
            point += 1
        li[i][j] = s[j]

def dijkstra(start, W):
    distance_list = [inf] * len(W)
    distance_list[start] = 0
    done_list = []
    wait_heap = []
    for i, d in enumerate(distance_list):
        heapq.heappush(wait_heap, (d, i))
    while wait_heap:
        p = heapq.heappop(wait_heap)
        i = p[1]
        if i in done_list:
            continue
        done_list.append(i)
        for j, x in enumerate(W[i]):
            if x != 0 and j not in done_list:
                d = min(distance_list[j], distance_list[i]+x)
                distance_list[j] = d
                heapq.heappush(wait_heap, (d, j))
    return distance_list

a = [[0 for i in range(w)]for j in range(h)]
for i in range(h):
    for j in range(w):
        a[i][j] = i*w + j

lin = [[0 for i in range(h*w)]for j in range(h*w)]

for i in range(h):
    for j in range(w-1):
        if li[i][j] == "." and li[i][j+1] == ".":
            lin[a[i][j]][a[i][j+1]] = 1
            lin[a[i][j+1]][a[i][j]] = 1

for i in range(h-1):
    for j in range(w):
        if li[i][j] == "." and li[i+1][j] == ".":
            lin[a[i][j]][a[i+1][j]] = 1
            lin[a[i][j]][a[i+1][j]] = 1

lis = dijkstra(0,lin)
if lis[h*w-1] == inf:
    print(-1)
    exit()

print(point-lis[-1]-1)

### FIXED CODE ###

from sys import stdin
from itertools import combinations

n = int(stdin.readline().rstrip())
a = int(stdin.readline().rstrip())

if a >= n:
    print("Yes")

else:
    if n%500 <= a:
        print("Yes")
    else:
        print("No")
A,B = int(input())
if(A%B == 0):
    print(B/A)
else:
    print(B//A+1)

### FIXED CODE ###

import math
A,B = map(int,input().split())
print(math.ceil((B-1)/(A-1)))
import heapq
n = int(input())
a = list(map(int, input().split))
a.sort(reverse=True)

ans = 0
heap = []
heapq.heappush(heap, -a[0])
for i in range(1, n):
    tmp = heapq.heappop(heap)
    tmp *= -1
    ans += tmp
    heapq.heappush(heap, -a[i])
    heapq.heappush(heap, -a[i])
print(ans)

### FIXED CODE ###

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

a.sort(reverse=True)

ans = a[0]
cnt = 1
index = 1
while cnt < n - 1:
    ans += 2 * a[index]
    index += 1
    cnt += 2
    
if cnt == n - 1:
    print(ans)
else:
    print(ans - a[index - 1])
text_list = input().split()
n = 0
a = int(text_list[0])
b = int(text_list[0]) + int(text_list[1])
c = int(text_list[0]) + int(text_list[1]) + int(text_list[2])
for i in range(int(text_list[3])):
    if i a:
        n += 1
    elif i b:
        continue
    elif i c:
        n -= 1

print(n)

### FIXED CODE ###

a, b, c, d = map(int, input().split())
if d <= a:
  print(d)
elif d <= a + b:
  print(a)
else:
  print(a-(d-(a+b)))
"\C-n":history-search-forward
"\C-p":history-search-backward

### FIXED CODE ###

a,b = map(int, raw_input().split())
print max(a+b,a-b,a*b)
N = int(input())
L = int(input())

aji = [(i+1)+L-1 for i in range(N)]
min = min(list(map(aji, abs)))
print(sum(aji)-min)

### FIXED CODE ###

N,L = input().split()

aji = [(i+1)+int(L)-1 for i in range(int(N))]
abs = list(map(abs, aji))
index = abs.index(min(abs))

print(sum(aji)-aji[index])
x = input("")
x2 = x.split()
result = x2[0] * x2[1]
result2= x2[0]*2 + x2[1]*2
print(result,result2)

### FIXED CODE ###

a, b =map(int, input().split())
print(a*b,2*(a+b))
def knapsack(nums, KLeap):
    n = len(nums)
    if n == 0 or n == 1:
        return 0
 
    if n < KLeap:
        return abs(nums[0] - nums[-1])
    # dp[i] is min cost when reaching stone i
    dp = [0] * n
    for i in range(1, KLeap):
        dp[i] = abs(nums[0] - nums[i])
 
    for i in range(K+1, n):
        dp[i] = min([dp[i - k] + abs(nums[i - k] - nums[i]) for k in range(1, KLeap)])
 
    return dp[-1]
 
 
if __name__ == "__main__":
    _, K = [int(x) for x in input().split()]
    nums = [int(x) for x in input().split()]
    print(knapsack(nums, K))

### FIXED CODE ###

def knapsack(nums, k):
    n = len(nums)

    # dp[i] is min cost when reaching stone i
    dp = [float('Inf')] * n
    dp[0] = 0
    for i in range(1, n):
        dp[i] = min([
            dp[i-j] + abs(nums[i] - nums[i-j])
            for j in range(1, k+1) if i - j >= 0]
        )
    return dp[-1]


if __name__ == "__main__":
    _, k = [int(x) for x in input().split()]
    nums = [int(x) for x in input().split()]
    print(knapsack(nums, k))
s=int(input())
i= list(map(int, input().split()))
 
i.sort(reverse=True)
sum=0
ks=0
for j in range(s):
    sum+=i[j+1]
for j in range(n,2*n):
  ks+=i[j]
print(max(sum,ks))

### FIXED CODE ###

s=int(input())
i= list(map(int, input().split()))
i.sort(reverse=True)
sum=0
for j in range(s):
    sum+=i[(2*j)+1]
print(sum)
L=list(map(int,input().split()));print(L[3],L[1],L[2])

### FIXED CODE ###

x,y,z = map(int,input().split())
print(z,x,y)
N = 50001
a = [True] *  N
i = 3
while i * i < N:
    for j in range(3 * i, N, 2 * i): a[j] = False
    i += 2
 
while True:
    try:
        n = int(input())
    except:
        break

    n0 = n + 2 if (n & 1) else n + 1
    for maxv in range(n0, N, 2):
        if a[maxv]: break
    n0 = n - 2 if (n & 1) else n - 1
    for minv in range(n0, 2, -2):
        if a[minv]: break

    print(minv, maxv)

### FIXED CODE ###

N = 50030
a = [True] *  N
i = 3
while i * i < N:
    for j in range(3 * i, N, 2 * i): a[j] = False
    i += 2
 
while True:
    try:
        n = int(input())
    except:
        break

    n0 = n + 2 if (n & 1) else n + 1
    for maxv in range(n0, N, 2):
        if a[maxv]: break
    n0 = n - 2 if (n & 1) else n - 1
    for minv in range(n0, 2, -2):
        if a[minv]: break
    else:
        minv = 2

    print(minv, maxv)
def tri(a,b,c):
	return a**2 == b**2 + c**2
for time in range(int(input())):
	x,y,z = [int(i) for i in input().split()]
	if tri(x,y,z) or tri(y,z,x) or tri(z,x,y):
		print(???YES???)

### FIXED CODE ###

def tri(a,b,c):
	return a**2 == b**2 + c**2
for time in range(int(input())):
	x,y,z = [int(i) for i in input().split()]
	if tri(x,y,z) or tri(y,z,x) or tri(z,x,y):
		print("YES")
	else:
		print("NO")
import math
A,B = map(int,input().split())

def prime_num_check(x):
  ls = []
  ls.append(1)
  for i in range(2,x+1):
    factor = 0
    if i%2 == 0 and i != 2:
      continue
    for divisor in range(2,math.floor(math.sqrt(i))+1):
      if i%divisor == 0:
        factor += 1
    if factor == 0:
      ls.append(i)
    return ls
  
x = math.gcd(A,B)

c_divisor = prime_num_check(x)
res = len(c_divisor) * (len(c_divisor) - 1) // 2

print(res)

### FIXED CODE ###

import math
A,B = map(int,input().split())
x = math.gcd(A,B)

def prime_decomposition(x):
  i = 2
  ls = []
  while i * i <= x:
    while x % i == 0:
      x /= i
      ls.append(i)
    i += 1
  if x > 1:
    ls.append(x)
  return ls

cnt = len(set(prime_decomposition(x)))

print(cnt+1)
N=int(input())
import math
A=list(map(int,input().split()))
b=math.ceil(math.log(max(A),2)) 
B=[0 for i in range(b)] #0のリスト
C=[0 for i in range(b)] #1のリスト
for i in A:
  for j in range(b):
    if ((i>>j) & 1):
      C[j]+=1
    else:
      B[j]+=1
 # print(B,C,i)
mod =10**9+7
ans=[(B[i]*C[i])*2**i % mod for i in range(b)]
print(sum(ans)%mod)

### FIXED CODE ###

N=int(input())
import math
A=list(map(int,input().split()))
b=math.ceil(math.log(max(max(A),1),2)) 
B=[0 for i in range(b)] #0のリスト
C=[0 for i in range(b)] #1のリスト
for i in A:
  for j in range(b):
    if ((i>>j) & 1):
      C[j]+=1
    else:
      B[j]+=1
 # print(B,C,i)
mod =10**9+7
ans=[(B[i]*C[i])*2**i % mod for i in range(b)]
print(sum(ans)%mod)
import math
import sys
a,b,c = map(int(input().split()))
if a < c and c < b:
    print("Yes")
elif b < c and c < a:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

import math
import sys
a,b,c = map(int,input().split())
if a < c and c < b:
    print("Yes")
elif a > c and c > b:
    print("Yes")
else:
    print("No")
N,M=map(int,input().split())
K=10**9+7
"""la=[]
for i in range(M):
    la.append(int(input()))"""
ldp=[0 for i in range(N)]
for i in range(M):
    a=int(input())
    ldp[a-1]=-1
if ldp[0]!=-1:
    ldp[0]=1
    #if ldp[1]!=-1:
    #    ldp[1]=1
if ldp[1]!=-1:
    ldp[1]+=1
    if ldp[0]!=-1:
        ldp[1]+=1
if N>=2:
    for i in range(2,N):
        if ldp[i]!=-1:
            if ldp[i-1]!=-1:
                ldp[i]=(ldp[i]+ldp[i-1])%K
            if ldp[i-2]!=-1:
                ldp[i]=(ldp[i]+ldp[i-2])%K
#print(ldp)
print(ldp[N-1])


### FIXED CODE ###

N,M=map(int,input().split())
K=10**9+7
"""la=[]
for i in range(M):
    la.append(int(input()))"""
ldp=[0 for i in range(N)]
for i in range(M):
    a=int(input())
    ldp[a-1]=-1
if ldp[0]!=-1:
    ldp[0]=1
    #if ldp[1]!=-1:
    #    ldp[1]=1
#if N>=1:


if N>=2:
    if ldp[1]!=-1:
        ldp[1]+=1
        if ldp[0]!=-1:
            ldp[1]+=1
    for i in range(2,N):
        if ldp[i]!=-1:
            if ldp[i-1]!=-1:
                ldp[i]=(ldp[i]+ldp[i-1])%K
            if ldp[i-2]!=-1:
                ldp[i]=(ldp[i]+ldp[i-2])%K
#print(ldp)
print(ldp[N-1])
import sys,math,collections,itertools,copy
input = sys.stdin.readline

D,G=list(map(int,input().split()))
score = []
maxScore = []
cos_per = []
for d in range(D):
    p,c=map(int,input().split())
    tmp = [(d+1)*100]*p
    tmp[-1]+=c
    score.append(tmp)
    maxScore.append(sum(tmp))
    #cos_per.append([d+1,sum(tmp)/p])
    cos_per.append([d+1,d+1])
#-最大いくつの問題セットを必要とするか-#
maxScore.sort()
tmp = 0
for idx,mS in enumerate(maxScore):
    tmp += mS
    if tmp >= G:
        max_num = idx+1
        break
#-最小でいくつの問題セットを必要とするか-#
tmp = 0
j=0
for i in range(len(maxScore)-1,-1,-1):
    j+=1
    tmp += maxScore[i]
    if tmp >= G:
        min_num = j
        break
#-最小-2個はスコアが高いものを入れてよし-#
#cos_per.sort(key = lambda x:-x[1])
#choice = set(range(1,D+1))
#choiceList = []
#for i in range(0,min_num-3):
 #   choiceList+=score[cos_per[i][0]-1]
 #   choice.discard(cos_per[i][0])
 #   max_num -=1
 
#-足し上げる-#

ans = float('inf')
for ch in itertools.permutations(choice,max_num):
    times = 0
    total = 0
    flag = 0
    for ci in ch:
        for sc in score[ci-1]:
            total += sc
            times += 1
            if total >= G:
                ans = min(ans,times)
                falg = 1
                break
    if flag ==1:
        break
print(ans)     


### FIXED CODE ###

import sys,math,collections,itertools,copy
input = sys.stdin.readline

D,G=list(map(int,input().split()))
score = []
maxScore = []
cos_per = []
maxS = []
for d in range(D):
    p,c=map(int,input().split())
    tmp = [(d+1)*100]*p
    tmp[-1]+=c
    score.append(tmp)
    maxScore.append(sum(tmp))
    maxS.append([p,sum(tmp)])
    #cos_per.append([d+1,sum(tmp)/p])
    cos_per.append([d+1,d+1])
#-最大いくつの問題セットを必要とするか-#
maxScore.sort()
tmp = 0
for idx,mS in enumerate(maxScore):
    tmp += mS
    if tmp >= G:
        max_num = idx+1
        break
#-最小でいくつの問題セットを必要とするか-#
tmp = 0
j=0
for i in range(len(maxScore)-1,-1,-1):
    j+=1
    tmp += maxScore[i]
    if tmp >= G:
        min_num = j
        break
#-最小-2個はスコアが高いものを入れてよし-#
#cos_per.sort(key = lambda x:-x[1])
choice = set(range(1,D+1))
#choiceList = []
#for i in range(0,min_num-3):
 #   choiceList+=score[cos_per[i][0]-1]
 #   choice.discard(cos_per[i][0])
 #   max_num -=1
 
#-足し上げる-#

ans = float('inf')
for ch in itertools.permutations(choice,max_num):
    times = 0
    total = 0
    flag = 0
    for ci in ch:
        if total + maxS[ci-1][1] <G:
            total += maxS[ci-1][1]
            times += maxS[ci-1][0]
        else:
            for sc in score[ci-1]:
                total += sc
                times += 1
                if total >= G:
                    ans = min(ans,times)
                    falg = 1
                    break
    if flag ==1:
        break
print(ans)
from collections import deque
import math


def main():
    n = int(input())
    digits = deque()
    alpha = ord('a') - 1
    maxex = int(math.log(n, 27))
    ex = 1
    for ex in range(1, maxex + 2):
        bb = pow(26, ex - 1)
        aa = bb * 26
        rem = n % aa // bb
        n -= bb * rem
        digits.appendleft(alpha + rem)
    if n != 0:
        digits.appendleft(alpha + n)

    [print(chr(d), end='') for d in digits]
    print()


if __name__ == '__main__':
    main()


### FIXED CODE ###

from collections import deque
import math


def main():
    n = int(input())
    if n == 1:
        print('a')
        return
    digits = deque()
    alpha = ord('a') - 1
    maxex = int(math.log(n-1, 26))
    ex = 1
    for ex in range(1, maxex + 2):
        bb = pow(26, ex - 1)
        aa = bb * 26
        rem = n % aa // bb
        n -= bb * rem
        if rem == 0:
            if n == 0:
                break
            rem += 26
            n -= aa
        digits.appendleft(chr(alpha + rem))

    [print(d, end='') for d in digits]
    print()


if __name__ == '__main__':
    main()
a = input()
print(a + a**2 + a**3)

### FIXED CODE ###

# １変数の標準入力
a = int(input())
# フォーマット関数
print("{}".format(a + a**2 + a**3))
N, A, B = map(int,input().split())
a = list()
a = ["blue"]*A + ["red"]*B
import math
n = math.ceil(N/(A+B))
for i in range(n):
    a = a + a
del a[N:]
print(a.count("blue"))


### FIXED CODE ###

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

import math
n = math.ceil(N//(A+B))
mod = N % (A+B)
b = n*A
if mod <= A:
    b += mod
else:
    b += A

print(b)
n = int(input())
a = list(map(int, input().split()))
lst = [i for i in range(n)]
start = 0
end = n-1
max_happy = 0
for _ in range(n):
  m = 0
  for j in lst:
    if abs(j - start) > abs(j - end):
      happy = a[j] * abs(j - start)
      idx = 0
    else:
      happy = a[j] * abs(j - end)
      idx = 1
    if happy > m:
      m = happy
      m_idx = idx
      m_point = j
  max_happy += m
  lst.remove(m_point)
  if m_idx == 0:
    start += 1
  else:
    end -= 1
print(max_happy)

### FIXED CODE ###

n = int(input())
a = map(int, input().split())
babies = [(a, i) for i, a in enumerate(a)]
babies.sort(reverse=True)

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

ans = 0

for l in range(n):
  for r in range(n):
    if l+r == n:
      ans = max(ans, dp[l][r])
      break
    activeness, ind = babies[l+r]
    dp[l+1][r] = max(dp[l+1][r], dp[l][r] + abs(ind - l) * activeness)
    dp[l][r+1] = max(dp[l][r+1], dp[l][r] + abs(ind - (n-1-r)) * activeness)
print(ans)
#coding: UTF-8

a,b,c=[int(x) for x in input().split()]

numlist = [a,b,c]

numlist.sorted()
print(numlist)


### FIXED CODE ###

#print(*sorted(map(int, input().split())))

print(*sorted(map(int, input().split())))
from numpy import int64, divmod

N, A = open(0)
N, A = int(N), int64(A.split())

ans = 0
S = -1
while S:
    B, A = divmod(A, N)
    S = B.sum()
    ans += S
    A += S - B

print(ans)


### FIXED CODE ###

N, *A = map(int, open(0).read().split())

ans = 0
S = 1
while S:
    S = sum(a // N for a in A)
    ans += S
    A = [a + S - (a // N) * (N + 1) for a in A]

print(ans)
import(math)

a,b=map(int,input().split())
if math.ceil(a/2)>=b:
  print('YES')
else:
  print('NO')

### FIXED CODE ###

import math
 
a,b=map(int,input().split())
if math.ceil(a/2)>=b:
  print('YES')
else:
  print('NO')
import sympy
n,m = map(int, input().split())

N = sympy.divisors(m)

for i in range(len(N)):
    if N[i] <= m/n:
        print(N[i])
        break

### FIXED CODE ###

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

def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n%i == 0:
      divisors.append(i)
      if i != n//i:
        divisors.append(n//i)
  divisors.sort(reverse=True)
  return divisors

numbers = make_divisors(m)
for i in range(len(numbers)):
  if numbers[i] <= m/n:
    print(numbers[i])
    break
(a,b)=map(int, raw_input().split())
if a<b
    print "a < b"
else if a>b
    print "a > b"
else
    print "a == b"

### FIXED CODE ###

(a,b)=map(int, raw_input().split())
if a<b:
    print "a < b"
if a>b:
    print "a > b"
if a==b:
    print "a == b"
n,q=map(int,input().split())
s=list(input())

count=0


ans=[0 for i in range(n+2)]
for i in range(n-1):
  if s[i]+s[i+1]=='AC':
    count+=1
    ans[i+1]=count
  else:
    ans[i+1]=count
ans[n]=ans[n-1]
ans[n+1]=ans[n]


for i in range(q):
  sita,ue=map(int,input().split())
  if s[ue-1]=='A' and s[ue]=='C':
    print(ans[ue]-ans[sita-1]-1)
  
  else:
    print(ans[ue]-ans[sita-1])
    
  

  


### FIXED CODE ###


n,q=map(int,input().split())
s=list(input())
a=[0]*n

for i in range(1,n):
  if s[i-1]=='A' and s[i]=='C':
    a[i]=a[i-1]+1
  else:
    a[i]=a[i-1]
    
for i in range(q):
  sita,ue=map(int,input().split())
  if sita==1:
    print(a[ue-1])
  elif s[sita-2]=='A' and s[sita-1]=='C':
    print(a[ue-1]-a[sita-2]-1)
  else:
    print(a[ue-1]-a[sita-2])
N = int(input())
A = list(map(int, input().split()))

if A[0] != 0:
    print(-1)
else:
    B = [0]*(N+1)
    C = [0]*(N+1)
    B[0] = 1
    C[N] = A[N]
    flag = True
    for i in range(1,N+1):
        B[i] = (B[i-1]-A[i-1]) * 2
        if (i < N and B[i] <= A[i]) or (i = N and B[i] < A[i]): flag = False
        C[N-i] = C[N+1-i]+A[N-i]
    sum = 0
    for i in range(0,N+1):
        sum += min(B[i],C[i])
    if flag == True:
        print(sum)
    else:
        print(-1)

### FIXED CODE ###

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

pm = sum(A)
e = 1
te = 1
for i in A:
    pm -= i
    e = min((e-i) * 2,pm)
    if e < 0:
        break
    te += e
if e < 0:
    print(-1)
else:
    print(te)
import sys
input = sys.stdin.buffer.readline
from collections import deque

n = int(input())

edges = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

nodes = [0 for _ in range(n)]
"""
white = all - black
"""

goal = n - 1
def dfs(num, f_num):
    if num == goal:
        nodes[num] = 1
        return 1
    s = 0
    for node in edges[num]:
        if node == f_num:
            continue
        s += dfs(node, num)
    nodes[num] = s + 1
    return s + 1

def dist(start, end):
    q =  deque([(0, -1, 1)])
    res = 0
    while len(q) > 0:
        num, f_num, dist = q.popleft()
        if num == end:
            res = dist
        for node in edges[num]:
            if node == f_num:
                continue
            q.append((node, num, dist + 1))
    return res

dfs(0, -1)
fennec = nodes[0] - dist(0, n-1) // 2
snuke = n - fennec
if fennec > snuke:
    print("Fennec")
else:
    print("Snuke")


### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
from collections import deque

n = int(input())
edges = [[] for _ in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

def get_dists(f):
    dists = [0 for _ in range(n)]
    q = deque()
    q.append((f, -1, 0))
    while len(q) > 0:
        num, f_num, dist = q.popleft()
        for node in edges[num]:
            if node == f_num:
                continue
            else:
                dists[node] = dist + 1
                q.append((node, num, dist+1))
    return dists

dist_1 = get_dists(0)
dist_n = get_dists(n-1)

ans = 0
for i in range(n):
    if dist_1[i] <= dist_n[i]:
        ans += 1

fennec = ans
snuke = n - fennec
if fennec > snuke:
    print("Fennec")
else:
    print("Snuke")
N=input()
div=0
A=0
B=0
count=0
answer=0
for i in range(1,N+1,2):
  div=0
  count=0
  while True:
    div+=1
    if i%div==0:
      A=div
      B=N/siv
      count+=1
    if B=count:
      if A<B and count==4:
        answer+=1  
      break
print(answer)

### FIXED CODE ###

N=int(input())
div=0
A=0
B=N
count=0
answer=0
for i in range(1,N+1,2):
  div=0
  count=0
  while True:
    div+=1
    if i%div==0:
      A=div
      B=i/div
      if A<B:
        count+=1
    if A>=B:
      if count==4:
        answer+=1  
      break
print(answer)
k = int(input())
x = int(input())
li = [str(x-k+1+i) for i in range(2*k-1)]
l = ' '.join(li)
print(l)

### FIXED CODE ###

k,x = map(int,input().split())	
li = [str(x-k+1+i) for i in range(2*k-1)]
l = ' '.join(li)
print(l)