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

N, Y = map(int, input().split())
for i in range(N):
  for j in range(N-i):
    k = N - i - j
    if Y == 10000 * k + 5000 * j + 1000 * i:
        print(" ".join(map(str, [k, j, i])))
        quit(0)
    elif Y == 10000 * k + 5000 * i + 1000 * j:
        print(" ".join(map(str, [k, i, j])))
        quit(0)
    elif Y == 10000 * i + 5000 * j + 1000 * k:
        print(" ".join(map(str, [i, j, k])))
        quit(0)
    elif Y == 10000 * i + 5000 * k + 1000 * j:
        print(" ".join(map(str, [i, k, j])))
        quit(0)
    elif Y == 10000 * k + 5000 * j + 1000 * i:
        print(" ".join(map(str, [k, j, i])))
        quit(0)
    elif Y == 10000 * k + 5000 * i + 1000 * j:
        print(" ".join(map(str, [k, i, j])))
        quit(0)
print("-1 -1 -1")

### FIXED CODE ###

N, Y = map(int, input().split())
for i in range(N + 1):
  for j in range(N- i + 1):
    k = N - i - j
    if Y == 10000 * i + 5000 * j + 1000 * k:
        print(" ".join(map(str, [i, j, k])))
        quit(0)
print("-1 -1 -1")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
def main():
    n,k = map(int,input().split())
    h = [int(i) for i in input().split()]
    # dpの最小値を変更する関数

    # 無限大の値
    f_inf = 10 ** 9 
    # DP テーブルを初期化　(最小化問題なので INF に初期化)
    dp = [f_inf] * (10**5+10)
    # 初期条件
    dp[0] = 0
    # 足場 i-1 から足場 i へ移動する。コストは|h[i]−h[i-1]|
    # 足場 i-2 から足場 i へと移動する コストは |h[i]−h[i-2]|
    for i in range(1, n):
        for j in range(1,k+1):
            if i-j < 0 :
                continue
            else:
                dp[i] = chmin(dp[i], dp[i - j] + abs(h[i] - h[i-j]))
    print(dp[n-1])

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
def chmin(a, b):
    if a > b:
        return b
    else:
        return a
  
n,k = map(int,input().split())
h = [int(i) for i in input().split()]
# dpの最小値を変更する関数

# 無限大の値
f_inf = 10 ** 9 
# DP テーブルを初期化　(最小化問題なので INF に初期化)
dp = [f_inf] * (10**5+10)
# 初期条件
dp[0] = 0
# 足場 i-1 から足場 i へ移動する。コストは|h[i]−h[i-1]|
# 足場 i-2 から足場 i へと移動する コストは |h[i]−h[i-2]|
for i in range(1, n):
    for j in range(1,k+1):
        if i-j < 0 :
            continue
        else:
            dp[i] = chmin(dp[i], dp[i - j] + abs(h[i] - h[i-j]))
print(dp[n-1])
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  w, v = map(int, input().split())
  for j in range(W+1):
    if j<w:
      dp[i][j] = dp[i-1][j]
      continue
    dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print(max(dp[N-1]))

### FIXED CODE ###

N, W = map(int, input().split())
dp = [[0]*(W+1) for _ in range(N+1)]
for i in range(N):
  w, v = map(int, input().split())
  for j in range(W+1):
    if j<w:
      dp[i][j] = dp[i-1][j]
      continue
    dp[i][j] = max(dp[i-1][j-w]+v, dp[i-1][j])
print(max(dp[N-1]))
### BUGGY CODE ###

#import sympy


def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

n=int(input())
t=0
for i in range(1,n+1):
    t=t+(len(make_divisors(i))*i)

print(t)


### FIXED CODE ###

n=int(input())
t=0
k=0
for i in range(1,n+1):
   k=n//i
   t+=i*k*(k+1)//2

print(t)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
lr = [tuple(map(int, input().split())) for _ in range(Q)]
for l, r in lr:
    print(S[l - 1:r].count("AC"))


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
lr = [tuple(map(int, input().split())) for _ in range(Q)]
acindex_list = []
ac = 0
old = ""
for c in S:
    if old == "A" and c == "C":
        ac += 1
    old = c
    acindex_list.append(ac)
for l, r in lr:
    print(acindex_list[r - 1] - acindex_list[l - 1])
### BUGGY CODE ###

from sys import exit
n = int(input())
a = [int(e) for e in input().split()]
b = [int(e) for e in input().split()]
result = 0
q = [i for i in range(n) if b[i] != a[i]]
while len(q) != 0:
    nq = []
    c = 0
    for i in q:
        if i == 0 or i == n - 1:
            j = b[(n + i - 1) % n] + b[(n + i + 1) % n]
        else:
            j = b[i - 1] + b[i + 1]
        if j > b[i] - a[i]:
            nq.append(i)
            continue
        c += 1
        k = (b[i] - a[i]) // j
        result += k
        b[i] -= j * k
        if a[i] != b[i]:
            nq.append(i)
    if c == 0 and len(nq) != 0:
        print(-1)
        exit()
    q = nq
print(result)


### FIXED CODE ###

def main():
  import sys
  _int = int
  n = _int(input())
  a = [_int(e) for e in input().split()]
  b = [_int(e) for e in input().split()]
  result = 0
  q = [i for i in range(n) if b[i] != a[i]]
  while len(q) != 0:
    nq = []
    c = 0
    for i in q:
      if i == 0 or i == n - 1:
        j = b[(n + i - 1) % n] + b[(n + i + 1) % n]
      else:
        j = b[i - 1] + b[i + 1]
      if j > b[i] - a[i]:
        nq.append(i)
        continue
      c += 1
      k = (b[i] - a[i]) // j
      result += k
      b[i] -= j * k
      if a[i] != b[i]:
        nq.append(i)
    if c == 0 and len(nq) != 0:
      print(-1)
      sys.exit()
    q = nq
  print(result)
main()
### BUGGY CODE ###

import sys
from collections import defaultdict

lines = 1
inp = list()

for _ in range(lines):
    inp.append(sys.stdin.readline().strip())


s = inp[0]
n = len(s)

tmp = defaultdict(int)
tmp[0] = 1

b = 0

for i in range(1, n + 1):
    a = int(s[n - i])
    b = ((10 ** (i-1)) * a + b) % 2019
    tmp[b] += 1

result = 0

for v in tmp.values():
    result += int(v * (v - 1) / 2)

print(result)


### FIXED CODE ###

import sys
from collections import defaultdict

lines = 1
inp = list()

for _ in range(lines):
    inp.append(sys.stdin.readline().strip())


s = inp[0]
n = len(s)

tmp = defaultdict(int)
tmp[0] = 1

b = 0
d = 1

for i in range(1, n + 1):
    a = int(s[n - i])
    b = ((d * a) + b) % 2019
    tmp[b] += 1
    d = (d * 10) % 2019

result = 0

for v in tmp.values():
    result += int(v * (v - 1) / 2)

print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

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

INF = 10**18

# dp0 = [[INF] * N for _ in range(N)]
# dp1 = [[INF] * N for _ in range(N)]
dp = [[INF] * N for _ in range(N)]

def calc(i, j, t):
    if dp[i][j] != INF:
        return dp[i][j]
    if t == 0:
        if i == j:
            dp[i][j] = a[i]
        else:
            dp[i][j] = max(calc(i+1, j, 1) + a[i], calc(i, j-1, 1) + a[j])
    else:
        if i == j:
            dp[i][j] = -a[i]
        else:
            dp[i][j] = min(calc(i+1, j, 0) - a[i], calc(i, j-1, 0) - a[j])
    return dp[i][j]
    # if t == 0:
    #     if dp0[i][j] == INF:
    #         if i == j:
    #             dp0[i][j] = a[i]
    #         else:
    #             dp0[i][j] = max(calc(i+1, j, 1) + a[i], calc(i, j-1, 1) + a[j])
    #     return dp0[i][j]
    # else:
    #     if dp1[i][j] == INF:
    #         if i == j:
    #             dp1[i][j] = -a[i]
    #         else:
    #             dp1[i][j] = min(calc(i+1, j, 0) - a[i], calc(i, j-1, 0) - a[j])
    #     return dp1[i][j]

print(calc(0, N-1, 0))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

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

INF = 10**18
dp = [[INF] * N for _ in range(N)]

# def calc(i, j, t):
#     if dp[i][j] != INF:
#         return dp[i][j]
#     if t == 0:
#         if i == j:
#             dp[i][j] = a[i]
#         else:
#             dp[i][j] = max(calc(i+1, j, 1) + a[i], calc(i, j-1, 1) + a[j])
#     else:
#         if i == j:
#             dp[i][j] = -a[i]
#         else:
#             dp[i][j] = min(calc(i+1, j, 0) - a[i], calc(i, j-1, 0) - a[j])
#     return dp[i][j]

# print(calc(0, N-1, 0))

for l in range(N):
    t = (N-l) % 2
    for i in range(N-l):
        j = i + l
        if t == 1:
            if l == 0:
                dp[i][j] = a[i]
            else:
                dp[i][j] = max(dp[i+1][j] + a[i], dp[i][j-1] + a[j])
        else:
            if l == 0:
                dp[i][j] = -a[i]
            else:
                dp[i][j] = min(dp[i+1][j] - a[i], dp[i][j-1] - a[j])
print(dp[0][N-1])
### BUGGY CODE ###

N, K = map(int, input().split())
ai = list(map(int, input().split()))
for i in range(N):
    ai[i] -= 1
    
import math
dv = []
dv.append(ai)
for k in range(1, int(math.log2(K)) + 1):
    l = [0] * N
    dv.append(l)
    for n in range(N):
        dv[k][n] = dv[k - 1][dv[k - 1][n]]
        
#a = []
now = 0
for i in range(int(math.log2(K)) + 1):
    if K >> i & 1:
        #a.append(i)
        now = dv[i][now]
print(now + 1)


### FIXED CODE ###

n, k = map(int, input().split())
an = list(map(int, input().split()))
for i in range(n):
    an[i] -= 1
    
import math
dv = []
dv.append(an)
K = k
N = n
for _ in range(1, int(math.log2(K)) + 1):
    l = [0] * N
    dv.append(l)

for k in range(1, int(math.log2(K)) + 1):
    for n in range(N):
        dv[k][n] = dv[k - 1][dv[k - 1][n]]
        
# N 回目を 2 ^ t で表すためにビット演算を用いる
# a : dv の何行目を用いるかを格納
a = []
for i in range(int(math.log2(K)) + 1):
    if K >> i & 1:
        a.append(i)
        
now = 0
for i in a:
    now = dv[i][now]
        
print(now + 1)
### BUGGY CODE ###

n = int(input())

ans = 0

for a,b in zip(range(1,n),range(2,n+1)):
    ans += a % b
print(ans)

### FIXED CODE ###

n = int(input())
ans = (n*(n-1))//2
print(int(ans))
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
setA=set(A)
number1={}#-1
number2={}
for i in setA:
    tmp=A.count(i) - 1
    souwa=(tmp - 1)*(tmp)//2
    number1[i]=souwa
    souwa=tmp*(tmp+1)//2
    number2[i]=souwa

t=sum(number2.values())

for a in A:
    total=number1[a]
    total+=t
    total-=number2[a]
    print(total)

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int,input().split()))
d=Counter(A)
dic={}
total=0
for item in d.items():
    counter=item[1]
    s1=(counter - 1)*(counter - 2)/2 #1個少ない
    s2=(counter)*(counter - 1)/2
    dic[item[0]]=int(s1 - s2)
    total+=int(s2)

for a in A:
    print(total + dic[a])
### BUGGY CODE ###

s = input()
res = 0
opes = [True]
while any(opes):
	opes = []
	for x in ['01', '10']:
		r = s.split(x)
		res += len(r) - 1
		opes.append(len(r)!=1)
		s = ''.join(r)

print(res * 2)

### FIXED CODE ###

from collections import Counter

s = input()
res = Counter(s)
print(min(res['0'], res['1']) * 2)
### BUGGY CODE ###

n = int(input())
b = []
flag = 1
for i in input().split():
    if flag > 0:
        b.append(i)
    else:
        b.insert(0, i)
    flag *= -1
    # print(b)
if flag < 0:
    b.reverse()
for i in b[:-1]:
    print(i+' ', end='')
print(b[-1])


### FIXED CODE ###

from collections import deque

n = int(input())
b = deque()
flag = 1
for i in input().split():
    if flag > 0:
        b.append(i)
    else:
        b.appendleft(i)
    flag *= -1
if flag < 0:
    b.reverse()
print(' '.join(b))
### BUGGY CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
mod=998244353
from collections import defaultdict
DX=defaultdict(int)
DY=defaultdict(int)
XY,X,Y=[],[],[]
for _ in range(n):
  x,y=map(int,input().split())
  X.append(x)
  Y.append(y)
  XY.append((x,y))
X.sort()
Y.sort()
XY.sort(key=lambda x:x[0])
for i,x in enumerate(X):
  DX[x]=i+1
for i,y in enumerate(Y):
  DY[y]=i+1
XY2=[]
for x,y in XY:
  XY2.append((DX[x],DY[y]))
A=[[0]*4 for _ in range(n)]

n_max=2*10**5
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

for i in range(n):
  x,y=XY2[i]
  ct=bitsum(BIT,y)
  A[i][2]+=ct
  A[i][1]+=i-ct
  bitadd(BIT,y,1)

BIT=[0]*(2**nn)
BIT.insert(0,0)
for i in range(n)[::-1]:
  x,y=XY2[i]
  ct=bitsum(BIT,y)
  A[i][3]+=ct
  A[i][0]+=(n-1-i)-ct
  bitadd(BIT,y,1)

def f(x):
  return pow(2,x,mod)

ans=0
for a,b,c,d in A:
  ans+=2*f(a+b+c+d)-f(a+b)-f(b+c)-f(c+d)-f(d+a)+f(a)+f(b)+f(c)+f(d)-1
  ans%=mod
print(ans)


### FIXED CODE ###

import sys
input=lambda: sys.stdin.readline().rstrip()
n=int(input())
mod=998244353
from collections import defaultdict
DX=defaultdict(int)
DY=defaultdict(int)
XY,X,Y=[],[],[]
for _ in range(n):
  x,y=map(int,input().split())
  X.append(x)
  Y.append(y)
  XY.append((x,y))
X.sort()
Y.sort()
XY.sort(key=lambda x:x[0])
for i,x in enumerate(X):
  DX[x]=i+1
for i,y in enumerate(Y):
  DY[y]=i+1
XY2=[]
for x,y in XY:
  XY2.append((DX[x],DY[y]))
A=[[0]*4 for _ in range(n)]

n_max=2*10**5
nn=n_max.bit_length()+1
BIT=[0]*(2**nn)
BIT.insert(0,0)
def bitsum(BIT,i):
  s=0
  while i>0:
    s+=BIT[i]
    i-=i&(-i)
  return s
def bitadd(BIT,i,x):
  while i<=2**nn:
    BIT[i]+=x
    i+=i&(-i)
  return BIT

for i in range(n):
  x,y=XY2[i]
  ct=bitsum(BIT,y)
  A[i][2]+=ct
  A[i][1]+=i-ct
  bitadd(BIT,y,1)

BIT=[0]*(2**nn)
BIT.insert(0,0)
for i in range(n)[::-1]:
  x,y=XY2[i]
  ct=bitsum(BIT,y)
  A[i][3]+=ct
  A[i][0]+=(n-1-i)-ct
  bitadd(BIT,y,1)

P=[0]*n
P[0]=1
for i in range(1,n):
  P[i]=(P[i-1]*2)%mod
def f(x):
  return P[x]

ans=0
for a,b,c,d in A:
  ans+=2*f(a+b+c+d)-f(a+b)-f(b+c)-f(c+d)-f(d+a)+f(a)+f(b)+f(c)+f(d)-1
  ans%=mod
print(ans)
### BUGGY CODE ###

H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
A = [[[0,0] for _ in range(W)] for _ in range(H)]
for i in range(H):
    cnt = 0
    for j in range(W):
        if S[i][j]=="#":
            cnt = 0
        else:
            cnt += 1
            A[i][j][0] = cnt
for i in range(H):
    for j in range(W-1,-1,-1):
        if S[i][j]=="." and j+1<W:
            A[i][j][0] = max(A[i][j][0],A[i][j+1][0])
for j in range(W):
    cnt = 0
    for i in range(H):
        if S[i][j]=="#":
            cnt = 0
        else:
            cnt += 1
            A[i][j][1] = cnt
for j in range(W):
    for i in range(H-1,-1,-1):
        if S[i][j]=="." and i+1<H:
            A[i][j][1] = max(A[i][j][1],A[i+1][j][1])
B = [[0 for _ in range(W)] for _ in range(H)]
cmax = 0
for i in range(H):
    for j in range(W):
        if S[i][j]==".":
            B[i][j] = A[i][j][0]+A[i][j][1]-1
            cmax = max(cmax,B[i][j])
print(cmax)        

### FIXED CODE ###

H,W = map(int,input().split())
S = [input().strip() for _ in range(H)]
L = [[0 for _ in range(W)] for _ in range(H)]
R = [[0 for _ in range(W)] for _ in range(H)]
U = [[0 for _ in range(W)] for _ in range(H)]
D = [[0 for _ in range(W)] for _ in range(H)]
for i in range(H):
    for j in range(W):
        if j==0 and S[i][j]==".":
            L[i][j] = 1
        elif j>0 and S[i][j]==".":
            L[i][j] = L[i][j-1]+1
        if i==0 and S[i][j]==".":
            U[i][j] = 1
        elif i>0 and S[i][j]==".":
            U[i][j] = U[i-1][j]+1
for i in range(H-1,-1,-1):
    for j in range(W-1,-1,-1):
        if j==W-1 and S[i][j]==".":
            R[i][j] = 1
        elif j<W-1 and S[i][j]==".":
            R[i][j] = R[i][j+1]+1
        if i==H-1 and S[i][j]==".":
            D[i][j] = 1
        elif i>0 and S[i][j]==".":
            D[i][j] = D[i+1][j]+1
cmax = 0
for i in range(H):
    for j in range(W):
        cmax = max(cmax,L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(cmax)
### BUGGY CODE ###

H, W, N = map(int, input().split())
d = {}
ans = [0] * 10
ans[0] = (H - 2) * (W - 2)
for i in range(N):
    a, b = map(int, input().split())
    for v in [a - 1, a, a + 1]:
        if v < 2 or v > H - 1:
            continue
        for w in [b - 1, b, b + 1]:
            if w < 2 or w > W - 1:
                continue
            black = 0
            for x in [v - 1, v, v + 1]:
                for y in [w - 1, w, w + 1]:
                    black += d.get((x, y), 0)
            ans[black] -= 1
            ans[black + 1] +=1
            #print(a, b, black, ans)
    d[a, b] = 1
    #print(d)
for i in ans:
    print(i)

### FIXED CODE ###

H, W, N = map(int, input().split())
d = {}
ans = [0] * 10
ans[0] = (H - 2) * (W - 2)
for i in range(N):
    a, b = map(int, input().split())
    for v in [a - 1, a, a + 1]:
        if v < 2 or v > H - 1:
            continue
        for w in [b - 1, b, b + 1]:
            if w < 2 or w > W - 1:
                continue
            black = 0
            for x in [v - 1, v, v + 1]:
                for y in [w - 1, w, w + 1]:
                    black += d.get((x, y), 0)
            ans[black] -= 1
            ans[black + 1] +=1
            #print(a, b, black, ans)
    d[a, b] = 1
    #print(d)
for i in ans:
    print(i)
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = {}
B = [0]*N
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in range(10**9) :
    try:
        for j in A[i] :
            for k in range(L) :
                if j + k not in ANS :
                    ANS[j+k] = i
                    count += 1
        if count > N * 0.9997 - 100 : break
    except KeyError:
        continue

for i in range(L):
    if i not in ANS : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n= int(input())
l =list(map(int,input().split()))
ans= 1
for i in range(n):
    ans*= l[i]
if ans <= 10**18:
    print(ans)
else:
    print("-1")

### FIXED CODE ###

n= int(input())
l =list(map(int,input().split()))
ans= 1

if 0 in l:
    print("0")
else:
    for i in range(n):
        ans*= l[i]
        if ans> 10**18:
            break
    if ans> 10**18:
        print("-1")
    else:
        print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
ls=[int(input()) for i in range(m)]

def dp(n,ls):
    dp_table=[[0 for i in range(n+1)]]
    dp_table[0][0]=1
    sum=0
    count=1
    edge=0
    while True:
        row=[0]*count
        previous=dp_table[-1]
        for i in range(count,n+1):
            if i in ls:
                row.append(0)
            elif i==0:
                row.append(0)
            elif i==1:
                row.append(previous[0])
            else:
                row.append(previous[i-1]+previous[i-2])
            if i==edge+2:
                edge=i
                row=row+([0]*(n-edge))
                break
        sum+=row[-1]
        if row.count(0)==n+1:
            return sum
        dp_table.append(row)
        count+=1

print(dp(n,ls)%1000000007)

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
a = set(a)
mod = 10**9+7
dp = [0]*(n+1)
dp[0] = 1
if 1 not in a:
    dp[1] = 1
for i in range(2,n+1):
    if i not in a:
        dp[i] = dp[i-1]+dp[i-2]
print(dp[-1]%mod)
### BUGGY CODE ###

n,K = map(int,input().split())
h = [0]
for i in input().split(): h.append(int(i))
def cost(i,j): return abs(h[i]-h[j])

dp = [float("inf") for _ in range(n+1)]
dp[0] = dp[1] = 0
for i in range(2,n+1):
    for k in range(1,K+1):
        if i-k > 0:
            dp[i] = min(dp[i-k]+cost(i,i-k),dp[i])

print(dp[n])


### FIXED CODE ###

n,K = map(int,input().split())
h = [0]
for i in input().split(): h.append(int(i))
def cost(i,j): return abs(h[i]-h[j])

dp = [float("inf") for _ in range(n+1)]
dp[0] = dp[1] = 0
for i in range(2,n+1):
    for k in range(1,K+1):
        if i-k > 0:
            dp[i] = min(dp[i-k]+cost(i,i-k),dp[i])

print(dp[n])
### BUGGY CODE ###

from itertools import combinations, product

n, m, q = map(int, input().split())
a = [0 for _ in range(q)]
b = [0 for _ in range(q)]
c = [0 for _ in range(q)]
d = [0 for _ in range(q)]

for i in range(q):
	a[i], b[i], c[i], d[i] = map(int, input().split())
	a[i] -= 1
	b[i] -= 1

max_score = 0
all_combs = product(range(1, m+1), repeat=n)
for comb in all_combs:
	is_sorted = True
	for i in range(1, n):
		if comb[i] - comb[i-1] < 0:
			is_sorted = False
			break
	if is_sorted:
		# print(comb)
		cur_score = 0
		for i in range(q):
			if comb[b[i]] - comb[a[i]] == c[i]:
				cur_score += d[i]
		# print("cur_score", cur_score)
		if cur_score > max_score:
			max_score = cur_score
			# print("new max", max_score)
		# print()

print(max_score)


### FIXED CODE ###

n, m, q = map(int, input().split())
a = [0 for _ in range(q)]
b = [0 for _ in range(q)]
c = [0 for _ in range(q)]
d = [0 for _ in range(q)]

for i in range(q):
	a[i], b[i], c[i], d[i] = map(int, input().split())
	a[i] -= 1
	b[i] -= 1

def get_next(l):
	i = n-1
	while i > -1 and l[i] == m:
		i -= 1

	if i < 0:
		return -1
	else:
		l[i] += 1
		for j in range(i+1, n):
			l[j] = l[i]
	return l

max_score = 0
cur_seq = [1 for _ in range(n)]
while cur_seq != -1:
	cur_score = 0
	for i in range(q):
		if cur_seq[b[i]] - cur_seq[a[i]] == c[i]:
			cur_score += d[i]
	if cur_score > max_score:
		max_score = cur_score
	cur_seq = get_next(cur_seq)

print(max_score)
### BUGGY CODE ###

def n_ary_notation(N, n):
  if N == 0:
    return '0'
  else:
    s = ''
    while N:
      s = str(N % abs(n)) + s
      N -= N % abs(n)
      N //= n
    return s
strL = input()
N = 21
M = 61
K = 2
while True:
  K += 1
  L = n_ary_notation(int(strL) - 1, K)
  N = len(L) * 2
  M = K * (len(L) - 1)
  for l in L:
    M += int(l) + 1
  if N < 21 and M < 61:
    break
print(N, M)
for i, l in enumerate(L[:-1]):
  k = len(L) - 1 - i
  print(2 * i + 1, 2 * i + 3, int(l) * K ** k)
  for j in range(int(l)):
    print(2 * i + 1, 2 * i + 2, j * K ** k)
for i in range(int(L[-1]) + 1):
  print(2 * len(L) - 1, 2 * len(L), i)
for k in range(len(L) - 1):
  s = 2 * (len(L) - k)
  for i in range(K):
    print(2 * (len(L) - k - 1), 2 * (len(L) - k), i * K ** k)

### FIXED CODE ###

L = int(input())
R = 0
while True:
  R += 1
  if 2 ** R > L:
    R -= 1
    break
N = R + 1
M = 2 * R
_L = L
for r in range(R, 0, -1):
  if _L - 2 ** (r - 1) >= 2 ** R:
    M += 1
    _L -= 2 ** (r - 1)
print(N, M)
for i in range(R):
  print(i + 1, i + 2, 2 ** i)
  print(i + 1, i + 2, 0)
for r in range(R, 0, -1):
  if L - 2 ** (r - 1) >= 2 ** R:
    print(r, N, L - 2 ** (r - 1))
    L -= 2 ** (r - 1)
### BUGGY CODE ###

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

def countAC(l, r):
    count = 0
    for i in range(l, r):
        if(S[i] == "A" and S[i+1] == "C"):
            count += 1
    return count

for i in range(Q):
    print(countAC(LR[i][0]-1, LR[i][1]-1))
        

### FIXED CODE ###

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

accum = [0] * N

def countAC():
    count = 0
    for i in range(1, N):
        if(S[i-1] == "A" and S[i] == "C"):
            count += 1
        accum[i] = count



countAC()

for i in range(Q):
    print(accum[LR[i][1]-1] - accum[LR[i][0]-1])