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

from copy import deepcopy
from functools import reduce


class Divisor:
    def __init__(self, n):
        """ make divisors list and prime factorization list of n
            complexity: O(n^(1/2))
            used in ProjectEuler No.12, yukicoder No.36
        """
        assert(n >= 1)
        number = n
        if number == 1:
            self.primeFactorization = {}
        else:
            self.primeFactorization = {}
            for i in range(2, int(n**0.5)+1):
                cnt = 0
                while number % i == 0:
                    cnt += 1
                    number //= i
                if cnt > 0:
                    self.primeFactorization[i] = cnt
            if number > 1:
                self.primeFactorization[number] = 1

    def primeFactors(self):
        return deepcopy(self.primeFactorization)

    def numDivisors(self):
        """ the number of divisors """
        if self.primeFactorization.get(1, 0) == 1:
            return 1
        numDiv = 1
        for _, cnt in self.primeFactorization.items():
            numDiv *= cnt+1
        return numDiv

    def sumDivisors(self):
        return reduce(lambda x, y: x * y, [sum(p**i for i in range(n+1)) for p, n in self.primeFactorization.items()])


mod = 10 ** 9 + 7

N = int(input())
A = [int(x) for x in input().split()]
divs = [Divisor(a) for a in A]
lcm = {}
for div in divs:
    for p, cnt in div.primeFactorization.items():
        lcm[p] = max(lcm.get(p, 0), cnt)
ans = 0
for div in divs:
    ret = 1
    for key, val in lcm.items():
        ret = ret * pow(key, val - div.primeFactorization.get(key, 0), mod) % mod
    ans = (ans + ret) % mod
print(ans)


### FIXED CODE ###

import sys
import math
if sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd


def inv(x, mod):
    return pow(x, mod-2, mod)


def lcm(arr, mod = 10 ** 9 + 7):
    ret = 1
    for a in arr:
        ret = ret * a // gcd(ret, a)
    return ret

mod = 10 ** 9 + 7

N = int(input())
A = [int(x) for x in input().split()]
a = lcm(A)
print(sum(a * inv(x, mod) for x in A) % mod)
### BUGGY CODE ###

#-*-coding:utf-8-*-
import bisect

def main():

    n = int(input())
    a_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))
    c_list = list(map(int, input().split()))

    a_list.sort()
    b_list.sort()
    c_list.sort()

    cnt = 0
    
    for i in range(n):
        for j in range(n):
            if a_list[i] < b_list[j]:
                position = bisect.bisect_right(c_list, b_list[j])
                cnt += n - position
    
    print(cnt)
    

if __name__ == '__main__':
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-
import bisect

def main():

    n = int(input())
    a_list = list(map(int, input().split()))
    b_list = list(map(int, input().split()))
    c_list = list(map(int, input().split()))

    a_list.sort()
    b_list.sort()
    c_list.sort()

    cnt = 0
    
    for b in b_list:
        i = bisect.bisect_left(a_list, b)
        j = n - bisect.bisect_right(c_list, b)
        cnt += i * j
    
    print(cnt)
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

'''
                                    *             * * * * * * * *
                                    *             *
                                    *             *
                                    *             *
                                    *             *
                                    *             *
                                    *             *
                                    * * * * * * * * * * * * * * *
                                                  *             *
                                                  *             *
                                                  *             *
                                                  *             *
                                                  *             *
                                                  *             *
                                    * * * * * * * *             *

'''
import sys
sys.setrecursionlimit(10**7)
dp=[-1]*(10**5+2)
dp[0]=0
def frog2(arr,N,K):
    if N==0:
        return dp[0]
    if dp[N]!=-1:
       return dp[N]
    cnt=10**9
    for i in range(N-1,max(N-K-1,-1),-1):
        cnt=min(cnt,frog2(arr,i,K)+abs(arr[N]-arr[i]))
    dp[N]=cnt
    #print(N,dp[N])
    return dp[N]
if __name__ == "__main__":
    N,K=map(int,input().split())
    h=[int(i) for i in input().split()][:N]
    frog2(h,N-1,K)
    #print(dp)
    print(dp[N-1])

### FIXED CODE ###

from sys import stdin
N,K=map(int,stdin.readline().split())
h=[int(i) for i in stdin.readline().split()][:N]
dp=[float('inf') for i in range(N)]
dp[0]=0
for i in range(N):
    for j in range(i+1,i+K+1):
        if j<N:
            dp[j]=min(dp[j],dp[i]+abs(h[j]-h[i]))
    #print(dp)
print(dp[-1])
### BUGGY CODE ###

from collections import defaultdict, Counter
import sys
input = sys.stdin.readline
def main():
    # Load data
    N = int(input())
    A = list(map(int, input().split()))
    p = 10**9 + 7
    # LCM: dict 最小公倍数の素因数分解
    LCM = defaultdict(int)
    # A2Factor: list A[i]の素因数分解
    A2Factor = []
    def primes(n):
        is_prime = [True] * (n + 1)
        is_prime[0] = False
        is_prime[1] = False
        for i in range(2, int(n**0.5) + 1):
            if not is_prime[i]:
                continue
            for j in range(i * 2, n + 1, i):
                is_prime[j] = False
        return [i for i in range(n + 1) if is_prime[i]]
    PRIME_LIST = primes(max(A))
    def factorization(n):
        arr = []
        temp = n
        for i in PRIME_LIST:
            if temp%i==0:
                # cnt=0
                while temp%i==0:
                    # cnt+=1
                    temp //= i
                    arr.append(i)

        if temp!=1:
            # arr[temp] = 1
            arr.append(temp)

        if not arr:
            # arr[n] = 1
            arr.append(n)

        return arr

    for idx in range(N):
        arr = factorization(A[idx])
        arr = Counter(arr)
        for key, value in arr.items():
            LCM[key] = max(LCM[key], value)
        A2Factor.append(arr)
    ans = 0
    for i in range(N):
        tmp = 1
        for key, value in LCM.items():
            cnt = 0 if key not in A2Factor[i].keys() else A2Factor[i][key]
            tmp *= pow(key, value-cnt, p)
            tmp %= p
        ans += tmp % p
        ans %= p

    print(ans % p)

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 ###

def main():
  import sys
  input=sys.stdin.readline
  h,w,k=map(int,input().split())
  sx,sy,tx,ty=map(int,input().split())
  b=[[-1]*(w+2)]
  for i in range(h):
    s=input()
    bb=[-1]
    for j in s:
      if j==".":bb.append(0)
      else:bb.append(-1)
    bb.append(-1)
    b.append(bb)
  b.append([-1]*(w+2))
  from collections import deque
  d=deque()
  d.append((sx,sy))
  while d:
    x,y=d.popleft()
    if x==tx and y==ty:
      exit(print(b[x][y]))
    for i in range(1,k+1):
      if b[x-i][y]<=b[x][y] and b[x-i][y]!=0:break
      d.append((x-i,y))
      b[x-i][y]=b[x][y]+1
    for i in range(1,k+1):
      if b[x+i][y]<=b[x][y] and b[x+i][y]!=0:break
      d.append((x+i,y))
      b[x+i][y]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y-j]<=b[x][y] and b[x][y-j]!=0:break
      d.append((x,y-j))
      b[x][y-j]=b[x][y]+1
    for j in range(1,k+1):
      if b[x][y+j]<=b[x][y] and b[x][y+j]!=0:break
      d.append((x,y+j))
      b[x][y+j]=b[x][y]+1
  print(-1)
if __name__ == "__main__":
  main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
h,w,k=map(int,input().split())
si,sj,ti,tj=map(int,input().split())
si-=1
sj-=1
ti-=1
tj-=1
b=[input()for _ in range(h)]
ans=[[-1]*w for _ in range(h)]
ans[si][sj]=0
from collections import deque
d=deque()
d.append((si,sj))
while d:
  x,y=d.popleft()
  if x==ti and y==tj:
    exit(print(ans[x][y]))
  for dx,dy in [[1,0],[-1,0],[0,-1],[0,1]]:
    for i in range(1,k+1):
      xx=x+dx*i
      yy=y+dy*i
      if not(0<=xx<h and 0<=yy<w) or b[xx][yy]=="@":break
      if 0<=ans[xx][yy]<=ans[x][y]:break
      if ans[xx][yy]==-1:d.append((xx,yy))
      ans[xx][yy]=ans[x][y]+1
print(-1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9+7
sum = 0
for i in range(N-1):
    for j in range(i+1, N):
        sum += A[i]*A[j]
print(sum%mod)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10 ** 9 + 7
cs = A[:]
for i in range(1, N):
	cs[i] += cs[i-1]
sum = 0
for i in range(0, N-1):
	sum += A[i] * (cs[-1] - cs[i])
print(sum % mod)
### BUGGY CODE ###

N,W = map(int,input().split())
goods = [list(map(int,input().split())) for _ in range(N)]

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

for i,[w,v] in enumerate(goods):
  for j in range(W):
    if i == 0:
      if j >= goods[0][0]-1:
        dp[0][j] = goods[0][1]
    else:
      if w <= j:
        dp[i][j] = max(v+dp[i-1][j-w],dp[i][j-1],dp[i-1][j])
      else:
        dp[i][j] = dp[i-1][j]

print(dp[N-1][W-1])

### FIXED CODE ###

N,W = map(int,input().split())
goods = [list(map(int,input().split())) for _ in range(N)]

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

for i,[w,v] in enumerate(goods):
  for j in range(W):
    if i == 0:
      if j >= goods[0][0]-1:
        dp[0][j] = goods[0][1]
    else:
      if w <= j:
        dp[i][j] = max(v+dp[i-1][j-w],dp[i][j-1],dp[i-1][j])
      else:
        dp[i][j] = max(dp[i-1][j],dp[i][j-1])

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

from collections import deque
import sys
n,p=map(int,input().split())

e=[]
for _ in range(n):
    s,t,x = map(int,input().split())
    e.append((s-x,1,x))
    e.append((t-x,-1,x))
e.sort()
q = deque()
for _ in range(p):
    q.append(int(input()))
s=set()
#print(e)
for t,f,x in e:
    while q and t > q[0]:
        #print((t,f,x,q.popleft()))
        q.popleft()
        if len(s) == 0:
            print(-1)
        else:
            print(min(s))
    if not q:
        sys.exit()
    if f == 1:
        s.add(x)
    else:
        s.remove(x)
while q:
    q.pop()
    print(-1)

### FIXED CODE ###

import sys
input = sys.stdin.readline
 
n,q = map(int,input().split())
imos = []
for i in range(n):
    s,t,x = map(int,input().split())
    imos.append((s-x,x))
    imos.append((t-x,-x))
ans = set()
j = 0
for i in range(q):
    d = int(input())
    imos.append((d,1e100))
imos.sort()
m = 1e100
flag = False
for t,stop in imos:
    if stop == 1e100:
        if ans:
            if not flag:
                m = min(ans)
                flag = True
            print(m)
        else:
            print(-1)
    elif stop > 0:
        ans.add(stop)
        if stop < m:
            m = stop
            flag = True
    else:
        ans.remove(-stop)
        if m == -stop:flag = False
### BUGGY CODE ###

n = int(input())
s = str(input())
r = []
g = []
b = []
for i in range(n):
    if s[i] == "R":
        r.append(i+1)
    elif s[i] == "G":
        g.append(i+1)
    else:
        b.append(i+1)
cnt = 0
for i in r:
    for j in g:
        if (i+j)%2==0 and (i + j) // 2 in b:
            cnt += 1
        if (2 * j) - i in b:
            cnt += 1
        if (2 * i) - j in b:
            cnt += 1
print((len(r) * len(g) * len(b))-cnt)




### FIXED CODE ###

n = int(input())
s = str(input())
r = []
g = []
b = []
for i in range(n):
    if s[i] == "R":
        r.append(i+1)
    elif s[i] == "G":
        g.append(i+1)
    else:
        b.append(i+1)
cnt=len(r)*len(g)*len(b)
if n<=3:
    print(0)
    exit()
for i in range(n-2):
    for j in range(i+1,n-1):
        if j*2-i<n:
            if s[i]!=s[j] and s[j]!=s[j*2-i] and s[j*2-i]!=s[i]:
                cnt-=1
print(cnt)
### BUGGY CODE ###

i=0
a,b,c,d=map(int,input().split())
while(a!=0 and c!=0):
   if(i%2):
        a-=d
   else:
       c-=b
   i+=1
print("Yes" if a!=0 else "No")

### FIXED CODE ###

ok=True
i=0
a,b,c,d=map(int,input().split())
k=c//b
c-=b*k
a-=d*(k)
if(a<=0 and c!=0):
    print("No")
else:
    print("Yes")
### BUGGY CODE ###

job = list()
salary = list()
k = 0
n,m = map(int,input().split())

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for j in range(n):
    a,b = job[j]
    salary.append(b)

    if a + k > m :
        salary.remove(min(salary))
        continue

    k += 1

print(sum(salary))


### FIXED CODE ###

import heapq
job = list()
salary = list()
n,m = map(int,input().split())

for i in range(n):
    a,b = map(int,input().split())
    job.append((a,b))

job.sort(reverse = True)

for x in job:
    s,t = x
    heapq.heappush(salary,t)
    if s - m > 0:
        heapq.heappop(salary)
    else:
        m -= 1

print(sum(salary))
### BUGGY CODE ###

# coding: utf-8
H,N=map(int,input().split())
AB=[[0,0]]
for i in range(N):
    AB.append(list(map(int,input().split())))
 
INF=10**9

dp=[INF for i in range(H+1)]
dp[0]=0

for i in range(1,N+1):
    for j in range(1,H+1):
        dp[j]=min(dp[j],dp[max(0,j-AB[i][0])] + AB[i][1])

print(dp[H])

### FIXED CODE ###

# coding: utf-8
H,N=map(int,input().split())
AB=[[0,0]]
for i in range(N):
    AB.append(list(map(int,input().split())))

INF=10**9

dp=[[INF for i in range(H+1)] for j in range(N+1)]

for i in range(N+1):
    dp[i][0]=0


for i in range(1,N+1):
    for j in range(1,H+1):
        dp[i][j]=min(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])
        #print(dp[i-1][j],dp[i-1][max(j-AB[i][0],0)] + AB[i][1],dp[i][max(j-AB[i][0],0)] + AB[i][1])
        


print(dp[N][H])
### BUGGY CODE ###

# coding: utf-8
# Your code here!
from collections import deque
N,Q = map(int,input().split())
tree = {}
px = []
counter = [0 for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = [b]
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = [a]
for _ in range(Q):
    ip,ix = map(int,input().split())
    px.append([ip,ix])


oya = deque([1])

while oya:
    oyai = oya.popleft()
    for ko in tree[oyai]:
        tree[ko].remove(oyai)
        oya.append(ko)


for pi,xi in px:
    oya = deque([pi])
    
    while oya:
        oyai = oya.popleft()
        counter[oyai-1] +=xi
        for ko in tree[oyai]:
            oya.append(ko)  
print(' '.join(map(str,counter)))


### FIXED CODE ###

# coding: utf-8
# Your code here!
from collections import deque
N,Q = map(int,input().split())
tree = {}
px = []
counter = [0 for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    if a in tree:
        tree[a].append(b)
    else:
        tree[a] = [b]
    if b in tree:
        tree[b].append(a)
    else:
        tree[b] = [a]
for _ in range(Q):
    ip,ix = map(int,input().split())
    counter[ip-1] += ix


oya = deque([1])

while oya:
    oyai = oya.popleft()
    for ko in tree[oyai]:
        tree[ko].remove(oyai)
        counter[ko-1] += counter[oyai-1]
        oya.append(ko)




print(' '.join(map(str,counter)))
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

def mod_inverse(a, p):
    return pow(a, p - 2, p)

def combination(n, k, p):
    a = 1
    for i in range(n, n - k, -1):
        a *= i
        a %= p
    b = 1
    for i in range(k):
        b *= (i + 1)
        b %= p
    return (a * mod_inverse(b, p)) % p

a.sort()
max_x = 0
min_x = 0
for i in range(n - k + 1):
    temp = combination(k - 1 + i, k - 1, mod)
    max_x += (temp * a[k - 1 + i])
    min_x += (temp * a[n - k - i])
    max_x %= mod
    min_x %= mod
print((max_x - min_x) % mod)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10 ** 9 + 7

fact = [1] * (n + 1)
revfact = [1] * (n + 1)
for i in range(n):
    fact[i + 1] = ((i + 1) * fact[i]) % mod
revfact[n] = pow(fact[n], mod - 2, mod)
for i in reversed(range(n)):
    revfact[i] = ((i + 1) * revfact[i + 1]) % mod
def combination(n, k, p):
    return (fact[n] * revfact[k] * revfact[n - k]) % p

a.sort()
max_x = 0
min_x = 0
for i in range(n - k + 1):
    temp = combination(k - 1 + i, k - 1, mod)
    max_x += (temp * a[k - 1 + i])
    min_x += (temp * a[n - k - i])
    max_x %= mod
    min_x %= mod
print((max_x - min_x) % mod)
### BUGGY CODE ###

N = int(input())
from collections import defaultdict

G = defaultdict(list)
EdaNum = defaultdict(int)

for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    EdaNum[(a,b)] = i
    
ans = [-1]*(N-1)

que = [[1,-1]]
K = 0
visited = [False]*(N+1)

for i in range(1,N+1):
    K = max(K,len(G[i]))

while que != []:
    #print(que)
    now,parent = que.pop()
    visited[now]=True
    used = [False]*(K+1)
    if parent != -1:
        used[ans[EdaNum[(min(now,parent),max(now,parent))]]] = True
    nowcolor = 1
    for i in G[now]:
        #print(i,parent)
        if i != parent:
            while used[nowcolor] == True:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            if len(G[i])!=1:
                que.append([i,now])
    #print(que)

print(K)
for i in ans:
    print(i)

### FIXED CODE ###

N = int(input())
from collections import defaultdict

G = defaultdict(list)
EdaNum = defaultdict(int)

for i in range(N-1):
    a,b = map(int,input().split())
    G[a].append(b)
    G[b].append(a)
    EdaNum[(a,b)] = i
    
ans = [-1]*(N-1)

que = [[1,-1,-1]]
K = 0
visited = [False]*(N+1)

for i in range(1,N+1):
    K = max(K,len(G[i]))

while que != []:
    #print(que)
    now,parent,parentcolor = que.pop()
    visited[now]=True
    nowcolor = 1
    for i in G[now]:
        #print(i,parent)
        if i != parent:
            if nowcolor == parentcolor:
                nowcolor += 1
            ans[EdaNum[(min(now,i),max(now,i))]] = nowcolor
            nowcolor += 1
            if len(G[i])!=1:
                que.append([i,now, nowcolor-1])
    #print(que)

print(K)
for i in ans:
    print(i)
### BUGGY CODE ###

import copy

n = int(input())
arr = [int(input()) for i in range(n)]
for i in range(n):
    brr = copy.copy(arr)
    brr.pop(i)
    print(max(brr))

### FIXED CODE ###

import copy

n = int(input())
arr = [int(input()) for i in range(n)]
brr = sorted(arr, reverse=True)
ind = arr.index(max(arr))
# for i in range(n):
#     brr = copy.copy(arr)
#     brr.pop(i)
#     print(max(brr))
for i in range(n):
    if i == ind:
        print(brr[1])
    else:
        print(brr[0])
### BUGGY CODE ###

from operator import itemgetter
N=int(input())
A=list(map(int, input().split()))
B=[[i, A[i]] for i in range(N)] 
B=sorted(B, key=itemgetter(1), reverse=True)

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

for x in range(N):
    dp[x+1][0]=dp[x][0]+B[x][1]*abs(B[x][0]-x)
    
for y in range(N):
    dp[0][y+1]=dp[0][y]+B[y][1]*abs(N-1-y-B[y][0])
    
for z in range(2, N+1):
    for x in range(1, z):
        y=z-x
        dp[x][y]=max(dp[x][y-1]+B[z-1][1]*abs(N-y-B[z-1][0]), dp[x-1][y]+B[z-1][1]*abs(x-1-B[z-1][0]))
        
print(max([dp[x][N-x] for x in range(N+1)]))

### FIXED CODE ###

from operator import itemgetter
N=int(input())
A=list(map(int, input().split()))
B=[[i, A[i]] for i in range(N)] 
B=sorted(B, key=itemgetter(1), reverse=True)

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

for x in range(N):
    dp[x+1][0]=dp[x][0]+B[x][1]*abs(B[x][0]-x)
    
for y in range(N):
    dp[0][y+1]=dp[0][y]+B[y][1]*abs(N-1-y-B[y][0])
    
for z in range(2, N+1):
    for x in range(1, z):
        y=z-x
        dp[x][y]=max(dp[x][y-1]+B[z-1][1]*abs(N-y-B[z-1][0]), dp[x-1][y]+B[z-1][1]*abs(x-1-B[z-1][0]))
        
print(max([dp[x][N-x] for x in range(N+1)]))
### BUGGY CODE ###

def inv(s):
    t = ''
    for i in range(len(s)):
        t += s[-1 * (i + 1)]
    return t

s = input()
q = int(input())
ans = s
for i in range(q):
    qi = input()
    if qi[0] == '1':
        ans = inv(ans)
    else:
        if qi[2] == '1':
            ans = qi[4] + ans
        elif qi[2] == '2':
            ans = ans + qi[4]
print(ans)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
ans = deque(s)
rev = 0
for i in range(q):
    qi = input()
    if qi[0] == '1':
        rev += 1
    else:
        if qi[2] == '1' and rev % 2 == 0:
            ans.appendleft(qi[4])
        elif qi[2] == '2' and rev % 2 == 0:
            ans.append(qi[4])
        if qi[2] == '1' and rev % 2 == 1:
            ans.append(qi[4])
        elif qi[2] == '2' and rev % 2 == 1:
            ans.appendleft(qi[4])

parity = rev % 2
if parity:
    ans.reverse()
    for i in ans:
        print(i, end='')
else:
    for i in ans:
        print(i, end='')
### BUGGY CODE ###

import sys
import array

from operator import itemgetter

def main():



	input = sys.stdin.readline


	md = 998244353
	n = int(input())
	tl=n+1
	
#	ft=[0]*tl
	ft=array.array('I', [0 for _ in range(tl)])
	xy = [[0]*2 for _ in range(n)]
	for i in range(n):
		xy[i] = [int(item) for item in input().split()]
	xy.sort(key=itemgetter(0))
	yxi = [y for x, y in xy]

	*YS, = set(yxi)
	YS.sort()
	yxi= list(map({e: i for i, e in enumerate(YS)}.__getitem__, yxi))

	ct=[0]*(n+1)
	ct[0]=1
	for i in range(1,n+1):
		ct[i]=ct[i-1]*2%md

	cnt=tuple(ct)

	def upd(i):
		i+=1
		while(i<=n):
			ft[i]+=1
			i+=i&-i

	def get(i):
		i+=1
		ret=0
		while(i!=0):
		    ret+=ft[i]
		    i-=i&-i
		return ret

	def calc(get,upd):
		for i, y in enumerate(yxi):
			v = get(y); upd(y)
			p1 = cnt[v]; p0 = cnt[y - v]
			q1 = cnt[i - v]; q0 = cnt[(n - y - 1) - (i - v)]
			yield (p0 + p1 + q0 + q1 - (p0 + q1) * (p1 + q0)) % md


	print((sum(calc(get,upd))+n*cnt[n] - n)%md)

main()


### FIXED CODE ###

import sys
import array

from operator import itemgetter

def main():



	input = sys.stdin.readline


	md = 998244353
	n = int(input())
	tl=n+1
	
	ft=[0]*tl

	xy = [[0]*2 for _ in range(n)]
	for i in range(n):
		xy[i] = [int(item) for item in input().split()]
	xy.sort(key=itemgetter(0))
	yxi = [y for x, y in xy]

	*YS, = set(yxi)
	YS.sort()
	yxi= list(map({e: i for i, e in enumerate(YS)}.__getitem__, yxi))

	ct=[0]*(n+1)
	ct[0]=1
	for i in range(1,n+1):
		ct[i]=ct[i-1]*2%md

	cnt=tuple(ct)

	def upd(i):
		i+=1
		while(i<=n):
			ft[i]+=1
			i+=i&-i

	def get(i):
		i+=1
		ret=0
		while(i!=0):
		    ret+=ft[i]
		    i-=i&-i
		return ret

	def calc(get,upd):
		for i, y in enumerate(yxi):
			v = get(y); upd(y)
			p1 = cnt[v]; p0 = cnt[y - v]
			q1 = cnt[i - v]; q0 = cnt[(n - y - 1) - (i - v)]
			yield (p0 + p1 + q0 + q1 - (p0 + q1) * (p1 + q0)) % md


	print((sum(calc(get,upd))+n*cnt[n] - n)%md)

main()
### BUGGY CODE ###

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

S = input()


for _ in range(Q):
    l, r = map(int, input().split())
    count = 0
    for j in range(l,r):
        if S[j-1:j+1] == 'AC':
            count += 1
            #print(S[j-1:j+1])
    print(count)


### 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 i in range(Q):
	l, r = map(int, input().split())
	print(t[r-1] - t[l-1])