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

H, W = map(int, input().split())
S = []
for i in range(H):
  ss = input()
  S.append(ss)
L = [[-1]*W for i in range(H)]
R = [[-1]*W for i in range(H)]
U = [[-1]*W for i in range(H)]
D = [[-1]*W for i in range(H)]
for i in range(H):
  n = 0
  for j in range(W):
    if S[i][j] == "#":
      n = 0
    else:
      n += 1
    L[i][j] = n
  n = 0
  for j in reversed(range(W)):
    if S[i][j] == "#":
      n = 0
    else:
      n += 1
    R[i][j] = n
for j in range(W):
  n = 0
  for i in range(H):
    if S[i][j] == "#":
      n = 0
    else:
      n += 1
    U[i][j] = n
  n = 0
  for i in reversed(range(H)):
    if S[i][j] == "#":
      n = 0
    else:
      n += 1
    D[i][j] = n
#for i in range(H):
#  print(U[i])
rs = []
for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      r = L[i][j]+R[i][j]+U[i][j]+D[i][j]-3
      rs.append(r)
r = max(rs)
print(r)


### FIXED CODE ###

H, W = map(int, input().split())
S = []
for i in range(H):
  ss = input()
  S.append(ss)
L = [[-1]*W for i in range(H)]
R = [[-1]*W for i in range(H)]
U = [[-1]*W for i in range(H)]
D = [[-1]*W for i in range(H)]
for i in range(H):
  n = -1
  for j in range(W):
    if S[i][j] == "#":
      n = j
    L[i][j] = j-n
  n = W
  for j in reversed(range(W)):
    if S[i][j] == "#":
      n = j
    R[i][j] = n-j
for j in range(W):
  n = -1
  for i in range(H):
    if S[i][j] == "#":
      n = i
    U[i][j] = i-n
  n = H
  for i in reversed(range(H)):
    if S[i][j] == "#":
      n = i
    D[i][j] = n-i
#for i in range(H):
#  print(D[i])
r = 0
for i in range(H):
  for j in range(W):
    if S[i][j] == ".":
      r = max(r, L[i][j]+R[i][j]+U[i][j]+D[i][j]-3)
print(r)
### BUGGY CODE ###

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

count = 0
for i in range(a, b+1):
    # print(i)  # debug
    if i % x == 0:  # 余りが0 = 割り切れる
        count += 1

print(count)


### FIXED CODE ###

import math
from decimal import Decimal
a, b, x = map(int, input().split())
a, b, x = Decimal(a), Decimal(b), Decimal(x)

min_bai = math.ceil(a/x)  # xの倍数で最小
max_bai = math.floor(b/x)  # xの倍数で最大
x_bai = max_bai - min_bai + 1

# print(min_bai)  # debug
# print(max_bai)  # debug
print(x_bai)
### BUGGY CODE ###

N=int(input())
S=list(map(int,input().split()))
S.sort(reverse=True)
p = [S.pop(0)]
c = S
f = False

for i in range(N):
    np = []
    nc = []
    for j in range(len(p)):
        for k in range(len(c)):
            if c[k] < p[j]:
                np.append(c.pop(k))
                f = True
                break
        if f == False:
            print("No")
            exit(0)
        f = False
    p += np
    p.sort(reverse=True)

print("Yes")

### FIXED CODE ###

N=int(input())
S=list(map(int,input().split()))
S.sort()
p = [S.pop(-1)]
r = S

for i in range(N):
    nr = []
    for p_ in p[::-1]:
        while r:
            r_ = r.pop()
            if r_ < p_:
                p.append(r_)
                break
            nr.append(r_)
    p.sort()
    r+=nr[::-1]

print("Yes" if len(r)==0 else "No")
### BUGGY CODE ###

from fractions import gcd
K = int(input())
A = B = C = [i for i in range(1, K+1)]
cnt = sum([gcd(gcd(a,b),c) for a in A for b in B for c in C])   
print(cnt)

### FIXED CODE ###

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
  
K = int(input())
A = B = C = [i for i in range(1, K+1)]

L = [gcd(a,b) for a in A for b in B]

cnt = sum([gcd(l,c) for l in L for c in C])   
print(cnt)
### BUGGY CODE ###

n, m = [int(i) for i in input().split()]
pre = []
year = []
year_order = [0 for i in range(m)]
each_arr = [[] for i in range(n)]
each_sort = [[] for i in range(n)]

for i in range(m):
    p, y = [int(i) for i in input().split()]
    pre.append(p)
    year.append(y)


for i in range(m):
    each_arr[pre[i]-1].append(year[i])

for j in range(n):
    each_sort[j] = sorted(each_arr[j])

for i in range(m):
    year_order[i] = each_sort[pre[i]-1].index(each_arr[pre[i]-1][0])+1
    each_arr[pre[i]-1].remove(each_arr[pre[i]-1][0])

pre = [format(str(i), '0>6') for i in pre]
year_order = [format(str(i), '0>6') for i in year_order]

for i in range(m):
    print(pre[i]+year_order[i])

### FIXED CODE ###

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

N, M = map(int, input().split())
L = []
for i in range(M):
    P, Y = map(int, input().split())
    L.append([P, Y, i])

L = sorted(L)

reset = 0
count = 0
ans = []
for i in range(M):
    if L[i][0] != reset:
        reset = L[i][0]
        count = 1
    else:
        count += 1
    
    ans.append([L[i][2], str(reset).zfill(6) + str(count).zfill(6)])

ans = sorted(ans)

for i in range(M):
    print(ans[i][1])
### BUGGY CODE ###

N = int(input())
a = [int(s) for s in input().split()]
ans = int(0)
temp = int(0)
MOD = int(1000000007)
for i in range(N-1):
  temp = sum(a[i+1:N])
  temp = temp % MOD
  temp = temp * a[i]
  temp = temp % MOD
  ans += temp
  ans = ans % MOD
print(ans)

### FIXED CODE ###

N = int(input())
a = [int(s) for s in input().split()]
ans = int(0)
temp = int(0)
MOD = int(1000000007)
sumari = sum(a)

for i in range(N-1):
  sumari = sumari - a[i] 
  temp = sumari % MOD
  temp = temp * a[i]
  temp = temp % MOD
  ans += temp
  ans = ans % MOD
print(ans)
### BUGGY CODE ###

import numpy as np

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

for i in range(0, N):
    a, b = np.array(list(map(int, input().split())))
    A.append(a)
    B.append(b)

cnt = 0
sum = 0
flag = 0
for j in range(0, N):
    idx = A.index(min(A))
    arrayA = np.array(A)
    arrayB = np.array(B)
    pay = arrayA[idx]
    num = arrayB[idx]
    A.pop(idx)
    B.pop(idx)
    if cnt + num < M :
        cnt += num
        sum += pay*num
    else :
        diff = M - cnt
        for t in range(0, diff):
            sum += pay
            cnt += 1
            if cnt == M :
                flag = 1
                print(sum)
                break
    if flag == 1:
        break


### FIXED CODE ###

import numpy as np

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

for i in range(0, N):
    a, b = np.array(list(map(float, input().split())))
    A.append((a, b))

dtype = [('key', int), ('value', int)]
arrayA = np.array(A, dtype=dtype)
arrayA = np.sort(arrayA, order=['key'])
cnt = 0
sum = 0
flag = 0
for j in range(0, N):
    pay = arrayA[j][0]
    num = arrayA[j][1]
    if cnt + num < M :
        cnt += num
        sum += pay*num
    else :
        diff = int(M - cnt)
        for t in range(0, diff):
            sum += pay
            cnt += 1
            if cnt == M :
                flag = 1
                print(int(sum))
                break
    if flag == 1:
        break
### BUGGY CODE ###

import re
N, Q = map(int, input().split())
S = input()
iter = re.finditer("AC", S)
indices_C = [m.start(0)+1 for m in iter]
total = S.count("AC")

dec_l_list = []
dec_l = 0
dec_r_list = []
dec_r = total
for i in range(N):
    if i in indices_C:
        dec_l += 1
        dec_r -= 1
    dec_l_list.append(dec_l)
    dec_r_list.append(dec_r)

for i in range(Q):
    l, r = map(int, input().split())
    print(total - dec_l_list[l-1] - dec_r_list[r-1])

### FIXED CODE ###

#import re
N, Q = map(int, input().split())
S = input()
#iter = re.finditer("AC", S)
#indices_C = [m.start(0)+1 for m in iter]
#total = len(indices_C)
#
#dec_l_list = []
#dec_l = 0
#dec_r_list = []
#dec_r = total
#for i in range(N):
#    if i in indices_C:
#        dec_l += 1
#        dec_r -= 1
#    dec_l_list.append(dec_l)
#    dec_r_list.append(dec_r)

flag = False
dec_l_list = []
total = 0
for i in range(N):
    if flag and S[i] == "C":
        total += 1
    dec_l_list.append(total)
    flag = True if S[i] == "A" else False
dec_r_list = [total - x for x in dec_l_list]

for i in range(Q):
    l, r = map(int, input().split())
    print(total - dec_l_list[l-1] - dec_r_list[r-1])
### BUGGY CODE ###

def product(list):
    i=1
    for j in list:
        i*=j
    return i

N=int(input())
A=list(map(int,input().split()))
ans=product(A)
if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
flag=True
if 0 in A:
    print(0)
else:
    for j in A:
        ans*=j
        if ans>10**18:
            print(-1)
            flag=False
            break
    if flag:
        print(ans)
### BUGGY CODE ###

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

for i in range(n):
    print(a.count(i + 1))

### FIXED CODE ###

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

for i in a:
    num_sub[i - 1] += 1

for num in num_sub:
    print(num)
### BUGGY CODE ###

n,k=map(int,input().split())
a,b=map(int,input().split())
s=[]
s+=[a]*b
for i in range(n-1):
  a,b=map(int,input().split())
  if a>max(s) and len(s)>k:
    continue
  s+=[a]*b
p=sorted(s)
print(p[k-1])

### FIXED CODE ###

n,k=map(int,input().split())
d=[0]*(10**5+1)
for i in range(n):
  a,b=map(int,input().split())
  d[a]+=b
for i in range(10**5+1):
  if d[i]>=k:
    print(i)
    break
  else:k-=d[i]
### BUGGY CODE ###

X = int(input())
if X==1:
    print(0,-1) 
else:
    d = 2
    while(X%d!=0):
        d+=1
    b = -(10**2)
    a = b+d
    while(X!=((a**5)-(b**5))):
        b+=1
        a=b+d
    print(a,b)

### FIXED CODE ###

X = int(input())

A = range(-118,120)
B = range(-118,120)
flag = 0
for a in A:
  for b in B:
    ans = a**5 - b**5
    if ans == X:
      print("{} {}".format(a,b))
      flag=1
      break
  if flag:
    break
### BUGGY CODE ###

import math 
def num_divisors_table(n):
  maxnum=math.floor((n + 1)/2) 
  length=n-maxnum
  aftersum=int(maxnum*length+length*(length+1)/2)
  aftersum+=(1+n)*n/2
  if n>=2:
    if n%2==0:
      aftersum+=(1+n/2)*n/2
    else:
      aftersum+=(1+(n-1)/2)*(n-1)/2

  for i in range(3, maxnum+1):
    for j in range(i, n+1, i):
      aftersum += j
  return aftersum

N=int(input())
print(int(num_divisors_table(N)))

### FIXED CODE ###

import math 
def num_divisors_table(n):
  maxnum=math.floor((n + 1)/2) #3
  #table = [0 for _ in range(n+1)]
  length=n-maxnum
  aftersum=int(maxnum*length+length*(length+1)/2)
  aftersum+=(1+n)*n/2
  if n>=2:
    if n%2==0:
      aftersum+=(1+n/2)*n/2
    else:
      aftersum+=(1+(n-1)/2)*(n-1)/2

  for i in range(3, maxnum+1):
    for j in range(i, n+1, i):
      aftersum += j
      #print(i,j)
  return aftersum

N=int(input())
#Nlist,ans_1=num_divisors_table(N)
#print(Nlist)
print(int(num_divisors_table(N)))
#print(int(sum(Nlist)+ans_1))
### BUGGY CODE ###

n = int(input())
apple = []
for _ in range(n):
    a = int(input())
    if a not in apple:
        apple.append(a)
    else:
        apple.remove(a)
print(len(apple))

### FIXED CODE ###

n = int(input())
apple = []
for _ in range(n):
    apple.append(int(input()))
apple = sorted(apple)
apple.append(0)
count = 0
ans = 1
for i in range(n):
    if apple[i] == apple[i + 1]:
        ans += 1
    else:
        if ans%2 == 0:
            ans = 1
        else:
            count += 1
print(count)
### BUGGY CODE ###

import itertools
from sys import stdin
N=list(map(int,stdin.readline().strip().split()))[0]
st=list(stdin.readline().strip())
count=0
num=list(set(st))
# num=["0","1","2","3","4","5","6","7","8","9"]
# num = [s for s in num if s in stt ]
num_list= ["".join(i) for i in itertools.product(num,repeat=3)]

for number in num_list:
    cnt = 0
    for i in range(N):
        if number[cnt]==st[i]:
            cnt+=1
            if cnt==3:
                count += 1
                break


print(count)

### FIXED CODE ###

def main():
  N = int(input())
  S = list(map(int,input()))
  ans = 0
  for i in range(10):
    for j in range(10):
      for k in range(10):
        flg = False
        flg2 = False
        for x in range(N):
          if flg2:
            break
          if not flg:
            if S[x] == i:
              flg = True
          else:
            if S[x] == j:
              flg2 = True
              if k in S[x+1:]:
                ans +=1
  print(ans)
main()
### BUGGY CODE ###

def fact(num):
  ret=[]
  if num==2:
    ret=[2]
    return ret
  elif num==3:
    ret=[2,3]
    return ret
  while 1:
    for i in range(2,int(num**0.5)+1):
      if num%i==0:
        ret.append(i)
        num=num%i
        break
 
n=int(input())
ans=fact(n)
print('{}: {}'.format(n,' '.join(map(str,ans))))


### FIXED CODE ###

def prime(num):
    if num==1:
        return False
    elif num==2 or num==3:
        return True
    else:
        for i in range(2,int(num**0.5)+1):
            if num%i==0:
                return False
        else:
            return True

n=int(input())
tmp=n
plist=[]
if prime(n):
    print('{}: {}'.format(n,n))
else:
    while 1:
        for i in range(2,tmp+1):
            if tmp%i==0:
                plist.append(i)
                tmp=tmp//i
                break
        else:
            break
    print('{}: {}'.format(n,' '.join(map(str,plist))))
### BUGGY CODE ###

import math
N=int(input())
for n in range(1,N+1):
    c=0
    for x in range(1,int(math.sqrt(n))):
        p=int(math.sqrt(n-x**2))
        for y in range(1,p):
            q=int(math.sqrt(n-x**2-y**2))
            for z in range(1,q):
                if n==x**2+y**2+z**2+x*y+y*z+z*x:
                    c=c+1
    print(c)


### FIXED CODE ###

N=int(input())
def sq(n):
    c=0
    A=[0 for j in range(n+1)]
    for i in range(n//2):
        p=(i+1)**2
        if p>n:
            for j in range(i**2,n+1):
                A[j]=i
            break
        else:
            for j in range(i**2,p):
                A[j]=i
    return A
A=sq(N)
a=A[N]
L=[0 for j in range(N+1)]
for x in range(1,a+1):
    for y in range(1,a+1):
        for z in range(1,a+1):
            p=x**2+y**2+z**2+x*y+y*z+z*x
            if p<=N:
                L[p]=L[p]+1
            else:
                break
for i in range(1,N+1):
    print(L[i])
### BUGGY CODE ###

if __name__ == '__main__':
    try:
        n = int(raw_input())
    except:
        print 'the first input must be integer value!'
        exit()

    genoms = []
    answers = []
    for _ in range(n):
        values = raw_input().split()
        order = values[0]
        genom = values[1]
        if order == "insert":
            genoms.append(genom)
        else:
            answers.append('yes' if genom in genoms else 'no' )

    # print(genoms)
    # print(answers)

    for answer in answers:
        print answer

### FIXED CODE ###

if __name__ == '__main__':
    try:
        n = int(raw_input())
    except:
        print 'the first input must be integer value!'
        exit()

    genoms = set([])
    answers = []
    for _ in range(n):
        values = raw_input().split()
        order = values[0]
        genom = values[1]
        if order == "insert":
            genoms.add(genom)
        else:
            # TODO: fasten here!
            answers.append('yes' if genom in genoms else 'no' )

    # print(genoms)
    # print(answers)

    for answer in answers:
        print answer
### BUGGY CODE ###

h, k = map(int, input().split())
As = list(map(int, input().split()))
try:
    for i in range(k):
        As_max = max(As)
        #print(As_max)
        As.remove(As_max)
    As_sum = sum(As)
    #print(As)
    print(As_sum)

except ValueError:
    print(0)

### FIXED CODE ###

n, k = map(int, input().split())
nums = list(map(int, input().split()))
nums.sort()
ans = 0
for i in range(n-k):
    ans += nums[i]
print(ans)
### BUGGY CODE ###

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

c = 0
try:
    while P:
        p_i = P.pop()
        if p_i <= min(P):
            c += 1
except ValueError:
    print(c + 1)


### FIXED CODE ###

N = int(input())
P = map(int, input().split())

m = next(P)
c = 1
for p in P:
    if p <= m:
        m = p
        c += 1
print(c)
### BUGGY CODE ###

"""
最小公倍数LCMを求めて、LCMを各Aで除した商を合計すればよい
"""
def main():
    from math import gcd
    mod = 10**9 +7
    N = int(input())
    A = list(map(int,input().split()))
    l = A[0]
    for i in range(1,N):
        l = (l*A[i])//gcd(l,A[i])

    ans = 0
    for a in A:
        ans += (l//a)%mod
        ans %= mod
    print(ans)
main()

### FIXED CODE ###

from math import gcd

def lcm(a, b):
    return a*b//gcd(a,b)
def main():
    N = int(input())
    A = list(map(int, input().split()))
    mod = 10**9 + 7
    LCM = 1
    for a in A:
        LCM = lcm(LCM, a)
    ans = 0
    for a in A:
        ans += (LCM//a)
        

    print(ans % mod)
main()
### BUGGY CODE ###

n = int(input())

ans = 1

for i in range(n):
    ans *= i + 1

print(ans % 1000000007)


### FIXED CODE ###

#!/usr/bin/env python3
n = int(input())

ans = 1

for i in range(n):
    ans *= i + 1
    ans %= 1000000007

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

import statistics

q=int(input())
a=[]
len_a=0
sum_b=0
for _ in range(q):
    qi=list(map(int,input().split()))
    if qi[0]==1:
        a.append(qi[1])
        sum_b+=qi[2]
        len_a+=1
    else:
        m=statistics.median_low(a)
        print(m,sum_b+sum(abs(x-m) for x in a))


### FIXED CODE ###

# youtube
from heapq import *

q = int(input())
sum_a = 0
sum_b = 0
L = []
R = []
for _ in range(q):
    qi = list(map(int, input().split()))
    if qi[0] == 1:
        a = qi[1]
        heappush(L, -a)
        heappush(R, a)
        if -L[0] > R[0]:
            LtoR = -heappop(L)
            RtoL = heappop(R)
            sum_a += LtoR - RtoL
            heappush(L, -RtoL)
            heappush(R, LtoR)
        sum_b += qi[2]
    else:
        print(-L[0], sum_a + sum_b)
### BUGGY CODE ###

import sys
a,b = map(int,input().split())
minus_count = 0
for i in range(a,b+1):
    if i == 0:
        print('Zero')
        sys.exit()
    if i < 0:
        minus_count += 1
if minus_count%2 == 1:
    print('Negative')
else:
    print('Positive')

### FIXED CODE ###

import sys
a,b = map(int,input().split())
if a > 0:
    print('Positive')
    sys.exit()
if b >= 0:
    print('Zero')
    sys.exit()
if (b-a+1)%2 == 1:
    print('Negative')
else:
    print('Positive')
### BUGGY CODE ###

#!/usr/bin/env python3

N, K = list(map(int, input().split()))
h_list = list(map(int, input().split()))
dp_list = [float("inf")] * N
dp_list[0] = 0

for i in range(1, N):
    # j番目の足場からi番目の足場に飛ぶ
    min_cost = float("inf")
    for j in range(max(i - K, 0), i):

        # j番目の足場までの最適コスト
        cum_cost = dp_list[j]

        # j番目の足場から飛んだ場合のコスト
        cost = dp_list[j] + abs(h_list[j] - h_list[i])
        if cost < min_cost:
            min_cost = cost

    # 最適コストで更新
    dp_list[i] = min_cost

ans = dp_list[-1]
print(ans)


### FIXED CODE ###

N, K = list(map(int, input().split()))
h_list = list(map(int, input().split()))
dp_list = [float("inf")] * N
dp_list[0] = 0

for i in range(1, N):
    # j番目の足場からi番目の足場に飛ぶ

    for j in range(max(i - K, 0), i + 1):

        # j番目の足場までの最適コスト
        cum_cost = dp_list[j]

        # j番目の足場から飛んだ場合のコスト
        cost = dp_list[j] + abs(h_list[j] - h_list[i])

        # 最適コストで更新
        dp_list[i] = min(dp_list[i], cost)

ans = dp_list[-1]
print(ans)
### BUGGY CODE ###

s = list(input())
q = int(input())

for i in range(q):
    op = input().split()
    if op[0] == "1":
        s.reverse()
    else:
        if op[1] == "1":
            s.insert(0, op[2])
        else:
            s.append(op[2])
    
for i in s:
    print(i, end='')
print()

### FIXED CODE ###

s = input()
q = int(input())

rvs = False
front = []
back = []
for i in range(q):
    op = input().split()
    if op[0] == "1":
        rvs = rvs ^ 1
    else:
        if op[1] == "1":
            if rvs:
                back.append(op[2])
            else:
                front.append(op[2])
        else:
            if rvs:
                front.append(op[2])
            else:
                back.append(op[2])

if rvs:
    for c in reversed(back):
        print(c, end='')
    for c in reversed(s):
        print(c, end='')
    for c in front:
        print(c, end='')
else:
    for c in reversed(front):
        print(c, end='')
    print(s, end='')
    for c in back:
        print(c, end='')

print()
### BUGGY CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

X, Y, Z, K = MAP()
A = LIST()
B = LIST()
C = LIST()

A=sorted(A)[::-1]
B=sorted(B)[::-1]
C=sorted(C)[::-1]
ans = []
for i in range(len(A)):
	if i > K:
		continue
	for j in range(len(B)):
		if i * j > K:
			continue
		for k in range(len(C)):
			if i * j * k > K:
				continue
			else:
				ans.append(A[i]+B[j]+C[k])
for i in sorted(ans)[::-1][0:K]:
	print(i)

### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

X, Y, Z, K = MAP()
A = LIST()
B = LIST()
C = LIST()

A=sorted(A)[::-1]
B=sorted(B)[::-1]
C=sorted(C)[::-1]
ans = []
for i in range(len(A)):
	for j in range(len(B)):
		for k in range(len(C)):
			if (i+1)*(j+1)*(k+1) <= K:
				ans.append(A[i]+B[j]+C[k])
			else:
				break
for i in sorted(ans)[::-1][0:K]:
	print(i)
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for x in range(0,k+1):
        for y in range(0,k+1):
                z = s - x - y
                #print("{} {} {}".format(x, y, z))
                if  0 <= z <= k and x + y + z == s:
                        count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for i in range(0, k+1):
        for j in range(0, k+1):
                if 0 <= s-i-j <= k:
                        count += 1
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

n,m = [int(i) for i in readline().split()]
a = [int(sys.stdin.readline()) for i in range(m)]
dp = [1]*2 + [0]*(n-1)
mod = 1000000007
 
for i in range(1,m):
  if a[i]==a[i-1]+1:
    print(0)
    sys.exit()
  
for i in range(n-1):
  if i+1 in a:
    dp[i+2] = dp[i]
    dp[i+1] = 0
  else:
    dp[i+2] = dp[i]+dp[i+1]

print(dp[-1]%mod)  


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
hole = [0]*(n+1)
for i in range(m):
  hole[int(input())] = 1

dp = [0]*(n+1)
dp[0] = 1
MOD = 10**9+7
   
for i in range(1,n+1):
  if hole[i]==1:
    dp[i] = 0
  else:
    dp[i] = dp[i-1]+dp[i-2]
    dp[i] %= MOD

print(dp[-1])
### BUGGY CODE ###

def ehand(n,a):
    for i in range(n):
        print max(a[:i]+a[(i+1):])
 
if __name__ == '__main__':
    n = int(raw_input())
    a = []
    a = [raw_input() for i in range(n)]
 
    ehand(n,map(int,a))

### FIXED CODE ###

import copy
def calcmax(a,b,fst,scd,n):
    for i in xrange(n):
        if fst == a[i]:
            count = i

    for i in xrange(n):
        if count == i:
            print scd
        else:
            print fst

if __name__ == '__main__':
    n = int(raw_input())
    a = [int(raw_input()) for i in xrange(n)]
    print("")

    fst = max(a)

    b = copy.deepcopy(a)
    b.remove(fst)

    scd = max(b)

    calcmax(a,b,fst,scd,n)
### BUGGY CODE ###

n, q = map(int, raw_input().split())
s = str(raw_input())
ans = []
arr = []
for i in range(n-1):
	if s[i:i+2] == 'AC':
		arr.append(1)
	else:
		arr.append(0)
for i in range(q):
	l, r = map(int, raw_input().split())
	count = sum(arr[l-1:r-1])
	ans.append(count)
for i in range(q):
	print ans[i]

### FIXED CODE ###

n, q = map(int, raw_input().split())
s = str(raw_input())
t = [0] * (n + 1)
for i in range(n):
	t[i + 1] = t[i] + (1 if s[i : i + 2] == 'AC' else 0)
for i in range(q):
	l, r = map(int, raw_input().split())
	print t[r-1] - t[l-1]