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

N=int(input())
A=list(map(int,input().split()))
D=[]
def factorization(N):
    temp={}
    while True:
        divided=False
        for i in range(2, int(N**0.5)+1):
            if N%i==0:
                if i in temp:
                    temp[i]+=1
                else:
                    temp[i]=1
                N=N//i
                divided=True
                break
        if not divided:
            temp[1]=1
            if N in temp:
                temp[N]+=1
            else:
                temp[N]=1
            break
    return temp
G={}
for a in A:
    b=factorization(a)
    D.append(b)
    for k in b.keys():
        if k in G:
            G[k]=max(G[k], b[k])
        else:
            G[k]=b[k]
ans=0
P=10**9+7
for i in range(len(A)):
    x=1
    b=D[i]
    for g in G:
        if g in b:
            x*=g**(G[g]-b[g])
        else:
            x*=g**(G[g])
    ans+=x
    ans%=P
print(ans)

### FIXED CODE ###

def gcd(a,b):
    if a>b:
        return gcd(b,a)
    if a==0:
        return b
    return gcd(b-a*(b//a),a)
def lcm(x,y):
    return (x*y)//gcd(x,y)
N=int(input())
A=list(map(int,input().split()))
s=1
for a in A:
    s=lcm(s,a)
ans=0
for a in A:
    ans+=s//a
print(ans%(10**9+7))
### BUGGY CODE ###

import math

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

t = (10 ** 9) + 7
n = n % t
A = (math.factorial(n) / (math.factorial(a) * math.factorial(n - a))) % t
B = (math.factorial(n) / (math.factorial(b) * math.factorial(n - b))) % t
ans = ((2 ** n) - 1 - A - B) % t
print(int(ans))

### FIXED CODE ###

def calc(n, x):
    up = 1
    bottom = 1
    for i in range(x):
        up *= (n - i)
        up = up % mod
        bottom *= (i + 1)
        bottom = bottom % mod
    return (up * pow(bottom, mod - 2, mod)) % mod

mod = (10 ** 9) + 7

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

ans = pow(2, n, mod) - 1
for i in [a, b]:
    ans -= calc(n, i)
print(ans % mod)
### BUGGY CODE ###

# DP
N, W = map(int, input().split())

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


### FIXED CODE ###

n, w = [int(e) for e in input().split()]
d = [[int(e) for e in input().split()] for i in range(n)]
t = {}
t[w] = 0
for i in range(n):
  keys = list(sorted(t.keys()))
  tw, tv = d[i]
  for j in keys:
    nw = j - tw
    if nw < 0:
      continue
    nv = t[j] + tv
    if nw in t:
      if nv > t[nw]:
        t[nw] = nv
    else:
      t[nw] = nv
print(max(t.values()))
### BUGGY CODE ###

n, q = map(int, input().split())
A = [set([]) for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    A[a].add(b)
    A[b].add(a)
S = [1]
while S:
    a_1 = S[0]
    for a_2 in A[a_1]:
        A[a_2] -= {a_1}
        S += a_2,
    S.pop(0)
C = [0]*(n+1)
for _ in range(q):
    p_1, x = map(int, input().split())
    C[p_1] += x
    T = [p_1]
    while T:
        p_1 = T[0]
        for p_2 in A[p_1]:
            C[p_2] += x
            T += p_2,
        T.pop(0)
print(*C[1:])

### FIXED CODE ###

n, q = map(int, input().split())
A = [set([]) for _ in range(n+1)]
for _ in range(n-1):
    a, b = map(int, input().split())
    A[a].add(b)
C = [0]*(n+1)
for _ in range(q):
    p, x = map(int, input().split())
    C[p] += x
for i in range(1, n+1):
    c = C[i]
    for a in A[i]:
        C[a] += c
print(*C[1:])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
k = []
for _ in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    k.append((a, sum([2 ** (i-1) for i in c])))

C = 2 ** n
INF = 10 ** 6

dp = [[INF for _ in range(C)] for __ in range(m + 1)]
for i in range(m+1):
    dp[i][0] = 0

for i, ki in enumerate(k):
    for j in range(C):
        dp[i+1][j] = dp[i][j]
    for j in range(C):
        dp[i+1][j | ki[1]] = min(dp[i+1][j | ki[1]], dp[i][j] + ki[0])

ans = dp[m][C-1]
if ans == INF:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
k = []
for _ in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    k.append((a, sum([2 ** (i-1) for i in c])))

C = 2 ** n
INF = 10 ** 6

dp = [[INF for _ in range(C)] for __ in range(m + 1)]
for i in range(m+1):
    dp[i][0] = 0

for i, ki in enumerate(k):
    for j in range(C):
        dp[i+1][j] = dp[i][j]
    for j in range(C):
        dp[i+1][j | ki[1]] = min(dp[i+1][j | ki[1]], dp[i][j] + ki[0])

ans = dp[m][C-1]
if ans == INF:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

from bisect import bisect_left

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

first = max(s)
made = [first]
s.remove(first)
s.append(0)
s.sort()

for _ in range(n):
    made_now = []
    for e in made:
        i = bisect_left(s, e)
        make = s.pop(i - 1)
        if make == 0:
            print("No")
            exit()
        made_now.append(make)

    made += made_now

print("Yes")


### FIXED CODE ###

from heapq import heappush, heappop
from copy import deepcopy

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

left = []
for e in s:
    heappush(left, -e)
mx = heappop(left)

made = []
heappush(made, mx)

for _ in range(n):
    made_nxt = deepcopy(made)
    tmp = []

    while made:
        made_val = heappop(made)
        while left and left[0] <= made_val:
            pp = heappop(left)
            tmp.append(pp)

        if not left:
            print("No")
            exit()

        left_val = heappop(left)
        heappush(made_nxt, left_val)

    made = made_nxt

    for e in tmp:
        heappush(left, e)

print("Yes")
### BUGGY CODE ###

def resolve():
  N, K = map(int, input().split(" "))
  A = [int(x) - 1 for x in input().split(" ")]

  history = []
  current = 0
  if K < N:
    for i in range(K):
      current = A[current]
    print(current + 1)
    return True
  else:
    while True:
      history.append(current)
      current = A[current]
      if current in history:
        loop_length = len( history[history.index(current):] )
        if loop_length == 0:
          print(current + 1)
          return True

        length_to_loop = len( history[:history.index(current)] )
        additional_way = (K-length_to_loop)%loop_length
        print(history[length_to_loop + additional_way] + 1)
        return True

if __name__ == "__main__":
    resolve()

### FIXED CODE ###

def resolve():
  N, K = map(int, input().split(" "))
  A = [int(x) - 1 for x in input().split(" ")]

  current = 0
  if K < N:
    for i in range(K):
      current = A[current]
    print(current + 1)
    return True
  else:
    history = [False] * N
    load_map = []
    while True:
      load_map.append(current)
      current = A[current]
      if history[current]:
        loop_length = len( load_map[load_map.index(current):] )
        if loop_length == 0:
          print(current + 1)
          return True

        length_to_loop = len( load_map[:load_map.index(current)] )
        additional_way = (K-length_to_loop)%loop_length
        print(load_map[length_to_loop + additional_way] + 1)
        return True
      else:
        history[current] = True

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

import sys
input = sys.stdin.readline

k,q = map(int,input().split())
d_array = list(map(int,input().split()))

ans_array = []
for _ in range(q):
    n, x, m = map(int,input().split())
    d_mod_array = [d % m for d in d_array]
    d_sum = sum(d_mod_array)
    mod_total = x % m + d_sum * ((n-1) // k) + sum(d_mod_array[:(n-1)%k])
    reduce_total = mod_total // m

    zero_count = d_mod_array.count(0)
    zero_total = zero_count * ((n-1) // k) + d_mod_array[:(n-1)%k].count(0)
    ans = (n-1) - reduce_total - zero_total
    ans_array.append(str(ans))

print("\n".join(ans_array))



### FIXED CODE ###

import sys
input = sys.stdin.readline

k,q = map(int,input().split())
d_array = list(map(int,input().split()))

ans_array = []
for _ in range(q):
    n, x, m = map(int,input().split())
    d_mod_array = [d % m for d in d_array]
    d_sum = 0
    d_part = 0
    zero_count = 0
    zero_part = 0
    part = (n-1) % k
    for i,d in enumerate(d_mod_array):
        d_sum += d
        if i < part:
            d_part += d
        if d == 0:
            zero_count += 1
            if i < part:
                zero_part += 1
    mod_total = x % m + d_sum * ((n-1) // k) + d_part
    reduce_total = mod_total // m

    zero_total = zero_count * ((n-1) // k) + zero_part
    ans = (n-1) - reduce_total - zero_total
    ans_array.append(str(ans))

print("\n".join(ans_array))
### BUGGY CODE ###

import copy
N, M, K = map(int, input().split())
tomodachi  = [ [i] for i in range(N+1)]
for _ in range(M):
  a, b  = map(int, input().split())
  tomodachi[a].append(b)
  tomodachi[b].append(a)
dupli = copy.deepcopy(tomodachi)

for n in range(1, N+1):
  kouho = set()
  for friend in tomodachi[n]:
    if friend == n:
      continue
    else:
      kouho.add(friend)
  while kouho:
    f = kouho.pop()
    for g in tomodachi[f]:
      if g in tomodachi[n]:
        continue
      else:
        kouho.add(g)
        tomodachi[n].append(g)


for _ in range(K):
  c, d  = map(int, input().split())
  if c in tomodachi[d]:
    tomodachi[d].remove(c)
    tomodachi[c].remove(d)

ans = [ str(len(t)-len(s)) for s, t in zip(dupli[1:], tomodachi[1:]) ]
print(' '.join(ans))

### FIXED CODE ###

import copy
N, M, K = map(int, input().split())

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
      
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

uf = UnionFind(N+1)

not_uf = [set() for _ in range(N+1)]
for _ in range(M):
  a, b = map(int, input().split())
  not_uf[a].add(b)
  not_uf[b].add(a)
  uf.union(a, b)

for _ in range(K):
  c, d = map(int, input().split())
  if uf.same(c, d):
    not_uf[c].add(d)
    not_uf[d].add(c)

for i in range(1, N+1):
  print(uf.size(i)-len(not_uf[i])-1)
### BUGGY CODE ###

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

now = 1
for i in range(k):
    now *= a[i]

for i in range(k,n):
    prv = now
    now *= a[i]
    now /= a[i-k]
    if prv < now:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

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

for i in range(k,n):
    if a[i] > a[i-k]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

from collections import deque

N, D, A = map(int, input().split())
XH = [0]*N
count = 0
for i in range(N):
    XH[i] = list(map(int, input().split()))
XH.sort()
XHd = deque(XH)
while len(XHd) > 0:
    if XHd[0][1] > 0:
        for i in range(len(XHd)):
            if XHd[i][0] <= XHd[0][0] + 2* D:
                XHd[i][1] -= A
        count += 1
    else:
        XHd.popleft()
print(count)

### FIXED CODE ###

from math import ceil
from collections import deque
count = 0
ans = 0

N, D, A = map(int, input().split())
Monster = [0]*N
for i in range(N):
    Monster[i] = list(map(int, input().split()))
Monster = [[x, ceil(h/A)] for x, h in Monster]
Monster.sort()
que = deque([])

for x,h in Monster:
    # 範囲外となったダメージを削除する
    while que and x > que[0][0]:
        a, b = que.popleft()
        count -= b
    # 範囲内で既に起きたダメージを受ける
    need = max(0, h-count)
    ans += need
    count += need
    # 爆発が届く限界と起きた回数を記録しておく
    que.append([x + 2*D, need])
print(ans)
### BUGGY CODE ###

import numpy as np

a=int(input())
b=list(map(int,input().split()))
b=2*np.array(b)
c=[[0 for s in range(a)] for _ in range(a)]
aa=0
for i in c:
    if aa==a-1:
        i[0]=1
        i[aa]=1
    else:
        i[aa+1]=1
        i[aa]=1
    aa+=1
c=np.array(c)

x=np.linalg.solve(c,b)
x=list(x)
for j in range(len(x)):
    x[j]=int(x[j])
print(" ".join(repr(e) for e in x))


### FIXED CODE ###

a=int(input())
b=list(map(int,input().split()))
c=sum(b[::2])-sum(b[1::2])
d=[c]
for i in b:
    d.append(2*i-c)
    c=2*i-c

d.pop()
print(*d)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    plus = False
    for a in A:
        if a>0:
            plus = True
            break

    A.sort(reverse=True)

    if K%2==1 and plus==False:
        ans = 1
        for i in A[:K]:
            ans *= i % MOD
        ans %= MOD
    else:
        A = deque(A)
        ans = 1
        if K%2==1:
            ans *= A.popleft()
        for _ in range(K//2):
            if A[0]*A[1]>=A[-1]*A[-2]:
                ans *= A.popleft()*A.popleft()%MOD
            else:
                ans *= A.pop() * A.pop() % MOD
        ans %= MOD

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.buffer.readline
read = sys.stdin.read
from collections import deque
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

def main():
    n, k = map(int, readline().split())
    A = list(map(int, readline().split()))
    MOD = int(1e9) + 7
    A.sort()
    ans = 1
    if A[n - 1] == 0 and (k & 1):
        ans = 0
    elif A[n - 1] <= 0 and (k & 1):
        for i in range(n - 1, n - k - 1, -1):
            ans = (ans * A[i]) % MOD
    else:
        i = 0
        j = n - 1
        if k & 1:
            ans = (ans * A[j]) % MOD
            j -= 1
            k -= 1
        k >>= 1
        for itr in range(k):
            left_product = A[i] * A[i + 1]
            right_product = A[j] * A[j - 1]
            if left_product > right_product:
                ans = (ans * left_product) % MOD
                i += 2
            else:
                ans = (ans * right_product) % MOD
                j -= 2

    print(ans % MOD)

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

N, M = map(int, input().split())
ans = 0
while N >= 1 and M >= 2:
	N -= 1
	M -= 2
	ans += 1
while M >= 4:
	M -= 4
	ans += 1
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
n = min(N, M //2)
m = max((M - 2 * N) // 4, 0)
print(n + m)
### BUGGY CODE ###

from itertools import*
n, k = map(int, input().split())
a, b = divmod(n, k)
t = 0 if k%2 else a + (b >= k//2)
j = lambda i: len(list(product(range(i), repeat=3)))
print(j(a)+j(t))

### FIXED CODE ###

n,k=map(int,input().split())
print((n//k) ** 3 + (k%2 == 0) * ((n + k//2) // k) ** 3)
### BUGGY CODE ###

N = int(input())
Ps = list(map(int,input().split()))
count = N
for i in range(N+1):
  P = Ps[i-1]
  for j in range(i):
    if P > Ps[j]:
      count=count-1
      break
      
print(count)

### FIXED CODE ###

N = int(input())
Ps = list(map(int,input().split()))
count = 0
y = Ps[0]
for i in range(N):
  y = min(Ps[i],y)
  if y == Ps[i]:
    count=count+1
      
print(count)
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

    for max_w in range(W+1):
        for i, (w, v) in enumerate(items):
            if max_w - w >= 0:
                dp[i+1][max_w] = max(dp[i][max_w], dp[i][max_w-w] + v)
            else:
                dp[i+1][max_w] = dp[i][max_w]
    print(dp[N][W])

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    N, W = map(int, input().split())
    items = [tuple(map(int, input().split())) for _ in range(N)]

    dp = [[0 for _ in range(W+1)] for _ in range(N+1)]

    for max_w in range(W+1):
        for i, (w, v) in enumerate(items):
            if max_w - w >= 0:
                dp[i+1][max_w] = max(dp[i][max_w], dp[i][max_w-w] + v)
            else:
                dp[i+1][max_w] = dp[i][max_w]
    print(dp[N][W])

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

#C - Attention
N = int(input())
S = input()
DP = []
tmpw = 0
tmpe = 0
ans = 10**9
for i in range(N):
    tmpw = S[:i].count('W')
    tmpe = S[i+1:].count('E')
    if ans >= tmpe+tmpw:
        ans = tmpe+tmpw
    else:
        pass

print(ans)

### FIXED CODE ###

#C - Attention
N = int(input())
S = input()
DP_w= []
DP_e = []
tmp = 0
tmpw = 0
tmpe = 0
ans = 10**9
for i in range(N):
    if S[i] == "W":
        tmpw += 1
        DP_w.append(tmpw)
    else:
        DP_w.append(tmpw)

for j in range(N-1,-1,-1):
    if S[j] == "E":
        tmpe += 1
        DP_e.append(tmpe)
    else:
        DP_e.append(tmpe)

DP_e.reverse()
for k in range(N):
    ans = min(ans,DP_w[k]+DP_e[k]-1)

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

import collections

N=int(input())
S=[]
for i in range(N):
    S.append(sorted(input()))

ans = 0
for j in range(N-1):
    for k in range(j+1, N):
        if (S[j]== S[k]):
            ans += 1

print(ans)


### FIXED CODE ###

N = int(input())

S = []
for i in range(N):
    S.append(input())

count = {}
ans = 0

for s in S:
    s=str(sorted(s))
    if s in count:
        count[s] += 1
    else:
        count[s] = 1

ans = 0
for c in count.values():
    ans += c*(c-1)//2
print(ans)
### BUGGY CODE ###

from collections import Counter

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

def nck(n, k): 
    C = [[0 for x in range(k+1)] for x in range(n+1)] 
  
    # Calculate value of Binomial Coefficient in bottom up manner 
    for i in range(n+1): 
        for j in range(min(i, k)+1): 
            # Base Cases 
            if j == 0 or j == i: 
                C[i][j] = 1
  
            # Calculate value using previously stored values 
            else: 
                C[i][j] = C[i-1][j-1] + C[i-1][j] 
  
    return C[n][k] 

for i in range(len(A)):
    total =0
    m = Counter(A[:i] + A[i+1:])
    for key, value in m.items():
        total += nck(value, 2)

    # print(uniquethings*(uniquethings)//2)
    print(total)



### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split(" ")))
m = Counter(A)
def nck(n, k): 
    C = [[0 for x in range(k+1)] for x in range(n+1)] 
  
    # Calculate value of Binomial Coefficient in bottom up manner 
    for i in range(n+1): 
        for j in range(min(i, k)+1): 
            # Base Cases 
            if j == 0 or j == i: 
                C[i][j] = 1
  
            # Calculate value using previously stored values 
            else: 
                C[i][j] = C[i-1][j-1] + C[i-1][j] 
  
    return C

most_common,num_most_common = m.most_common(1)[0]
CHOOSE_MATRIX = nck(num_most_common, 2)
total = 0
for key, value in m.items():
        # if key == A[i]:
        #     continue
        # else:
    total += CHOOSE_MATRIX[value][2]


for i in range(len(A)):
    newtotal = total
    # m[A[i]] -= 1
    # for key, value in m.items():
    #     # if key == A[i]:
    #     #     continue
    #     # else:
    #     total += CHOOSE_MATRIX[value][2]
    # m[A[i]] += 1
    tosubtract = CHOOSE_MATRIX[m[A[i]]][2]
    newtotal -= tosubtract
    newtotal += CHOOSE_MATRIX[m[A[i]]- 1][2]
    print(newtotal)
    # print(uniquethings*(uniquethings)//2)
    # print(total)
### BUGGY CODE ###

import itertools, math, collections
H, W, K = [int(_) for _ in input().split()]
A = [[2 if _ == 'S' else 1 if _ == '.' else 0 for _ in input()]
     for _ in range(H)]
for i, j in itertools.product(range(H), range(W)):
    if A[i][j] == 2:
        break
Q = collections.deque([[i, j, 0]])
sH = set()
sW = set()
while Q:
    h, w, dist = Q.popleft()
    A[h][w] = 0
    sH.add(h)
    sW.add(w)
    if dist < K:
        for nh, nw in [[h - 1, w], [h + 1, w], [h, w - 1], [h, w + 1]]:
            if 0 <= nh < H and 0 <= nw < W and A[nh][nw]:
                Q += [[nh, nw, dist + 1]]
print(1 + min([
    math.ceil(_ / K)
    for _ in (min(sH), H - 1 - max(sH), min(sW), W - 1 - max(sW))
]))


### FIXED CODE ###

import itertools, math, collections, sys
input = sys.stdin.readline
H, W, K = [int(_) for _ in input().split()]
A = [input() for _ in range(H)]
for h in range(H):
    if 'S' in A[h]:
        w = A[h].index('S')
        break
visited = [[False] * W for _ in range(H)]
ans = min([h, H - 1 - h, w, W - 1 - w])
res = K - 1
Q = collections.deque([[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                       [h, w + 1, res]])
while Q:
    h, w, res = Q.popleft()
    if 0 <= h < H and 0 <= w < W and A[h][w] == '.' and not visited[h][w]:
        visited[h][w] = True
        ans = min([ans, h, H - 1 - h, w, W - 1 - w])
        if res:
            res -= 1
            Q += [[h - 1, w, res], [h + 1, w, res], [h, w - 1, res],
                  [h, w + 1, res]]
print(1 + math.ceil(ans / K))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

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

mem = {}
def rec(arr):
    if len(arr)==1:
        if arr[0] == 1:
            return [1]
        else:
            return False
    h = hash(tuple(arr))
    if h in mem:
        return mem[h]
    for i,a in reversed(list(enumerate(arr))):
        if i+1 == a:
            res = rec(arr[:i] + arr[i+1:])
            if res:
                res.append(i+1)
                mem[h] = res
                break
    else:
        mem[h] = False
    return mem[h]

ans = rec(B)
if ans:
    print(*ans,sep='\n')
else:
    print(-1)

### FIXED CODE ###

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

ans = []
while B:
    for i,a in reversed(list(enumerate(B))):
        if i+1 == a:
            ans.append(a)
            del B[i]
            break
    else:
        print(-1)
        exit()
print(*ans[::-1], sep='\n')
### BUGGY CODE ###

A, B = map(int, input().split())
answer = A
for i in range(A+1, B+1):
  answer ^= i
print(answer)

### FIXED CODE ###

A,B = map(int, input().split())
def f(n):
    if n % 4 == 0:
        return n
    elif n % 4 == 1:
        return 1
    elif n % 4 == 2:
        return n ^ (n-1) ^ (n-2)
    elif n % 4 == 3:
        return 0
print(f(A-1) ^ f(B))
### BUGGY CODE ###

if __name__ == "__main__":
    N = int(input())
    A = []
    for i in range(N):
        Ai = int(input())
        if Ai in A:
            A.remove(Ai)
        else:
            A.append(Ai)
    print(len(A))

### FIXED CODE ###

if __name__ == "__main__":
    N = int(input())
    #A = []
    d = {}
    for i in range(N):
        Ai = int(input())
        if Ai in d.keys():
            d[Ai] = not d[Ai]
        else:
            d[Ai] = True
    
    ans = 0
    for item in d.items():
        if item[1]:
            ans += 1
    
    print(ans)
### BUGGY CODE ###

n,q = map(int,input().split())
s = input()
s = s.replace('AC','aC')
ac = []
for i in range(len(s)):
  if s[i] == 'a':
    ac.append(i)

lr = [tuple(map(int,input().split())) for _ in range(q)]
for i in range(q):
  cnt = 0
  for j in range(len(ac)):
    if lr[i][0]-1 <= ac[j] <= lr[i][1] - 2:
      cnt += 1
  print(cnt)

### FIXED CODE ###

n,q = map(int,input().split())
s = input()

ac = [0] * (n - 1)
for i in range(n-1):
  if s[i] == 'A' and s[i+1] == 'C':
    ac[i] = 1

acc = [0] * n
for i in range(n-1):
  acc[i+1] = acc[i] + ac[i]

lr = [tuple(map(int,input().split())) for _ in range(q)]
for i in range(q):
  l = lr[i][0] - 1
  r = lr[i][1] - 1
  print(acc[r] - acc[l])