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

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
import numpy as np
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

h,w = MI()
a = [list(input()) for i in range(h)]
d = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dist = [[-1]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            d.append([i,j])
            dist[i][j] = 0
while d:
    s = d.popleft()
    x= s[0]
    y= s[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        else:
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,dist[i][j])
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**7)
import bisect
import heapq
import itertools
import math
from collections import Counter, defaultdict, deque
from copy import deepcopy
from decimal import Decimal
from math import gcd
from operator import add, itemgetter, mul, xor
def cmb(n,r,mod):
  bunshi=1
  bunbo=1
  for i in range(r):
    bunbo = bunbo*(i+1)%mod
    bunshi = bunshi*(n-i)%mod
  return (bunshi*pow(bunbo,mod-2,mod))%mod
mod = 10**9+7
def I(): return int(input())
def LI(): return list(map(int,input().split()))
def MI(): return map(int,input().split())
def LLI(n): return [list(map(int, input().split())) for _ in range(n)]

h,w = MI()
a = [list(input()) for i in range(h)]
d = deque()
dx = [1,-1,0,0]
dy = [0,0,1,-1]
dist = [[-1]*w for _ in range(h)]
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            d.append([i,j])
            dist[i][j] = 0
while d:
    s = d.popleft()
    x= s[0]
    y= s[1]
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        if nx < 0 or ny < 0 or nx >= h or ny >= w:
            continue
        else:
            if dist[nx][ny] == -1:
                dist[nx][ny] = dist[x][y] + 1
                d.append([nx,ny])
ans = 0
for i in range(h):
    for j in range(w):
        ans = max(ans,dist[i][j])
print(ans)
### BUGGY CODE ###

def main():
    N,K=map(int,input().split())
    L=list(map(int,input().split()))
    LL=[]
    for i in range(0,N):
        for j in range(1,N-i):
            LL.append(L[i]*L[i+j])
    print(sorted(LL)[K-1])
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
N,K=map(int,input().split())
L=[int(i) for i in input().split()]
Pos = [x for x in L if x > 0]
Zero = [x for x in L if x == 0]
Neg = [x for x in L if x < 0]
Pos.sort()
Neg.sort(reverse=True)

Po = len(Pos)
Ne = len(Neg)
Ze= len(Zero)

ZeN = Ze*(Ze-1)//2 + Ze*(Po+Ne)
NeN = Po*Ne

if NeN<K<=NeN+ZeN:
    print(0)

else:
    def f(x):
        cnt = 0
        if x < 0:
            j = Po - 1
            for i in range(Ne):
                j=min(Po-1,j+1)
                while j >=0:
                    if Neg[i] * Pos[j] <= x:
                        j = j - 1
                    else:
                        break
                cnt = cnt + Po - j - 1
        else:
            j = 0
            for i in range(Po)[::-1]:
                j=max(0,j-1)
                while j < i:
                    if Pos[i]*Pos[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            j = 0
            for i in range(Ne)[::-1]:
                j = max(0, j - 1)
                while j < i:
                    if Neg[i]*Neg[j] <= x:
                        j = j+1
                    else:
                        break
                cnt = cnt+j

            cnt = cnt + ZeN + NeN
        return(cnt)

    Hi = 10**18
    Lo = -10**18

    while Hi-Lo > 1:
        Mid = (Hi + Lo) // 2
        if f(Mid) >= K:
            Hi = Mid
        else:
            Lo = Mid
    print(Hi)
### BUGGY CODE ###

n = int(input())
bra = []
ket = []
for _ in range(n):
  s = input()
  mini = 0
  now = 0
  l = len(s)
  for i in range(l):
    if s[i] == '(':
      now += 1
    else:
      now -= 1
      mini = min(mini,now)
  bra.append([-mini,now])
  s = s[::-1]
  mini = 0
  now = 0
  for i in range(l):
    if s[i] == ')':
      now += 1
    else:
      now -= 1
      mini = min(mini,now)
  ket.append([-mini,now])  
check = 0
for x in bra:
  #print(x)
  check += x[1]
if check != 0:
  print('No')
  exit()
bra.sort()
now = 0
here = -1
#print(bra)
import heapq
pool = []
for i in range(n):
  while here != n-1:
    if bra[here+1][0] <= now:
      here += 1
      heapq.heappush(pool,-bra[here][1])
    else:
      break
  #print(i,'#',pool)
  if not pool:
    print('No')
    exit()
  else:
    tmp = heapq.heappop(pool)
    now -= tmp
    if tmp > 0:
      break

ket.sort()
now = 0
here = -1
#print(bra)
pool = []
for i in range(n):
  while here != n-1:
    if ket[here+1][0] <= now:
      here += 1
      heapq.heappush(pool,-ket[here][1])
    else:
      break
  #print(i,'#',pool)
  if not pool:
    print('No')
    exit()
  else:
    tmp = heapq.heappop(pool)
    now -= tmp
    if tmp > 0:
      break
print('Yes')

### FIXED CODE ###

n = int(input())
bra = []
ket = []
c = []
for _ in range(n):
  s = input()
  mini = 0
  now = 0
  l = len(s)
  for i in range(l):
    if s[i] == '(':
      now += 1
    else:
      now -= 1
      mini = min(mini,now)
  if now >= 0:
    bra.append([-mini,now])
  c.append(now)
  s = s[::-1]
  mini = 0
  now = 0
  for i in range(l):
    if s[i] == ')':
      now += 1
    else:
      now -= 1
      mini = min(mini,now)
  if now >= 0:
    ket.append([-mini,now])  
check = 0
for x in c:
  #print(x)
  check += x
if check != 0:
  print('No')
  exit()
bra.sort()
now = 0
here = -1
n = len(bra)
#print(bra)
import heapq
pool = []
for i in range(n):
  while here != n-1:
    if bra[here+1][0] <= now:
      here += 1
      heapq.heappush(pool,-bra[here][1])
    else:
      break
  #print(i,'#',pool)
  if not pool:
    print('No')
    exit()
  else:
    now -= heapq.heappop(pool)

ket.sort()
now = 0
here = -1
n = len(ket)
#print(bra)
pool = []
for i in range(n):
  while here != n-1:
    if ket[here+1][0] <= now:
      here += 1
      heapq.heappush(pool,-ket[here][1])
    else:
      break
  #print(i,'#',pool)
  if not pool:
    print('No')
    exit()
  else:
    now -= heapq.heappop(pool)
print('Yes')
### BUGGY CODE ###

def main():
  import math
  import sys
  imput=sys.stdin.readline
  a=int(input())
  b=input()
  R=0
  L=0
  ans=1
  mod=10**9+7
  if b[0]=="W" or b[-1]=="W":
    print(0)
    exit()
  for i in range(2*a):
    if i==0:
      L+=1
      fr="L"
    else:
      if b[i]==b[i-1]:
        if fr=="L":
          ans=ans*(L-R)
          R+=1
          fr="R"
        else:
          L+=1
          fr="L"
      else:
        if fr=="L":
          L+=1
        else:
          ans=ans*(L-R)
          R+=1
    
  if L!=R:
    print(0)
    exit()


  
  print(ans*math.factorial(a)%mod)
  

if __name__ == '__main__':  
  main()
  

### FIXED CODE ###

def main():
  import math
  import sys
  imput=sys.stdin.readline
  a=int(input())
  b=input()
  R=0
  L=0
  ans=1
  mod=10**9+7
  if b[0]=="W" or b[-1]=="W":
    print(0)
    exit()
  for i in range(2*a):
    if i==0:
      L+=1
      fr="L"
    else:
      if b[i]==b[i-1]:
        if fr=="L":
          ans=ans*(L-R)%mod
          R+=1
          fr="R"
        else:
          L+=1
          fr="L"
      else:
        if fr=="L":
          L+=1
        else:
          ans=ans*(L-R)%mod
          R+=1
    
  if L!=R:
    print(0)
    exit()


  
  print(ans*math.factorial(a)%mod)
  

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

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]

AB = [list(map(lambda x, y: abs(x - y), a, b)) for a, b in zip(A, B)]
dp = [[[0] * 15001 for _ in range(W + 1)] for _ in range(H + 1)]
dp[0][0][0] = 1

for h in range(H):
    for w in range(W):
        ab = AB[h][w]
        for i in range(15000):
            if dp[h][w][i] == 1:
                dp[h+1][w][i+ab] = 1
                dp[h+1][w][abs(i-ab)] = 1
                dp[h][w+1][i+ab] = 1
                dp[h][w+1][abs(i-ab)] = 1

for i in range(15000):
    if dp[H][W-1][i] == 1:
        print(i)
        break


### FIXED CODE ###

H, W = map(int, input().split())
A = [list(map(int, input().split())) for _ in range(H)]
B = [list(map(int, input().split())) for _ in range(H)]

AB = [list(map(lambda x, y: abs(x - y), a, b)) for a, b in zip(A, B)]
dp = [[[0] * 12801 for _ in range(W + 1)] for _ in range(H + 1)]
dp[0][0][0] = 1

for h in range(H):
    for w in range(W):
        ab = AB[h][w]
        for i in range(10000):
            if dp[h][w][i] == 1:
                dp[h+1][w][i+ab] = 1
                dp[h+1][w][abs(i-ab)] = 1
                dp[h][w+1][i+ab] = 1
                dp[h][w+1][abs(i-ab)] = 1

for i in range(1000):
    if dp[H][W-1][i] == 1:
        print(i)
        break
### BUGGY CODE ###

import math

def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

Q = int(input())
lr_list = [list(map(int,input().split())) for _ in range(Q)]
flags = [False] * (10 ** 5)


for i in range(1, 10 ** 5 + 1, 2):
    if not flags[i]:
        flag1 = is_prime(i)
        flag2 = is_prime((i + 1) // 2)
        if flag1 and flag2:
            flags[i] = True

for l, r in lr_list:
    print(sum(flags[l: r + 1]))

### FIXED CODE ###

import math
import bisect
def is_prime(n):
    if n == 1: return False

    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False

    return True

Q = int(input())
lr_list = [list(map(int,input().split())) for _ in range(Q)]
flags = [False] * (10 ** 5)


for i in range(1, 10 ** 5 + 1, 2):
    if not flags[i]:
        flag1 = is_prime(i)
        flag2 = is_prime((i + 1) // 2)
        if flag1 and flag2:
            flags[i] = True
True_idxs = []
for i in range(len(flags)):
    if flags[i]:
        True_idxs.append(i)

# print(True_idxs)

for l, r in lr_list:
    l_idx = bisect.bisect_left(True_idxs, l)
    r_idx = bisect.bisect_right(True_idxs, r)
    print(r_idx - l_idx)
### BUGGY CODE ###

N = int(input())

literals = [[0]*26 for _ in range(N)]

for i in range(N):
    word = input()
    for char in word:
        literals[i][ord(char) - 97] += 1

answer = 0
for i in range(N):
    target = literals.pop()
    answer += literals.count(target)

print(answer)

### FIXED CODE ###

def C():
    N = int(input())

    word_dict = dict()
    count = 0

    for i in range(N):
        word = ''.join(sorted(input()))
        if word not in word_dict.keys():
            word_dict[word] = 1
        else:
            count += word_dict[word]
            word_dict[word] += 1

    print(count)

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

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

M = 10**6

import math

setwise = A[0]
for i in range(1,N):
    setwise = math.gcd(setwise,A[i])
    
PrimeFactorss = [[] for _ in range(M+1)]
for i in range(2, M+1):
    if len(PrimeFactorss[i]) == 0:
        for x in range(i, M+1, i):
            PrimeFactorss[x].append(i)
num_list = [0]*(M+1)

for i in range(N):
    num_list[A[i]] += 1

pairwise = [0]*N

for i in range(N):
    num_list[A[i]] -= 1
    for j in PrimeFactorss[A[i]]:
        for k in range(j,M+1,j):

            if num_list[k]==1:
                pairwise[i] += 1
                break
                
    num_list[A[i]] += 1
    
    if pairwise[i]>0:
        break
    
if sum(pairwise) == 0:
    print("pairwise coprime")
elif setwise == 1:
    print("setwise coprime")
else:
    print("not coprime")


### FIXED CODE ###

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

M = 10**6

import math

setwise = A[0]
for i in range(1,N):
    setwise = math.gcd(setwise,A[i])
    
PrimeFactorss = [[] for _ in range(M+1)]
for i in range(2, M+1):
    if len(PrimeFactorss[i]) == 0:
        for x in range(i, M+1, i):
            PrimeFactorss[x].append(i)
num_list = [0]*(M+1)

for i in range(N):
    num_list[A[i]] += 1

pairwise = [0]*(M+1)

n=M
primes = set(range(2, n+1))
for i in range(2, int(n**0.5+1)):
    primes.difference_update(range(i*2, n+1, i))
primes=list(primes)

for i in primes:
    for j in range(i,M+1,i):
        if num_list[j]==1:
            pairwise[i] += 1
        
ans = 0    
for i in pairwise:
    if i>1:
        ans += 1
        break
    
if setwise == 1 and ans == 0:
    print("pairwise coprime")
elif setwise == 1:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a=sorted(a)
f=sorted(f,reverse=True)

def is_lessthanK(X):
  ans=0
  for i in range(n):
    ans+=max(0,a[i]-X//f[i])
  return ans<=k

ng=-1
ok=10**13
while ok-ng>1:
  mid=(ok+ng)//2
  if is_lessthanK(mid):
    ok=mid
  else:
    ng=mid
print(ok)



### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
f=list(map(int,input().split()))
a=sorted(a)
f=sorted(f,reverse=True)


def is_lessthanK(X):
  ans=0
  for A,F in zip(a,f):
    if A*F>X:
      ans+=A-X//F
    if ans > k:
      return False
  return True


ng=-1
ok=a[-1]*f[0]
while ok-ng>1:
  mid=(ok+ng)//2
  if is_lessthanK(mid):
    ok=mid
  else:
    ng=mid
print(ok)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 0
for i in range(len(a)-1):
    for j in range(i+1, len(a)):
        x += a[i]*a[j]
print(x%(10**9+7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
x = 0
m = sum(a)
for i in range(len(a)-1):
    m = (m-a[i])%(10**9+7)
    x += a[i]*m
    x = x%(10**9+7)
print(x%(10**9+7))
### BUGGY CODE ###

n, q = map(int, input().split())
s = str(input())
for i in range(q):
    i = [int(i) for i in input().split()]
    ans = s[i[0]-1:i[1]].count("AC")
    print(ans)

### FIXED CODE ###

n, q = map(int, input().split())
s = 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 j in range(q):
    l, r = map(int, input().split())
    ans = t[r-1] - t[l-1]
    print(ans)
### BUGGY CODE ###

n = int(input())
s = input()

ans = 0

for i in range(1000):
    ss = str(i).zfill(3)
    idx = 0
    for j in range(len(s)):
        if (s[j] == ss[idx]):
            idx += 1
            if (idx == 3):
                break
    if (idx == 3):
        ans += 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()

ans = 0

for i in range(1000):
    ss = str(i).zfill(3)
    if (ss[0] in s):
        ind1 = s.index(ss[0])
        if (ss[1] in s[ind1+1:]):
            ind2 = ind1+1 + s[ind1+1:].index(ss[1])
            if (ss[2] in s[ind2+1:]):
                ans += 1

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

a,b,x=map(int,input().split())
c=0
def fun():
     print('1')
     print('2')
     print('3')
     print('4')
     print('5')
     print('6')
for i in range(a,b+1):
     if i%x==0:
          c+=1
print(c)

### FIXED CODE ###

a,b,x=map(int,(input().split()))
print(b//x-(a-1)//x)
#0 100000000000000000 1
### BUGGY CODE ###

import copy
import math

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(1,N+1):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1
T= copy.copy(V)

if S > Ns:
    S = Ns

# --
w = [[math.inf]*Nv for _ in range(Nv) ]
# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            w[ V[(u,ns_s)] ][ V[(v,ns_g)] ] = b
            # V -> U
            w[ V[(v,ns_s)] ][ V[(u,ns_g)] ] = b
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# -----

for i in range(N):
    c,d = map(int,input().split())
    v = i+1
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        w[ V[(v,ns_s)] ][ V[(v,ns_g)] ] = d

# -----
D=[-1]*Nv
# -----
s=(1,S)
del T[s]
D[V[s]] = 0
for v in T:
    D[V[v]] = w[ V[s] ][ V[v] ]
while len(T) > 0:
    u,_ = min(T.items(),key=lambda x:D[x[1]])
    del T[u]
    for v in T:
        D[ V[v] ] = min( D[ V[v] ], D[ V[u] ] + w[ V[u] ][ V[v] ] )

for i in range(2,N+1):
    ans = min([ D[ V[(i,ns)] ] for ns in range(Ns+1) ])
    print(ans)

### FIXED CODE ###

import math
import heapq

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

Us=[0]*M
Vs=[0]*M
As=[0]*M
Bs=[0]*M
for i in range(M):
    Us[i],Vs[i],As[i],Bs[i] = map(int,input().split())
    Us[i] -= 1
    Vs[i] -= 1

# ---
V={}
Ns = max(As)*N
Nv=N*(Ns+1)
cnt=0
for i in range(N):
    for ns in range(Ns+1):
        V[(i,ns)]=cnt
        cnt+=1

G=[[] for _ in range(Nv)]

if S > Ns:
    S = Ns

# U <-> V
for _ in range(M):
    u = Us.pop()
    v = Vs.pop()
    a = As.pop()
    b = Bs.pop()
    #
    for i in range(Ns+1): # i = 0,..,Ns
        ns_s = Ns - i
        ns_g = ns_s - a
        if ns_g >= 0:
            # U -> V
            G[ V[(u,ns_s)] ].append( (V[(v,ns_g)],b) )
            # V -> U
            G[ V[(v,ns_s)] ].append( (V[(u,ns_g)],b) )
            #print(u,v,a,b,ns_s,ns_g,V[(u,ns_s)],V[(v,ns_g)])

# -----

for i in range(N):
    c,d = map(int,input().split())
    for j in range(Ns): # j = 0,...,Ns-1
        ns_s = j
        ns_g = j + c
        if ns_g > Ns:
            ns_g = Ns
        G[ V[(i,ns_s)] ].append( (V[(i,ns_g)],d) )

# -----
D=[math.inf]*Nv
q=[]
# -----

s=V[(0,S)]
D[s] = 0
heapq.heappush(q,(0,s))

while len(q) > 0:
    p_cost,p_v = heapq.heappop(q)
    if D[p_v] < p_cost:
        continue
    for e_to,e_cost in G[p_v]:
        if D[ e_to ] > D[p_v] + e_cost:
            D[e_to] = D[p_v] + e_cost
            heapq.heappush(q, (D[e_to], e_to))

for i in range(1,N):
    ans = min([D[i*(Ns+1)+v] for v in range(Ns+1)])
    print(ans)
### BUGGY CODE ###

import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
""" B = []
C = []
for _ in range(M):
    L_,R_ = map(int,input().split())
    B.append(L_)
    C.append(R_) """

heapq.heapify(A)
for i in range(M):
    for j in range(BC[i][0]):
        tmp = heapq.heappop(A)
        if tmp >= BC[i][1]:
            heapq.heappush(A,tmp)
            break
        heapq.heappush(A,BC[i][1])
print(sum(A))

### FIXED CODE ###

import heapq
N,M = map(int,input().split())
A = list(map(int,input().split()))
BC = [list(map(int,input().split())) for _ in range(M)]
BC = sorted(BC,key = lambda x:x[1],reverse=True)


heapq.heapify(A)
for i in range(M):
    for j in range(BC[i][0]):
        tmp = heapq.heappop(A)
        if tmp >= BC[i][1]:
            heapq.heappush(A,tmp)
            break
        heapq.heappush(A,BC[i][1])
print(sum(A))
### BUGGY CODE ###

import bisect

n, m=map(int, input().split())
a=[int(n) for n in input().split()]
ans=0
cha=[]
a.sort()
if len(a)>m:
  for i in range(m):
    cha.append(a.pop())
else:
  for i in range(len(a)):
    cha.append(a.pop())
cha.sort()
for i in range(m):
  num=cha.pop()//2
  cha.insert(bisect.bisect_left(cha,num),num)


print(sum(cha)+sum(a))

### FIXED CODE ###

import heapq

n, m=map(int, input().split())
a=[-1*int(n) for n in input().split()]
heapq.heapify(a)

for i in range(m):
  num=-1*(-1*heapq.heappop(a)//2)
  heapq.heappush(a,num)

print(-1*sum(a))
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
quiz = [list(map(int, input().split())) for _ in range(q)]

for i in range(q):
    t = s[quiz[i][0] - 1:quiz[i][1]]
    cnt = t.count("AC")
    print(cnt)

### FIXED CODE ###

n, q = map(int, input().split())
s = list(input())
quiz = [list(map(int, input().split())) for _ in range(q)]

cnt_list = [0]*n
judge = 0

for i in range(n):
    if s[i] == "A":
        judge = 1
        cnt_list[i] = cnt_list[i-1]
    elif judge == 1 and s[i] == "C":
        judge = 0
        cnt_list[i] = cnt_list[i-1] + 1
    else:
        judge = 0
        cnt_list[i] = cnt_list[i-1]

for i in range(q):
    print(cnt_list[quiz[i][1] - 1] - cnt_list[quiz[i][0]-1])
### BUGGY CODE ###

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

N = 998244353

def fac(n,r,N):
    ans=1
    for i in range(r):
        ans=ans*(n-i)%N
    return ans

def combi(n,r,N):
    r= min(r, n-r)
    ans = fac(n,r,N)*pow(fac(r,r,N),N-2,N)%N
    return ans

ans=0
for i in range(k+1):
    ans+=m*combi(n-1,i,N)*pow(m-1,n-1-i,N)%N
    ans%=N
print(ans)



### FIXED CODE ###

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

N = 998244353

factorial = [1]
inverse = [1]
for i in range(1, n+2):
    factorial.append(factorial[-1] * i % N)
    inverse.append(pow(factorial[-1], N - 2, N))

def combi(n, r):
    if n < r or r < 0:
        return 0
    elif r == 0:
        return 1
    return factorial[n] * inverse[r] * inverse[n - r] % N

ans=0
if k<n//2:
    for i in range(k+1):
        ans+=m*combi(n-1,i)*pow(m-1,n-1-i,N)%N
        ans%=N
    print(ans)
else:
    for i in range(k+1,n):
        ans+=m*combi(n-1,i)*pow(m-1,n-1-i,N)%N
        ans%=N
    ans = pow(m,n,N)-ans
    if ans < 0:
        ans +=N
    print(ans)
### BUGGY CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [0]
for i in range(1, n):
    dp += [min([dp[i - j] + abs(h[i] - h[i - j]) for j in range(1, min(i, k) + 1)])]
print(dp[-1])

### FIXED CODE ###

n, k = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [0]
for i in range(1, n):
    to = min(i, k) + 1
    dp += [min([dp[-j] + abs(h[i] - h[i - j]) for j in range(1, to)])]
print(dp[-1])
### BUGGY CODE ###

import fractions
A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes

get_primes(10**6)

for p in get_primes(C):
  if p ** 2 > C:
    break
  if C % p == 0:
    pfac.append(p)
    while C % p == 0:
      C //= p
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)

### FIXED CODE ###

import fractions
import math

A, B = map(int, input().split())
C = fractions.gcd(A, B)
pfac = []

def get_primes(n):
  primes = [2]
  for i in range(3, (n+1), 2):
    for p in primes:
      if i % p == 0:
        break
      if i < p ** 2:
        primes.append(i)
        break
    else:
      primes.append(i)
  return primes

def get_primes2(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n == 1:
        return []
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

for q in get_primes2(min(C, 10**6)):
  if q ** 2 > C:
    break
  if C % q == 0:
    pfac.append(q)
    while C % q == 0:
      C //= q
if C != 1:
  pfac.append(C)


print(len(pfac) + 1)