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

# 末端の頂点は白1通り、黒1通り
# それ以外の頂点は、各子どもの頂点を元に、白:子の全ての場合分けの積、黒:子が全て白の場合分けの積
# で更新していく

N = int(input())
G = [set() for i in range(N)]
MOD = 10 ** 9 + 7

for i in range(N - 1):
  x,y = map(int,input().split())
  G[x - 1].add(y - 1)
  G[y - 1].add(x - 1)
  
dp_black = [-1] * N
dp_white = [-1] * N

stack = [-1,0]

while len(stack) > 1:
  v = stack[-1]
  parent = stack[-2]
  black = 1
  white = 1
  for child in G[v]:
    if child == parent:
      continue
    if dp_black[child] == -1:
      stack.append(child)
      break
    black *= dp_white[child]
    black %= MOD
    white *= (dp_black[child] + dp_white[child])
    white %= MOD
  else:
    dp_black[v] = black
    dp_white[v] = white
    stack.pop()
    
print((dp_black[0] + dp_white[0]) % MOD)    


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

# 末端の頂点は白1通り、黒1通り
# それ以外の頂点は、各子どもの頂点を元に、白:子の全ての場合分けの積、黒:子が全て白の場合分けの積
# で更新していく

N = int(input())
G = [[] for i in range(N)]
MOD = 10 ** 9 + 7

for i in range(N - 1):
  x,y = map(int,input().split())
  G[x - 1].append(y - 1)
  G[y - 1].append(x - 1)
  
dp_black = [-1] * N
dp_white = [-1] * N

# 頂点vの(黒,白)の場合の数を求める
def search(v,parent):
  if dp_black[v] != -1:
    return (dp_black[v],dp_white[v])
  black = 1
  white = 1
  for child in G[v]:
    if child == parent:
      continue
    b,w = search(child, v)
    black *= w
    black %= MOD
    white *= (b + w)
    white %= MOD
  dp_black[v] = black
  dp_white[v] = white
  return (black, white)

print(sum(search(0, -1)) % MOD)
### BUGGY CODE ###

N = int(input())
S = input().strip()
cnt = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            cur = [i,j,k]
            ind = 0
            for n in range(N):
                if int(S[n])==cur[ind]:
                    ind += 1
                    if ind==3:break
            if ind==3:
                cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
S = list(map(int,list(input().strip())))
cnt = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            cur = [i,j,k]
            ind = 0
            for n in range(N):
                if S[n]==cur[ind]:
                    ind += 1
                    if ind==3:
                        cnt += 1
                        break
print(cnt)
### BUGGY CODE ###

S=input()
Q=int(input())

for _ in range(Q):
    Query=list(input().split())
    if int(Query[0])==1:
        S=S[::-1]#逆順覚える
    elif int(Query[1])==1:
        S=Query[2]+S
    elif int(Query[1])==2:
        S=S+Query[2]
print(S)

### FIXED CODE ###

from collections import deque

S=input()
Q=int(input())

t=deque(S)
flag_r=0
for _ in range(Q):
    Query=input().split()
    if int(Query[0])==1:
        flag_r=(flag_r+1)%2
    elif int(Query[1])==1+flag_r:
        t.appendleft(Query[2])
    else:
        t.append(Query[2])
result=''.join(t)
if flag_r:# reverseは最後にやる
    result=result[::-1]
print(result)
### BUGGY CODE ###

s = input()
if len(s)%2==1:
    s += '0'
s = s[:-2]
while True:
    if s[:len(s)//2] == s[len(s)//2:]:
        print(len(s[:len(s)//2]))
    s = s[:-2]

### FIXED CODE ###

s = input()
if len(s)%2==1:
    s += '0'
s = s[:-2]
while True:
    if s[:len(s)//2] == s[len(s)//2:]:
        print(len(s))
        break
    s = s[:-2]
### BUGGY CODE ###

n = int(input())
d = len(bin(n)) - 2
mod = 10**9 + 7
dp = [[0 for j in range(n+1+2**d)] for i in range(d+1)]
dp[0][0] = 1
for i in range(d):
    t = 2 ** (d-i-1)
    for j in range(n+1):
        dp[i+1][j] = (dp[i+1][j] +  dp[i][j]) % mod
        dp[i+1][j+t] = (dp[i+1][j+t] + dp[i][j]) % mod
        dp[i+1][j+2*t] = dp[i][j] % mod
print(sum(dp[d][:n+1]))

### FIXED CODE ###

n = int(input())
d = len(bin(n)) - 2
mod = 10**9 + 7
dp = [[0 for j in range(3)] for i in range(d+1)]
dp[d][0] = 1
for i in range(d):
    k = d - 1 - i
    for j in range(3):
        if j == 0:
            if (n >> k) & 1:
                dp[k][0] += dp[k+1][0]
                dp[k][1] += dp[k+1][0]
            else:
                dp[k][0] += dp[k+1][0]
        elif j == 1:
            if (n >> k) & 1:
                dp[k][1] += dp[k+1][1]
                dp[k][2] += dp[k+1][1] * 2
            else:
                dp[k][0] += dp[k+1][1]
                dp[k][1] += dp[k+1][1]
                dp[k][2] += dp[k+1][1]
        else:
            dp[k][2] += dp[k+1][2] * 3
        map(lambda x:x%mod, dp[k])
print(sum(dp[0]) % mod)
### BUGGY CODE ###

INF = 10**18
def li():
    return [int(x) for x in input().split()]
from collections import deque

H, W = li()
Ch, Cw = li()
Dh, Dw = li()
S = [list(input()) for x in range(H)]

dx=[1,0,-1,0]
dy=[0,1,0,-1]

def bfs():
    costmap = [[-1] * W for i in range(H)]
    costmap[Ch-1][Cw-1] = 0
    que = deque([])
    que.append((Cw, Ch))

    while que:
        x, y = que.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                que.appendleft((nx, ny))
                costmap[ny-1][nx-1] = costmap[y-1][x-1]
        for i in range(x-2, x+3):
            for j in range(y-2, y+3):
                nx, ny = i, j
                if 0 < nx <= W and 0 < ny <= H and S[ny - 1][nx - 1] == '.' and (costmap[ny - 1][nx - 1] == -1 or costmap[y - 1][x - 1] < costmap[ny - 1][nx - 1]):
                    que.append((nx, ny))
                    costmap[ny-1][nx-1] = costmap[y-1][x-1] + 1
    return costmap

costmap = bfs()
print(costmap[Dh-1][Dw-1])


### FIXED CODE ###

from collections import deque
h,w=map(int,input().split())
ch,cw=map(int,input().split())
dh,dw=map(int,input().split())
s=[list(input()) for i in range(h)]
 
#幅優先で解く。
dx=[1,0,-1,0]
dy=[0,1,0,-1]
def bfs():
  maze=[[-1]*w for i in range(h)]
  maze[ch-1][cw-1]=0
  qu=deque([])
  qu.append((cw-1,ch-1))
  magic=0
  
  while qu:
    x,y=qu.popleft()
    for i in range(4):
      nx=dx[i]+x
      ny=dy[i]+y
      if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]):
        qu.appendleft((nx,ny))
        maze[ny][nx]=maze[y][x]
    for i in range(x-2,x+3):
      for j in range(y-2,y+3):
        nx=i
        ny=j
        if 0<=nx<=w-1 and 0<=ny<=h-1 and s[ny][nx]=="." and (maze[ny][nx]==-1 or maze[ny][nx]>maze[y][x]+1):
          qu.append((nx,ny))
          maze[ny][nx]=maze[y][x]+1
  return maze
    
maze = bfs()
print(maze[dh-1][dw-1])
### BUGGY CODE ###

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

mod = 1000000007

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

print(ans)


### FIXED CODE ###

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

mod = 1000000007
s = sum(a) % mod
ans = 0

for i in a:
    s -= i
    ans += s * i
    ans %= mod

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

import sys
n = int(input()) 

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

ans = 1;
for i in range(n):
  if a[i] == 0:
    print(0)
    sys.exit()
    
  ans *= a[i]
  
if (ans > 1000000000000000000):
    print(-1)
    sys.exit()
print(ans)

### FIXED CODE ###

import sys
n = int(input()) 

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

ans = 1;
for i in range(n):
  if (a[i] == 0):
    print('0')
    sys.exit()
 
for i in range(n):
    
  ans *= a[i]
  if (ans > 1000000000000000000):
    print('-1')
    sys.exit()
  

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

#134
N=int(input())
a=[int(input()) for i in range(N) ]
a_M=[]
a_M.append( max(a[1:]) )
for i in range(1,N):
    if a[i]<a_M[0]:
        a_M.append(a_M[0])
    else:
        s=a[i]
        a[i]=0
        a_M.append( max(a) )
        a[i]=s   
for x in a_M:
    print(x)

### FIXED CODE ###

#134
N=int(input())
a=[int(input()) for i in range(N) ]
a_M=[]
a_M1=sorted(a)[-1]
a_M2=sorted(a)[-2]
for i in range(N):
    if a[i]==a_M1:
        a_M.append(a_M2)
    else:
        a_M.append(a_M1)
for x in a_M:
    print(x)
### BUGGY CODE ###

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

def kuriagari(n, m):
  if n+m == n^m:
    return 0
  else:
    return 1
  
num=0

for i in range(N):
  judge = 0
  num2 = 0
  j=0
  while judge == 0 and i+j<N:
    judge=kuriagari(num2, A[i+j])
    if judge==0:
      num2+=A[i+j]
      num+=1
    j+=1
      
print(num)
  

### FIXED CODE ###

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

def kuriagari(n, m):
  if n+m == n^m:
    return 0
  else:
    return 1
  
num=0

zero_list = [0] * (N-1)
zero_list.append(N)
for i in range(N-1):
  if A[N-1-i] == 0:
    zero_list[N-2-i]=zero_list[N-1-i]
  else:
    zero_list[N-2-i]=N-1-i

for i in range(N):
  judge = 0
  num2 = 0
  j=0
  while judge == 0 and i+j<N:
    judge=kuriagari(num2, A[i+j])
    if judge==0:
      num2+=A[i+j]
      num+=zero_list[i+j]-(i+j)
    j+=zero_list[i+j]-(i+j)
      
print(num)
### BUGGY CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
ans = 0
st = 0
go = k
cnt = sum(a[:go])
for i in range(n-k):
    st += 1
    go += 1
    if cnt < sum(a[st:go]):
        print("Yes")
    else:
        print("No")
    cnt = sum(a[st:go])

### FIXED CODE ###

n,k = map(int,input().split())
a = list(map(int,input().split()))
for i in range(n-k):
    if a[i+k] > a[i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n,k=map(int,input().split())
s=input()
s+="?"

tmp=[]
l=1
for i in range(n):
    if s[i]==s[i+1]:
        l+=1
    else:
        tmp.append(l)
        l=1

for _ in range(k):
    if len(tmp)==1:
        break
    elif len(tmp)==2:
        tmp=[tmp[0]+tmp[1]]
        continue
    tmp=[tmp[0]+tmp[1]+tmp[2]]+tmp[3:]

ans=sum(tmp)-len(tmp)
print(ans)

### FIXED CODE ###

n,k=map(int,input().split())
s=input()
s+="?"

tmp=[]
l=1
for i in range(n):
    if s[i]==s[i+1]:
        l+=1
    else:
        tmp.append(l)
        l=1

RLs=max(1, len(tmp)-2*k)

ans=n-RLs
print(ans)
### BUGGY CODE ###

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

ans = 0
while n > 0:
    if n >= a:
        ans += a
        n -= a
    else:
        ans += n
        break
    n -= b

print(ans)

### FIXED CODE ###

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

ans = int(n/(a+b)) * a

if n%(a+b) <= a:
    ans += n%(a+b)
else:
    ans += a

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

n = int(input())
a = tuple(map(int, input().split()))
x = 1
for aa in a:
    x *= aa
if x > 10 ** 18:
    print(-1)
else:
    print(x)


### FIXED CODE ###

n = int(input())
a = tuple(sorted(map(int, input().split())))
x = 1
for aa in a:
    x *= aa
    if x > 10 ** 18:
        print(-1)
        exit(0)
print(x)
### BUGGY CODE ###

n, max_w = map(int, input().split())

w = []
v = []
for i in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

dp = [[0 for _ in range(max_w+1)] for _ in range(n+2)]

for i in range(1, n+1):
    for j in range(max_w+1):
        dp[i][j] = max(dp[i][j], dp[i-1][j])
        if j >= w[i-1]:
            dp[i][j] = max(dp[i][j], dp[i-1][j-w[i-1]]+v[i-1])

print(max(dp[n]))

### FIXED CODE ###

n, max_w = map(int, input().split())

w = []
v = []
for i in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

f_inf = float('inf')
max_v = 100000

dp = [f_inf]*(max_v+2)
dp[0] = 0

for i in range(1, n+1):
    for j in range(max_v+1, -1, -1):
        if j >= v[i-1]:
            dp[j] = min(dp[j], dp[j-v[i-1]]+w[i-1])

ans = 0
for i in range(max_v+1):
    if dp[i] <= max_w:
        ans = max(ans, i)
print(ans)
### BUGGY CODE ###

import math
K = int(input())

def gcd(a,b,c):
  return math.gcd(math.gcd(a, b), c)

s = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    for c in range(1, K+1):
      s += gcd(a, b, c)
      
print(s)

### FIXED CODE ###

import math
K = int(input())
 
s = 0
for a in range(1, K+1):
  for b in range(1, K+1):
    d = math.gcd(a, b)
    for c in range(1, K+1):
      s += math.gcd(d, c)
      
print(s)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
d=[]
for i in range(m):
  b,c = map(int,input().split()) 
  d.extend([c]*b)
if n < len(d):
  d=d[:n]
d.sort(reverse=True)
for i in range(len(d)):
  for j in range(i,n):
    if a[j] < d[i]:
      a[j]=d[i]
      break
print(sum(a))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1])
for b,c in bc[::-1]:
  a.extend([c]*b)
  if len(a)>2*n:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

import itertools

n=int(input())
a=list(map(int,input().split()))
l=list(range(1,n+1))
ans=(list([a[x-1],a[y-1]] for x,y in (itertools.combinations(l, 2)) if x<y and a[x-1]!=x and a[y-1]!=y and a[x-1]==y and a[y-1]==x))
print (len(ans))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a = [None] + a
cnt = 0
for i in range(1, n):
  j = a[i]
  if j > i and a[j] == i:
    cnt += 1
print(cnt)
### BUGGY CODE ###

from functools import reduce
n=int(input())
a=list(map(int,input().split()))
c=list(range(1,n+1))
num=list(map(lambda t:reduce(lambda a,b:a+1 if b==t else a,a,0),c))
preans=reduce(lambda x,y:x+y*(y-1)/2,num,0)
for i in range(n):
    print(int(preans-num[a[i]-1]+1))

### FIXED CODE ###

from functools import reduce
n=int(input())
a=list(map(int,input().split()))
c=list(range(1,n+1))
num=[0]*n
for i in range(n):
    num[a[i]-1]=num[a[i]-1]+1
preans=reduce(lambda x,y:x+y*(y-1)/2,num,0)

for i in range(n):
    print(int(preans-num[a[i]-1]+1))
### BUGGY CODE ###

import numpy as np

N = int(input())
X = [int(i) for i in input().split()]

arrayX = np.array(X)
num = arrayX.size

for i in range(num):
    arrayX = np.delete(arrayX,i)
    print(int(np.median(arrayX)))
    arrayX = np.array(X)

### FIXED CODE ###

N = int(input())
X = [int(i) for i in input().split()]

sortedX = X[:]
sortedX.sort()
lenX = len(X)

for i in X:
    if i > sortedX[int(lenX/2) - 1]:
        print(sortedX[int(lenX/2)-1])
    else:
        print(sortedX[int(lenX/2)])
### BUGGY CODE ###

N, x = list(map(int, input().split()))
n = N
a = list(map(int, input().split()))
b = [[1000000000000000000000 for i in range(n)] for j in range(n)]
for i in range(n):
	b[i][0] = a[i]
	for j in range(1, n):
		b[i][j] = min(b[i][j-1], a[(i-j+n)%n])
s = [0 for i in range(n)]
for i in range(n):
	for j in range(n):
		s[j] += b[i][j]
ans = 1000000000000000000000
for i in range(n):
	for j in range(n):
		ans = min(ans, j*x+s[j])
print(ans)


### FIXED CODE ###

N, x = list(map(int, input().split()))
n = N
a = list(map(int, input().split()))
b = [[1000000000000000000000 for i in range(n)] for j in range(n)]
for i in range(n):
	b[i][0] = a[i]
	for j in range(1, n):
		b[i][j] = min(b[i][j-1], a[(i-j+n)%n])
s = [0 for i in range(n)]
for i in range(n):
	for j in range(n):
		s[j] += b[i][j]
ans = 1000000000000000000000
for i in range(n):
	for j in range(n):
		ans = min(ans, j*x+s[j])
print(ans)
### BUGGY CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(10**7)
n = int(input())
B = list(map(int, input().split()))
c = Counter(B)
A = []
history = []


def dfs(i):
    if i == n+1:
        if A == B:
            print(*history, sep='\n')
            exit()
        return 0
    for j in reversed(range(1, i+1)):
        if not c[j]:
            continue
        c[j] -= 1
        history.append(j)
        A.insert(j-1, j)
        dfs(i+1)
        A.pop(j-1)
        history.pop()
        c[j] += 1


dfs(1)
print(-1)

### FIXED CODE ###

n = int(input())
B = list(map(int, input().split()))
A = []
for b in B:
    A.insert(b-1, b)
if all(A[i] <= i+1 for i in range(n)):
    C = []
    for a in A:
        C.insert(a-1, a)
    if B == C:
        print(*A, sep='\n')
    else:
        print(-1)
else:
    print(-1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
fir = []
sec = []

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        fir.append(b)
    elif a == n:
        sec.append(b)
    if b == 1:
        fir.append(a)
    elif b == n:
        sec.append(a)

for i in fir:
    if i in sec:
        print("POSSIBLE")
        break
else:
    print("IMPOSSIBLE")

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
fir = []
sec = []

for _ in range(m):
    a, b = map(int, input().split())
    if a == 1:
        fir.append(b)
    elif a == n:
        sec.append(b)
    if b == 1:
        fir.append(a)
    elif b == n:
        sec.append(a)
fir.sort()
sec.sort()
flag = True
for i in fir:
    j = 0
    while flag and sec:
        if i > sec[j]:
            del sec[j]
        elif i == sec[j]:
            print("POSSIBLE")
            flag = False
        else:
            break
if flag == True:
    print("IMPOSSIBLE")
### BUGGY CODE ###

h, w = map(int, input().split())
grid = [[0] * (w + 1)]
for _ in range(h):
    grid.append([0] + list(map(int, input().split())))
for i in range(1, h + 1):
    l = [0] + list(map(int, input().split()))
    for j in range(w + 1):
        grid[i][j] = abs(grid[i][j] - l[j])

biggest = max([max(i) for i in grid])
m = (h + w) * biggest

if m == 0:
    print(0)
    exit()

unba = [[[False] * m for _ in range(w + 1)] for _ in range(h + 1)]

for i in range(1, w + 1):
    unba[0][i][0] = True
for i in range(1, h + 1):
    unba[i][0][0] = True

for i in range(1, h + 1):
    for j in range(1, w + 1):
        for k in range(m):
            if unba[i-1][j][k] or unba[i][j-1][k]:
                unba[i][j][grid[i][j] + k] = True
                unba[i][j][abs(grid[i][j] - k)] = True

l = [i for i in range(m) if unba[h][w][i]]
print(min(l))

### FIXED CODE ###

def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    h, w = map(int, input().split())
    g = []
    for _ in range(h):
        g.append(list(map(int, input().split())))
    for i in range(h):
        k = list(map(int, input().split()))
        for j in range(w):
            g[i][j] = abs(g[i][j] - k[j])

    m = (h + w) * 80

    if m == 0:
        print(0)
        exit()

    dp = [[False] * m for _ in range(w)]
    dp[0][g[0][0]] = True
    for j in range(1, w):
        for k in range(m):
            if dp[j-1][k]:
                dp[j][abs(k - g[0][j])] = True
                dp[j][k + g[0][j]] = True
    
    for i in range(1, h):
        new_dp = [[False] * m for _ in range(w)]
        for k in range(m):
            if dp[0][k]:
                new_dp[0][abs(k - g[i][0])] = True
                new_dp[0][k + g[i][0]] = True
        
        for j in range(1, w):
            for k in range(m):
                if new_dp[j-1][k] or dp[j][k]:
                    new_dp[j][abs(k - g[i][j])] = True
                    new_dp[j][k + g[i][j]] = True
        dp = new_dp

    for j in range(m):
        if dp[w-1][j]:
            print(j)
            break

main()
### BUGGY CODE ###

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

### FIXED CODE ###

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

if 0 in A:
  ans = 0
  
else:
  ans = 1
  for i in range(N):
    ans *= A[i]
    if ans > 10**18:
      ans = -1
      break

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

from collections import deque


def main():
    N, M = map(int, input().split())
    dp = [[set() for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        dp[0][v-1].add(u-1)
    S, T = map(int, input().split())
    for i in range(1, 3):
        for j in range(N):
            tmp = list()
            for nxt in dp[i-1][j]:
                tmp += list(dp[0][nxt])
            dp[i][j] = set(tmp)
    adj = [set() for _ in range(N)]
    for i in range(N):
        for j in dp[2][i]:
            adj[j].add(i)
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N*3)]
    dp = [[[] for _ in range(N)] for _ in range(3)]
    for _ in range(M):
        u, v = map(int, input().split())
        u -= 1
        v -= 1
        adj[u].add(N*1+v)
        adj[N*1+u].add(N*2+v)
        adj[N*2+u].add(v)
    S, T = map(int, input().split())
    searchq = deque()
    visited = set()
    searchq.append((S-1, 0))
    visited.add(S-1)
    while len(searchq):
        p, cost = searchq.popleft()
        if p == T-1:
            print(cost//3)
            return
        for nxt in adj[p]:
            if nxt not in visited:
                searchq.append((nxt, cost+1))
                visited.add(nxt)
    print(-1)


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

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
#import itertools
#import heapq
#from collections import deque
#d = deque()

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    mod=998244353
    dp=[0]*(2*(10**5)+10)
    dp[0]=1
    n,k=map(int, readline().rstrip().split())
    #s=set()
    #lr=[0]*(2*(10**5)+10)
    ll=[0]*(2*(10**5)+10)
    rr=[0]*(2*(10**5)+10)
    for i in range(k):
        ll[i],rr[i]=map(int, readline().rstrip().split())
    for i in range(n-1):
        if dp[i] == 0:
            continue
        for j in range(k):
            for x in range(ll[j],rr[j]+1):
                if (i+x) > n:
                    break
                dp[i+x] += dp[i]
                dp[i+x]%=mod
    print(dp[n-1])
    #for i in range(n):
    #    if i > 0:
    #        lr[i]+=lr[i-1]
    #    if lr[i] > 0:
    #        s.add(i)

    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------

### FIXED CODE ###

### ----------------
### ここから
### ----------------

import sys
from io import StringIO
import unittest
#import itertools
#import heapq
#from collections import deque
#d = deque()

def yn(b):
    print("Yes" if b==1 else "No")
    return

def resolve():
    readline=sys.stdin.readline
    mod=998244353
    dp=[0]*(2*(10**5)+10)
    dp[0]=1
    n,k=map(int, readline().rstrip().split())
    #s=set()
    #lr=[0]*(2*(10**5)+10)
    ll=[0]*(2*(10**5)+10)
    rr=[0]*(2*(10**5)+10)
    for i in range(k):
        ll[i],rr[i]=map(int, readline().rstrip().split())
    for i in range(n-1):
        if i > 0:
            dp[i]+=dp[i-1]

        if dp[i] == 0:
            continue

        for j in range(k):
            if i+ll[j] <= n:
                dp[i+ll[j]] += dp[i]
                dp[i+ll[j]]%=mod
            if i+rr[j]+1 <= n:
                dp[i+rr[j]+1] -= dp[i]
                dp[i+rr[j]+1]%=mod
    print(dp[n-1])
    #for i in range(n):
    #    if i > 0:
    #        lr[i]+=lr[i-1]
    #    if lr[i] > 0:
    #        s.add(i)

    #arr=list(map(int, readline().rstrip().split()))
    #n=int(readline())
    #ss=readline().rstrip()
    #yn(1)

    return

if 'doTest' not in globals():
    resolve()
    sys.exit()

### ----------------
### ここまで 
### ----------------
### BUGGY CODE ###

n,q = map(int,input().split())
s = input().replace("AC","aC")
L = [0]*n
for i in range(n):
    if s[i] == "a":
        L[i] = 1

for i in range(q):
    l,r = map(int,input().split())
    print(sum(L[l-1:r-1]))


### FIXED CODE ###

n,q = map(int,input().split())
s = input().replace("AC","aC")
L = [0]*n
cnt = 0
for i in range(1,n):
    if s[i-1] == "a":
        cnt += 1
    L[i]=cnt
        
for i in range(q):
    l,r = map(int,input().split())
    print(L[r-1] - L[l-1])