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

import sys
input = sys.stdin.readline
from fractions import gcd

N=int(input())
a_list = list(map(int, input().split()))
MOD = 10**9+7


def cal_lcm(a, b):
  return int(a*b//gcd(a,b))


lcm = 1
ans = 0
for i in range(N):
  lcm_ = cal_lcm(lcm, a_list[i])
  ans = ans*(lcm_//lcm) % MOD
  ans = (ans + (lcm_//a_list[i])) % MOD
  lcm = lcm_

print(ans)

### FIXED CODE ###

from fractions import gcd
 
N=int(input())
a_list = tuple(int(i) for i in input().split())
MOD = 10**9+7

def cal_lcm(a, b):
  return int(a*b//gcd(a,b))

lcm = 1
for i in range(N):
  lcm = cal_lcm(lcm, a_list[i])
  
ans = 0
for i in range(N):
  ans += lcm//a_list[i]
print(ans%MOD)
### BUGGY CODE ###

n = int(input())
a_lst = [int(elem) for elem in input().split()]

cnt = 0
for i in range(n):
    if i+a_lst[i] < n-1:
        for j in range(n-1, i+a_lst[i], -1):
            if (j-i) == a_lst[i] + a_lst[j]:
                cnt += 1
print(cnt)


### FIXED CODE ###

n = int(input())
a_lst = [int(elem) for elem in input().split()]

dic = {}
for i in range(n):
    if not i - a_lst[i] in dic:
        dic[i - a_lst[i]] = 1
    else:
        dic[i - a_lst[i]] += 1
        
cnt = 0
for j in range(n):
    if j + a_lst[j] in dic:
        cnt += dic[j + a_lst[j]]

print(cnt)
### BUGGY CODE ###

from operator import itemgetter
import bisect


class DualSegmentTree():
 
    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)
 
    def update(self, begin, end, val, k=0, l=0, r=-1):
        if 2*self.size - 1 <= k:
            return
        if r < 0:
            r = self.size
        if begin <= l and r <= end:
            self.node[k] = min(val, self.node[k])
        self.update(begin, end, val, 2*k+1, l, (l+r)//2)
        self.update(begin, end, val, 2*k+2, (l+r)//2, r)

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n)]
d = [int(input()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)

### FIXED CODE ###

import sys
import bisect


class DualSegmentTree():

    def __init__(self, n):
        INF = float("inf")
        self.size = 1
        while self.size < n:
            self.size *= 2
        self.node = [INF] * (2*self.size - 1)

    def update(self, begin, end, val):
        begin += (self.size - 1)
        end += (self.size - 1)
        while begin < end:
            if (end - 1) & 1:
                end -= 1
                self.node[end] = min(val, self.node[end])
            if (begin - 1) & 1:
                self.node[begin] = min(val, self.node[begin])
                begin += 1
            begin = (begin - 1) // 2
            end = (end - 1) // 2

    def get_val(self, i):
        i += (self.size - 1)
        val = self.node[i]
        while i > 0:
            i = (i - 1) // 2
            val = min(val, self.node[i])
        return val

n, q = map(int, input().split())
info = [list(map(int, sys.stdin.readline().split())) for i in range(n)]
d = [int(sys.stdin.readline()) for i in range(q)]
INF = float("inf")

st = DualSegmentTree(len(d)+1)

for i in range(n):
    a, b = info[i][0] - info[i][2], info[i][1] - info[i][2]  
    l = bisect.bisect_left(d, a)
    r = bisect.bisect_left(d, b)
    st.update(l, r, info[i][2])

for i in range(q):
    tmp = st.get_val(i)
    if tmp == float("inf"):
        print(-1)
    else:
        print(tmp)
### BUGGY CODE ###

import math
from functools import reduce


def gcd(*numbers):
    return reduce(math.gcd, numbers)


K = int(input())
sum = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            sum += gcd(i, j, k)
print(sum)

### FIXED CODE ###

import math


K = int(input())
sum = 0
for i in range(1, K+1):
    for j in range(1, K+1):
        i_j = math.gcd(i, j)
        for k in range(1, K+1):
            sum += math.gcd(i_j, k)
print(sum)
### BUGGY CODE ###

import math
MOD = 10**9 + 7
def cc(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))
n = int(input())
a = list(map(int, input().split()))
for i in range(n):
    a[i] = format(a[i], '060b')
s = 0
for i in range(60):
    c0 = 0
    c1 = 0
    for j in range(n):
        if a[j][i] == '0':
            c0 += 1
        else:
            c1 += 1
    s += 2**(59-i)*c0*c1%MOD
    s %= MOD
print(s)

### FIXED CODE ###

MOD = 10**9 + 7
n = int(input())
a = list(map(int, input().split()))
s = 0
m = 1
for i in range(60):
    c = sum(ai & m for ai in a)
    c //= m
    s = (s + m*c*(n-c))%MOD
    m <<= 1
print(s)
### BUGGY CODE ###

N,M=map(int,input().split())
List = []
for i in range (M):
  List.append(list(map(int, input().split())))
resList = [1]*N
for i in range(M):
  if List[i][0] > 1:
    for j in range(0,List[i][0]-1):
      if resList[j] == 1:
        resList[j] = 0
  if List[i][1] < N:
    for k in range(List[i][1],N):
      if resList[k] == 1:
        resList[k] = 0
print(resList.count(1))

### FIXED CODE ###

N,M=map(int,input().split())
List = []
for i in range (M):
  List.append(list(map(int, input().split())))
resList = [0]*N
for i in range(M):
  resList[List[i][0]-1] +=1
  if List[i][1]<N:
    resList[List[i][1]] +=-1
for j in range(1,N):
  resList[j] = resList[j] + resList[j-1]
print(resList.count(M))
### BUGGY CODE ###

from math import floor

r, g, b, n = map(int, input().split())

cnt = 0
for r0 in range(floor(n // r)+1):
  for g0 in range(floor(n // g)+1):
    sum = r * r0 + g * g0
    if sum > n:
      continue
    if (n - sum) % b == 0:
      cnt += 1

print(cnt)
      

### FIXED CODE ###

from math import floor

r, g, b, n = map(int, input().split())
r, g, b = sorted([r, g, b])[::-1]

cnt = 0
for r0 in range(floor(n // r)+1):
  for g0 in range(floor((n-r*r0)// g)+1):
    sum = r * r0 + g * g0
    if sum > n:
      continue
    if (n - sum) % b == 0:
      cnt += 1

print(cnt)
### BUGGY CODE ###

from bisect import insort_left
N, M=map(int, input().split())
A=[]
Y=[[] for _ in range(N)] #県
for i in range(M):
  p,y=map(int, input().split())
  A.append((p,y))
  Y[p-1].append(y)
  Y[p-1].sort()


for i in range(M):
  p,y=A[i]
  y=str(Y[p-1].index(y)+1)
  p=str(p)
  ans="0"*(6-len(p))+p+"0"*(6-len(y))+y
  print(ans)

### FIXED CODE ###


N, M=map(int, input().split())
#A=[]
Y=[[] for _ in range(N)] #県
for i in range(M):
  p,y=map(int, input().split())
  #A.append((p,y))
  Y[p-1].append([y,i+1])

for i in range(N):
  if Y[i]:
    Y[i].sort(key=lambda x: x[0])
#indexは時間かかる
ans=[]
for i in range(N):
  for j,L in enumerate(Y[i]):
    p,y,n=i+1, L[0],L[1]
    ans.append((n,p,j+1))
ans=sorted(ans)
for n,p,y in ans:
  a=(6-len(str(p)))*"0"+str(p)+(6-len(str(y)))*"0"+str(y)
  print(a)
### BUGGY CODE ###

N = input()
N = int(N)

l = input().split(" ")
l = [int(n0) for n0 in l]

# print(l)

l.append(10**10)

ans = 0

for xi in range(N-1):
    step = l[xi]
    count = 0
    while step >= l[xi+count+1] :
        step = l[xi+count+1]
        count = count +1
    if ans < count:
        ans = count

print(ans)


### FIXED CODE ###

n = int(input())
h = [int(xi) for xi in input().split()]

step = 0
mstep = 0
for xi in range(n-1):
    if h[xi] >= h[xi+1]:
        step += 1
    else:
        if mstep<step:
            mstep = step
        step = 0

if mstep<step:
    mstep = step

print(mstep)
### BUGGY CODE ###

S = input()

count = 0
for i in range(len(S)-4):
    for j in range(i+4, len(S)):
        x = int(S[i:j+1])
        if x % 2019 == 0:
            count += 1

print(count)

### FIXED CODE ###

S = input()
digits = list(map(int,S))
# S = S[::-1]→これが時間かかる

# i~nまでの値をmod2019したときの数
# ls = [0for i in range(2019)]
ls = [0] * 2019

# 0文字の時
ls[0] += 1

x = 0
pow10 = 1
count = 0
for i in reversed(digits):
    x += i*pow10
    x %= 2019
    count += ls[x]
    ls[x] += 1
    pow10 *= 10
    pow10 %= 2019

# for x in ls:
#     count += x*(x-1)/2

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

'''
Created on 2020/08/17

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N=int(pin())
  P=list(map(int,pin().split()))
  ans=0
  for i in range(N):
    if min(P[:i+1])==P[i]:
      ans+=1
  print(ans)
  return 

main()

### FIXED CODE ###

'''
Created on 2020/08/17

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N=int(pin())
  P=list(map(int,pin().split()))
  ans=0
  m=P[0]
  for i in range(N):
    if m>=P[i]:
      m=P[i]
      ans+=1
  print(ans)
  return 

main()
### BUGGY CODE ###

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

ans = 1
tmp = P
start = P // (2 ** N) + 1
# for i in range(start, 1, -1):
#     newtmp, rest = divmod(tmp, (i**N))
#     print(i, tmp, rest, ans)
#     if rest == 0:
#         ans = ans * i
#         tmp = newtmp

for i in range(2, P):
    while True:
        newtmp, rest = divmod(tmp, (i**N))
        # print(i, tmp, rest, ans)
        if rest == 0:
            ans = ans * i
            tmp = newtmp
        else:
            break
    if newtmp == 0:
        break

print(ans)


### FIXED CODE ###

N, P = list(map(int, input().split()))
if N == 1:
    print(P)
    exit()
elif P == 1:
    print("1")
    exit()

ans = 1
tmp = P

for i in range(2, int(pow(P, 1 / N)) + 1):
    po = pow(i, N)
    while tmp % po == 0:
        tmp = tmp // po
        ans = ans * i
        # print(i, tmp, ans)

    if tmp < po:
        break

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


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

# 同じ年に誕生した市は存在しないので，誕生年を識別値にする
city = {}
ord_list = []

for m in range(M):
	pf, ordr = map(int, input().split(" "))

	if pf not in city:
		city[pf] = []

	city[pf].append(ordr)
	ord_list.append(ordr)

for i in ord_list:
	for k, vs in city.items():
		# 順序づけ
		vs = sorted(vs, key=lambda v: int(v))
		for index, v in enumerate(vs):
			if v == i:
				
				ans_city = [x for x in reversed(list(str(k)))]
				while len(ans_city) < 6:
					ans_city.append('0')
				
				ans_ord = [x for x in reversed(list(str(index + 1)))]
				while len(ans_ord) < 6:
					ans_ord.append('0')

				
				ans = ans_ord + ans_city
				print("".join(reversed(ans)))
			

### FIXED CODE ###

n,m = map(int, input().split())
l = [[] for _ in range(n)]
for i in range(m):
    p,y = map(int, input().split())
    l[p-1].append((y, i))
ans = [None]*m
for i,pre in enumerate(l):
    pre.sort()
    for j,(a,b) in enumerate(pre):
        ans[b] = "{:0>6}{:0>6}".format(i+1,j+1)
print("\n".join(ans))
### BUGGY CODE ###

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

ans=0
for i in range(n-1):
  for j in range(i+1, n):
    ans+=(a[i]*a[j])
print(ans%(10**9+7))

### FIXED CODE ###

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

s=sum(a)
ans=0
for i in range(n-1):
  s-=a[i]
  ans+=s*a[i]
print(ans%(10**9+7))
### BUGGY CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())

b = [i for i in A]
for _ in range(K):
    buf = [0]*(N+1)
    for i, j in enumerate(b):
        buf[max(i-j, 0)] += 1
        buf[min(i+j+1, N)] -= 1
    for i in range(1, N+1):
        buf[i] += buf[i-1]
    b = [buf[i] for i in range(N)]

print(*b)

### FIXED CODE ###

N, K = map(int, input().split())
*A, = map(int, input().split())

b = [i for i in A]
for c in range(K):
    buf = [0]*(N+1)
    for i, j in enumerate(b):
        buf[max(i-j, 0)] += 1
        buf[min(i+j+1, N)] -= 1
    for i in range(1, N+1):
        buf[i] += buf[i-1]
    b = [buf[i] for i in range(N)]
    if all([i==N for i in b]):
        break

print(*b)
### BUGGY CODE ###

n,*s=map(int,open(0).read().split());s,t,f,g=[s[i*n:i*n+n]for i in range(4)];r=range(n);a=[n*[0]for _ in r];e=enumerate
for b in range(64):
 y=1<<b;u=[k&y for k in f];v=[k&y for k in g];l=[0]*n;m=l[:]
 for i,k in e(u):
  for j,h in e(v):
   if(k&h)|((s[i]^1)*k)|((t[j]^1)*h):a[i][j]|=y;l[i]+=1;m[j]+=1
 for i in r:
  for j in r:
   if(l[i]==0)*s[i]*u[i]*(t[j]^1)*(n-m[j]>1):a[i][j]|=y;m[j]+=1;break
  for j in r:
   if(m[i]==0)*t[i]*v[i]*(s[j]^1)*(n-l[j]>1):a[j][i]|=y;l[j]+=1;break
h=a[0][:];w=[i[0]for i in a]
for i,k in e(a):
 for j,l in e(k):w[i]=(l|w[i]if s[i]else w[i]&l);h[j]=(l|h[j]if t[j]else h[j]&l)
if(g!=h)|(f!=w):print(-1);exit() 
for i in a:print(*i)


### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
t=list(map(int,input().split()))
u=list(map(int,input().split()))
v=list(map(int,input().split()))
ans=[n*[0]for _ in range(n)]
ss=[u[i]if s[i]==0 else 0 for i in range(n)]
tt=[v[i]if t[i]==0 else 0 for i in range(n)]
son=[[]for _ in range(n)]
ton=[[]for _ in range(n)]
sno=[[n-1]*64 for _ in range(n)]
tno=[[n-1]*64 for _ in range(n)]
for i in range(n):
  for j in range(n):
    ans[i][j]=u[i]&v[j]
    if s[i]==0:
      ans[i][j]|=u[i]
      ss[i]&=ans[i][j]
    else:
      ss[i]|=ans[i][j]
    if t[j]==0:
      ans[i][j]|=v[j]
      tt[j]&=ans[i][j]
    else:
      tt[j]|=ans[i][j]
    if s[i]==0 or t[i]==0:
      for k in range(64):
        if ans[i][j]&1<<k:
          if s[i]==0:sno[i][k]-=1
          if t[j]==0:tno[j][k]-=1
    if j==n-1:
      if s[i]==1:
        if ss[i]|u[i]>u[i]:print(-1);exit()
        if ss[i]!=u[i]:
          for k in range(64):
            if u[i]&1<<k:
              if (ss[i]&1<<k)==0:
                son[i].append(k)
          ss[i]=1
        else:ss[i]=0
      else:
        if ss[i]!=u[i]:print(-1);exit()
        else:ss[i]=2
    if i==n-1:
      if t[j]==1:
        if tt[j]|v[j]>v[j]:print(-1);exit()
        if tt[j]!=v[j]:
          for k in range(64):
            if v[j]&1<<k:
              if (tt[j]&1<<k)==0:
                ton[j].append(k)
          tt[j]=1
        else:tt[j]=0
      else:
        if tt[j]!=v[j]:print(-1);exit()
        else:tt[j]=2
for i in range(n):
  for k in son[i]:
    for j in range(n):
      if t[j]==0:
        if tno[j][k]>0:
          ans[i][j]|=1<<k
          tno[j][k]-=1
          break
      if j==n-1:print(-1);exit()
for j in range(n):
  for k in ton[j]:
    for i in range(n):
      if s[i]==0:
        if sno[i][k]>0:
          ans[i][j]|=1<<k
          sno[i][k]-=1
          break
      if i==n-1:print(-1);exit()
for i in range(n):
  if s[i]==0:uu=ans[i][0]
  else:uu=0
  for j in range(n):
    if s[i]==0:uu&=ans[i][j]
    else:uu|=ans[i][j]
  if uu!=u[i]:print(-1);exit()
for j in range(n):
  if t[j]==0:vv=ans[0][j]
  else:vv=0
  for i in range(n):
    if t[j]==0:vv&=ans[i][j]
    else:vv|=ans[i][j]
  if vv!=v[j]:print(-1);exit()
for i in ans:print(*i)
### BUGGY CODE ###

s = input()
q = int(input())
ans = 0

for i in range(q):
    c = list(map(str, input().split()))
    if c[0] == '1':
        ans +=1
    if c[0] == '2':
        if c[1] == '1' and ans%2 == 0 :
          s = c[2] + s
        if c[1] == '1' and ans%2 == 1 :
          s = s + c[2]
        if c[1] == '2' and ans%2 == 0:
          s = s + c[2]
        if c[1] == '2' and ans%2 == 1:
          s = c[2] + s

if ans%2 == 1:
  s = s[::-1]

print(s)

### FIXED CODE ###

s=input()
q=int(input())
f=""
b=""
r=0
for i in range(q):
  query=input().split()
  if int(query[0])==1:
    r=1-r
  else:
    if (r^(int(query[1])-1))==0:
      f+=query[2]
    else:
      b+=query[2]
ret=f[::-1]+s+b
if r:
  ret=ret[::-1]
print(ret)
### BUGGY CODE ###

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

mod = 10**9 +7
ans = 0
for i in range(n):
  ans += (sum(a[i+1:]) % mod) *a[i]
print(ans % mod)

### FIXED CODE ###

n = int(input())
a = tuple(map(int,input().split()))
t = 0
mod = 10**9 + 7
at = []
for j in range(1,n):
  t += a[n-j] % mod 
  at.append(t)

ans = 0
for i in range(n-1):
  ans += at[n-2-i] *a[i]
print(ans % mod)
### BUGGY CODE ###

import numpy as np
H,W=map(int, input().split())
F=[]
for h in range(H):
    a=list(input())
    F.append(a)

black=[]
white=[]
for h in range(H):
    for w in range(W):
        if F[h][w]=="#":
            black.append([h,w])
        else:
            white.append([h,w])
black=np.array(black)
white=np.array(white)
ans=0
#print(black, white)
for i in range(white.shape[0]):
    w=white[i,:].reshape(1,2)
    
    sub=np.abs(black-w).sum(axis=1).min()
    
    ans=max(sub, ans)
print(ans)

### FIXED CODE ###

from collections import deque
H,W=map(int, input().split())

A=[]
que=[]
done=[[-1]*W for _ in range(H)]
for h in range(H):
    a=list(input())
    A.append(a)
    for w in range(W):
        if a[w]=="#":
            que.append((h,w))
            done[h][w]=0

d=[(1,0),(-1,0),(0,1),(0,-1)]
que=deque(que)
ans=0
while que:
    h,w=que.popleft()
    now=done[h][w]
    for t in d:
        dh,dw=t
        nh=h+dh
        nw=w+dw
        if 0<=nh<H and 0<=nw<W:
            if done[nh][nw]==-1:
                done[nh][nw]=now+1
                que.append((nh,nw))
                ans=max(ans, now+1)



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

import sys
import itertools

def resolve(in_):
    N = int(next(in_))
    A = list(map(int, next(in_).split()))

    mod = 10 ** 9 + 7
    ans = 0
    for a, b in itertools.combinations(A, 2):
        ans += a * b
        ans %= mod

    return ans
    

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys


def resolve(in_):
    N = int(next(in_))
    A = tuple(map(int, next(in_).split()))

    mod = 10 ** 9 + 7
    ans = 0
    v = sum(A)
    for a in A:
        v -= a
        ans += a * v
        ans %= mod

    return ans
    

def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


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

n = int(input())
a = list(map(int, input().split()))
x = 1
for i in range(n):
    for j in range(x, n):
        if a[i] == a[j]:
            print("NO")
            quit()
    x += 1
    if x == n:
        print("YES")
        quit()

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = set(a)
if len(a) == len(b):
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

#nord_aで使っている色の＋１
#初期入力
import sys
input = sys.stdin.readline
#from collections import deque
import heapq
N = int(input())
connection   ={i:set() for i in range(1,N+1)}
A            =[[i] for i in range(N-1)]
A_sort =sorted(A)
for i in range(N-1):
    a,b = (int(x) for x in input().split())
    connection[a].add(b) # つながりを逆向きも含めて入力
    connection[b].add(a) # 
    A_sort[i].append((a,b))             #色を出力するため
A_sort.sort(key=lambda x:x[1])
#色の数(各頂点の最大値)
color_max =0
for i in connection.values():
    color_max =max(color_max, len(i) )

#各頂点に色を準備⇒辺の色決定
aa=[]
hq_none =heapq.heapify(aa)
color_node ={i:[] for i in range(1,N+1)} #頂点に使った色の管理,dequeで高速？
for i in range(1,N+1):
    heapq.heapify(color_node[i])
color_edge =[0]*(N-1)

for i in range(N-1):
    n_a,n_b = A_sort[i][1] #i番目の辺とつながっている頂点
    if color_node[n_a] ==[]:
        color =0
    else:
        color =(color_node[n_a][0]) -1
    while True:
        #color +=1
        q,color =divmod(color,(-1)*color_max)
        if color not in color_node[n_a] and color not in color_node[n_b]: 
            #color_edge[i] =color+1          #辺の色を出力用に決める。1～color_max
            A_sort[i].append((-1)*color+1)     #辺の色を出力用に決める。1～color_max,A_sortに入れて、再度ソート
            heapq.heappush(color_node[n_a],color)    #前の頂点に使った色を追加、
            heapq.heappush(color_node[n_b],color)    #heapqの最大値出したいので*(-1)

            break
        else:
            color -=1      
#出力
print(color_max)
A_sort.sort()
for i in A_sort:
    print(i[2])

### FIXED CODE ###

"""
参考    yy4さん 2019-11-24 21:24:43
516 ms          PyPy3 (2.4.0)
"""
#def solve():
from collections import deque
import sys

input = sys.stdin.readline

n = int(input())

g = tuple(set() for _ in range(n))
for idx in range(n - 1):
    a, b = (int(x) - 1 for x in input().split())
    g[a].add((b, idx))
    g[b].add((a, idx))

q = deque()
q.append((0, -1, -1))

e = [-1] * n  # e[-1]は使わない
used = [False] * n
used[0] = True
while q:
    v, v_idx, prev_color = q.popleft()
    curr = 1 if prev_color != 1 else 2
    for u, u_idx in g[v]:
        if used[u]:
            continue
        used[u] = True
        e[u_idx] = curr
        q.append((u, u_idx, curr))
        curr += 1
        if curr == prev_color:
            curr += 1

ret = e[:-1]
#return len(set(ret)), ret

    
#l, ret = solve()
l=len(set(ret))
print(l)
print(*ret, sep='\n')
### BUGGY CODE ###


N = int(input())
L = list(map(int, input().split()))
L.sort(reverse=True)

ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        for m in range(j+1,N):
            if L[i]<L[j]+L[m]:
                ans+=1
print(ans)

### FIXED CODE ###

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

'''
A=[]
B=[]
for i in range():
    a, b = map(int, input().split())
    A.append(a)
    B.append(b)'''


def sol(n,l):
    import bisect
    l.sort()
    ans = 0
    #print(l)
    for i in range(n-1):
        for j in range(i+1,n):
            ji = l[j]+l[i]
            ind = bisect.bisect_left(l,ji)
            #print(i,j,ind,ind-j-1)
            ans += ind-j-1
    return ans


def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    l = list(map(int, input().split()))
    print(sol(n,l))

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

# coding:utf-8

memo = []

def main():
    N,Q = map(int,input().split())
    S = input()
    for i in range(N-1):
        if S[i:i+2] == "AC":
            memo.append(i)
    # print(memo)
    for i in range(Q):
        li,ri = map(int,input().split())
        count = 0
        # 両方の範囲に入る最初と最後
        start = -1
        end = -1

        for i in range(len(memo)):
            if ac_check(i,li,ri):
                count+=1
        #         break

        # for i in reversed(range(len(memo))):
        #     if ac_check(i,li,ri):
        #         end = i
        #         break

        # print(start,end)
        # if start < 0 
        # count = end - start

        print(count)

def ac_check(i,li,ri):
    if memo[i] >= li-1 and memo[i]+1 <= ri-1:
        return True
    return False

# def ac_check(sub_s):
#     count = 0
#     for i in range(len(sub_s)-1):
#         if sub_s[i:i+2] == "AC":
#             count += 1
#     return count


if __name__ == "__main__":
    main()

### FIXED CODE ###

# coding:utf-8

memo = []

def main():
    N,Q = map(int,input().split())
    S = input()
    t = [0] *(N+1)
    for i in range(N):
        if S[i:i+2] == "AC":
            t[i+1] = t[i] + 1
        else:
            t[i+1] = t[i]
    # for i in range(N-1):
    #     if S[i:i+2] == "AC":
    #         memo.append(i)
    # print(memo)

    for i in range(Q):
        li,ri = map(int,input().split())
        print(t[ri-1] - t[li-1])
        # count = len(memo)
        # 両方の範囲に入る最初と最後
        # print(li,ri)
        # for i in range(li-1,ri-1):
        #     # print("debug"+str(i))
        #     if S[i] == "A" and S[i+1] == "C":
        #         count += 1
        #         start = i
        #         break
        # if start < 0:
        #     count = 0
        # else: 
        #     for i in reversed(range(li-1,ri+1)):
        #         if S[i-1] == "A" and S[i] == "C":
        #             end = i-1
        #             break
        #     print(start,end)
        #     count = memo.index(end) - memo.index(start) + 1


        # for i in range(len(memo)):
        #     if ac_check(i,li,ri):
        #         start = i
        #         break
        # if start < 0:
        #     count = 0
        # else:
        #     for i in reversed(range(len(memo))):
        #         if ac_check(i,li,ri):
        #             end = i
        #             break
        #     # print(start,end)
        #     count = count - (start) - (len(memo)-end) + 1
        # print(count)

# def ac_check(i,li,ri):
#     if memo[i] >= li-1 and memo[i]+1 <= ri-1:
#         return True
#     return False

# def ac_check(sub_s):
#     count = 0
#     for i in range(len(sub_s)-1):
#         if sub_s[i:i+2] == "AC":
#             count += 1
#     return count


if __name__ == "__main__":
    main()