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

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

cost = [[float("inf") for i in range(n)] for i in range(n)] 

for i in range(m):
    ai,bi=map(int, input().split())
    cost[ai-1][bi-1] = 1
    cost[bi-1][ai-1] = 1
    

def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d

################################
        
q=dijkstra(0,n,m,cost)
r=[0]*n
for i in range(1,len(q)):
    qmin=10**10
    for j in range(n):
        if cost[i][j]==1:
            if qmin>q[j]:
                qmin=q[j]
                r[i]=j

if max(q)==float("inf"):
    print("No")
else:
    print("Yes")
    for i in range(1,len(q)):
        print(r[i]+1)
                

### FIXED CODE ###

import sys
from collections import deque

icase=0
if icase==0:
    n,m=map(int,input().split())
    g = [[] for _ in range(n)]
    for i in range(m):
        ai,bi=map(int,input().split())
        g[ai-1].append(bi-1)
        g[bi-1].append(ai-1)
elif icase==1:
    n,m=4,4
    g=[[1], [0, 2, 3], [1, 3], [2, 1]]
elif icase==2:
    n,m=6,9
    g=[[5, 4], [3, 5], [3, 4], [2, 1, 5, 4], [2, 0, 3, 5], [0, 3, 1, 4]]

q=deque([0])

stack=[0]
parent=[-1]*n
parent[0]=0
dist=[-1]*n
dist[0]=0
while q:
    state = q.popleft()
#    print("--- q:",q,"state:",state,"g:",g[state],"p:",parent)
    for v in g[state]:
#        print("  state:",state,"v:",v,"q:",q)
#        if parent[state] == v:
        if parent[v] !=-1:
            continue
        else:
#            print("parent:",parent,"xx:",xx,"stack",stack)
            parent[v]=state
            dist[v]=dist[state]+1
            q.append(v)
#            print(" state:",state,"v:",v,"parent:",parent,"stack",stack,"dist[v]",dist[v])
for i in range(1,n):
    if parent[i]==-1:
        print("No")
        sys.exit()

print("Yes")
for i in range(1,n):
#    print(i+1,dist[i])    
    print(parent[i]+1)
### BUGGY CODE ###

from itertools import combinations

n = int(input())
ls = list(map(int, input().split()))
ls.sort()

count = 0
# for a, b, c in combinations(ls, 3):
#     if a < b + c and b < c + a and c < a + b:
#         count += 1
for j in range(n - 1, 1, -1):
    last = ls[j]
    for a, b in combinations(ls[:j], 2):
        if a + b > last:
            count += 1

print(count)

### FIXED CODE ###

# from itertools import combinations
from bisect import bisect_left

n = int(input())
ls = list(map(int, input().split()))
ls.sort()

count = 0

# for a, b, c in combinations(ls, 3):
#     if a < b + c and b < c + a and c < a + b:
#         count += 1

# for j in range(n - 1, 1, -1):
#     last = ls[j]
#     for a, b in combinations(ls[:j], 2):
#         if a + b > last:
#             count += 1

for i in range(n - 1, 1, -1):
    for j in range(i - 1, 0, -1):
        idx = bisect_left(ls[:j], ls[i] - ls[j] + 1)
        if idx < j:
            count += j - idx

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

import math
N,K = map(int,input().split())
A = [-1]+list(map(int,input().split()))
B = [0] * (N+1)
B[0] = -1

for _ in range(K):
  for i,a in enumerate(A):
    if i==0: continue
    for j in range(max(math.ceil(i-a-0.5),0), min(math.floor(i+a+0.5),N)+1):
      B[j] += 1

  A = B[::]
  B = [0] * (N+1)

print(" ".join(map(str, A[1:])))

### FIXED CODE ###

from itertools import accumulate

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

for _ in range(K):
  arr = [0]*(N+1)
  for i, a in enumerate(A):
    left = max(0, i-a)
    right = min(N, i+a+1)
    arr[left] += 1
    arr[right] -= 1
  
  A = list(accumulate(arr[:-1]))
  if all(a == N for a in A):
    break

print(*A, sep=" ")
### BUGGY CODE ###

def PrimeFactorization(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1:
        pf[m] = 1
    return pf


def lcmlist(l):
    from collections import defaultdict
    d = defaultdict(int)
    for i in set(l):
        for k, v in PrimeFactorization(i).items():
            d[k] = max(d[k], v)
    n = 1
    for k, v in d.items():
        n *= k ** v
    return n

n=int(input())
a=list(map(int,input().split()))
x=lcmlist(a)
ans=0
for i in a:
  ans+=x//i
  ans%=1000000007
print(ans)

### FIXED CODE ###

def PrimeFactorization(m):
    pf = {}
    for i in range(2, int(m ** 0.5) + 1):
        while m % i == 0:
            pf[i] = pf.get(i, 0) + 1
            m //= i
    if m > 1:
        pf[m] = 1
    return pf


def lcmlist(l):
    from collections import defaultdict
    d = defaultdict(int)
    for i in set(l):
        for k, v in PrimeFactorization(i).items():
            if v > d[k]:
                d[k] = v
    n = 1
    for k, v in d.items():
        n *= k ** v
    return n

n=int(input())
a=list(map(int,input().split()))
x=lcmlist(a)
ans=0
for i in a:
  ans+=x//i
ans%=1000000007
print(ans)
### BUGGY CODE ###

MOD = 10 ** 9 + 7
ans = 1

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

pos = []
neg = []

for x in a:
    if x >= 0:
        pos.append(x)
    else:
        neg.append(x)

pos.sort(reverse=True)
neg.sort()

if n == k:
    for x in a:
        ans *= x
    print(ans % MOD)

elif len(pos) == 0 and k % 2:
    for i in range(1, k+1):
        ans *= neg[-i]
    print(ans % MOD)

else:
    if k % 2:
        ans *= pos.pop(0)
        k -= 1
    
    l = []
    
    for i in range(1, len(pos), 2):
        l.append(pos[i] * pos[i - 1])
    
    for i in range(1, len(neg), 2):
        l.append(neg[i] * neg[i - 1])
    
    l.sort(reverse=True)
    
    for i in range(k // 2):
        ans *= l[i]
        ans %= MOD
    
    print(ans % MOD)
    

### FIXED CODE ###

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

MOD = 10 ** 9 + 7
ans = 1

#全部取る
if n == k:
    for x in a:
        ans *= x
        ans %= MOD
    print(ans % MOD)

#全部負かつ奇数個取る
elif max(a) < 0 and k % 2:
    a.sort()
    for i in range(1, k+1):
        ans *= a[-i]
        ans %= MOD
    print(ans % MOD)

else:
    pos = []
    neg = []
    
    for x in a:
        if x >= 0:
            pos.append(x)
        else:
            neg.append(x)
    
    pos.sort(reverse=True)
    neg.sort()
    
    
    if k % 2:
        ans *= pos.pop(0)
        k -= 1
     
    #2個ずつ取る
    num = []
    for x, y in zip(pos[::2], pos[1::2]):
        num.append(x * y)
    for x, y in zip(neg[::2], neg[1::2]):
        num.append(x * y)

    num.sort(reverse=True)

    for i in range(k // 2):
        ans *= num[i]
        ans %= MOD
    
    print(ans % MOD)
### BUGGY CODE ###

from math import sqrt

n = int(input())

if n == 1:
    print(0)

n_sqrt = int(sqrt(n))

dp = [-1] * (n_sqrt+2)

for i in range(2, n_sqrt+2):
    if dp[i] == -1:
        dp[i] = 1
        for j in range(i*2, n_sqrt+2, i):
            dp[j] = 0

prime = []

for i in range(2, n_sqrt+2):
    if dp[i] == 1:
        prime.append(i)

prime.append(n)

memo = []
for p in prime:
    cnt = 0
    while n%p==0:
        n //= p
        cnt += 1

    if cnt:
        memo.append(cnt)

if n > 1:
    memo.append(1)

ans = 0

for j in memo:
    k = 1
    while True:

        if k*(k+1)//2 <= j <= k*(k+3)//2:
            ans += k
            break
        k += 1

print(ans)

### FIXED CODE ###

from math import sqrt

n = int(input())

if n == 1:
    print(0)
    exit()

n_sqrt = int(sqrt(n))

dp = [-1] * (n_sqrt+2)

for i in range(2, n_sqrt+2):
    if dp[i] == -1:
        dp[i] = 1
        for j in range(i*2, n_sqrt+2, i):
            dp[j] = 0

prime = []

for i in range(2, n_sqrt+2):
    if dp[i] == 1:
        prime.append(i)

prime.append(n)

memo = []
for p in prime:
    cnt = 0
    while n%p==0:
        n //= p
        cnt += 1

    if cnt:
        memo.append(cnt)

if n > 1:
    memo.append(1)

ans = 0

for j in memo:
    k = 1
    while True:

        if k*(k+1)//2 <= j <= k*(k+3)//2:
            ans += k
            break
        k += 1

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



import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

import math
from fractions import gcd

A, B = map(int, input().split())

# 最大公約数
g = gcd(A, B)

if g == 1:
    print(1)
    exit()

ggg = []
for i in range(1, g+1):
    if A%i == 0 and B%i == 0:
        ggg.append(i)

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    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]

prime = get_sieve_of_eratosthenes(g)
phash = {}
for p in prime:
    phash[p] = True

#print(prime)
#print(phash)

count = 0
for c in ggg:
    if c in phash:
        count += 1


print(count+1)

### FIXED CODE ###


import sys
input = sys.stdin.readline
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
# A = [ int(input()) for _ in range(N) ]
##############################

from fractions import gcd

A, B = map(int, input().split())

# 最大公約数
g = gcd(A, B)

if g == 1:
    print(1)
    exit()

def prime_factorize(n):
    a = set()
    while n % 2 == 0:
        a.add(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.add(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.add(n)
    return a

print(len(prime_factorize(g)) +1)
### BUGGY CODE ###

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

weight = [0] * N
value = [0] * N
for i in range(N):
    w, v = map(int, input().split())
    weight[i], value[i] = w, v

dp = [[0]*(W+1) for _ in range(N)]
for i in range(weight[0], W+1):
    dp[0][i] = value[0]

for i in range(1, N):
    for ws in range(W+1):
        if ws - weight[i] >= 0:
            dp[i][ws] = dp[i-1][ws - weight[i]] + value[i]
        dp[i][ws] = max(dp[i][ws], dp[i-1][ws])

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

### FIXED CODE ###

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

weight = [0] * N
value = [0] * N
for i in range(N):
    w, v = map(int, input().split())
    weight[i], value[i] = w, v

dp = [[0]*(W+1) for _ in range(N)]
for i in range(weight[0], W+1):
    dp[0][i] = value[0]

for i in range(1, N):
    for ws in range(W+1):
        if ws - weight[i] >= 0:
            dp[i][ws] = dp[i-1][ws - weight[i]] + value[i]
        dp[i][ws] = max(dp[i][ws], dp[i-1][ws])

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

z = []
while True:
	try:
		a, b, c, d, e, f = map(float, raw_input().split())
		x = (c * e - b * f) / (a * e - d * b)
		y = (c * d - f * a) / (b * d - e * a)
		z.append([x, y])
	
	except:
		print(z)

### FIXED CODE ###

z = []
while True:
	try:
		a, b, c, d, e, f = map(float, raw_input().split())
		x = (c * e - b * f) / (a * e - d * b)
		y = (c * d - f * a) / (b * d - e * a)
		z.append([x, y])
	
	except:
		break
for i in z:
	print("{:.3f} {:.3f}".format(i[0] + 0, i[1] + 0))
### BUGGY CODE ###

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

l=[]
i=n
aa=s.rfind('.')
bb=s.find('.')
ans=min(s[:aa+1].count('.'),s[:aa+1].count('#'))
while i>=0:
    a=s[:i].rfind('.')
    ans=min(ans,(1+min(s[:a+1].count('.'),s[:a+1].count('#'))))
    #print(ans,a)
    i=a
    if a==bb:
        break

print(ans)



### FIXED CODE ###

n=int(input())
s=str(input())
a=0
b=s.count('.')
l=[b]
for i in range(n):
    if s[i]=='#':
        a+=1
    if s[i]=='.':
        b-=1
    l.append(a+b)
print(min(l))
### BUGGY CODE ###

def e_roaming(MOD=10**9 + 7):
    N, K = [int(i) for i in input().split()]
    from operator import mul
    from functools import reduce

    def cmb(n, r):
        if n - r < r:
            r = n - r
        if r == 0:
            return 1
        if r == 1:
            return n

        numerator = [n - r + k + 1 for k in range(r)]
        denominator = [k + 1 for k in range(r)]

        for p in range(2, r + 1):
            pivot = denominator[p - 1]
            if pivot > 1:
                offset = (n - r) % p
                for k in range(p - 1, r, p):
                    numerator[k - offset] /= pivot
                    denominator[k] /= pivot

        result = 1
        for k in range(r):
            if numerator[k] > 1:
                result *= int(numerator[k])
                result %= MOD

        return result

    return cmb(2 * N - 1, N) if K >= N - 1 else sum([cmb(N, k) * cmb(N - 1, k) % MOD for k in range(K + 1)]) % MOD

print(e_roaming())

### FIXED CODE ###

def e_roaming(MOD=10**9 + 7):
    N, K = [int(i) for i in input().split()]

    class Combination(object):
        """参考: https://harigami.net/contents?id=5f169f85-5707-4137-87a5-f0068749d9bb"""
        __slots__ = ['mod', 'factorial', 'inverse']

        def __init__(self, max_val_arg: int = 10**6, mod: int = 10**9 + 7):
            fac, inv = [1], []
            fac_append, inv_append = fac.append, inv.append

            for i in range(1, max_val_arg + 1):
                fac_append(fac[-1] * i % mod)

            # inv_append(pow(fac[-1], -1, mod)) (after Python 3.8)
            inv_append(pow(fac[-1], mod - 2, mod))

            for i in range(max_val_arg, 0, -1):
                inv_append((inv[-1] * i) % mod)

            self.mod, self.factorial, self.inverse = mod, fac, inv[::-1]

        def combination(self, n, r):
            r = min(r, n - r)
            if n < 0 or r < 0 or n < r:
                return 0
            return self.factorial[n] * self.inverse[r] * self.inverse[n - r] % self.mod

    comb = Combination(N).combination
    if K >= N:
        K = N - 1  # N 回以上移動することは、N-1 回移動することと同じ結果を生む
    return sum(comb(N, k) * comb(N - 1, k) % MOD for k in range(K + 1)) % MOD

print(e_roaming())
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

INF = 10**18

N = int(readline())
ABC = [list(map(int, readline().split())) for _ in range(N - 1)]
Q, K = map(int, readline().split())
XY = [list(map(int, readline().split())) for _ in range(Q)]


def warshall_floyd(dist):
    for k, _ in enumerate(dist):
        for i, _ in enumerate(dist):
            for j, _ in enumerate(dist):
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
    return dist


dist = [[INF] * (N + 1) for _ in range(N + 1)]
for abc in ABC:
    dist[abc[0] - 1][abc[1] - 1] = abc[2]
    dist[abc[1] - 1][abc[0] - 1] = abc[2]

dist = warshall_floyd(dist)

for x, y in XY:
    print(dist[x - 1][K - 1] + dist[K - 1][y - 1])


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())

edges = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    a, b, c = map(int, readline().split())
    edges[a].append((b, c))
    edges[b].append((a, c))

Q, K = map(int, readline().split())

dist = [0] * (N + 1)


def dfs(v, p, d):
    dist[v] = d

    for n, dd in edges[v]:
        if n == p:
            continue
        dfs(n, v, d + dd)


dfs(K, -1, 0)

for _ in range(Q):
    x, y = map(int, readline().split())
    print(dist[x] + dist[y])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
assert len(S) == N

def solve(l, r):
    return sum(1 for i in range(l - 1, r - 1) if S[i : i + 2] == 'AC')

for i in range(Q):
    l, r = map(int, input().split())
    print(solve(l, r))

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
assert len(S) == N

AC = [S[i : i + 2] == 'AC' for i in range(len(S) - 1)]

nAC = [0]  # nAC[i] == the number of 'AC' whose head 'A' is in S[:i]
for i in range(len(AC)):
    nAC.append(nAC[-1] + (1 if AC[i] else 0))

def solve(l, r):
    return nAC[r - 1] - nAC[l - 1]

for i in range(Q):
    l, r = map(int, input().split())
    print(solve(l, r))
### BUGGY CODE ###

def prime(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes
pp=prime(10**3)
p=[]
for i in range(2,1001):
  if pp[i]:
    p.append(i)
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

g=a[0]
for i in a[1:]:
  g=gcd(g,i)
if g==1:
  mm=[0 for i in range(10**6+1)]
  f=True
  for i in a:
    if mm[i] and i!=1:
      f=False
      break
    mm[i]=1
    for j in range(168):
      if i%p[j]==0:
        if mm[p[j]] and i!=p[j]:
          f=False
          break
        mm[p[j]]=1
        t=i//p[j]
        if mm[t] and t!=p[j] and i!=p[j]:
          f=False
          break
        mm[t]=1
    if not f:
      break
  if f:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")
      


### FIXED CODE ###

def prime(n):
    primes = [0, 1] * (n // 2 + 1)
    if n % 2 == 0:
        primes.pop()
    primes[1] = 0
    primes[2] = 1
    for p in range(3, n + 1, 2):
        if primes[p]:
            for q in range(p * p, n + 1, 2 * p):
                primes[q] = 0
    return primes
pp=prime(10**3)
p=[]
for i in range(2,1001):
  if pp[i]:
    p.append(i)
n=int(input())
a=list(map(int,input().split()))
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

g=a[0]
for i in a[1:]:
  g=gcd(g,i)
if g==1:
  mm=[0 for i in range(10**6+1)]
  f=True
  for i in a:
    if mm[i] and i!=1:
      f=False
      break
    mm[i]=1
    si=i**0.5
    for j in range(168):
      if p[j]>si:
        break
      if i%p[j]==0 and i!=p[j]:
        if mm[p[j]]:
          f=False
          break
        mm[p[j]]=1
        t=i//p[j]
        if mm[t] and t!=p[j]:
          f=False
          break
        mm[t]=1
    if not f:
      break
  if f:
    print("pairwise coprime")
  else:
    print("setwise coprime")
else:
  print("not coprime")
### BUGGY CODE ###

n,a,b=list(map(int,input().split()))
from math import factorial as f
print(int(2**n-f(n)/(f(n-a)*f(a))-f(n)/(f(n-b)*f(b)))-1)

### FIXED CODE ###

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

p=10**9+7
ans1=1
ans2=1

for i in range(n-a+1,n+1):
    ans1*=i
    ans1%=p

for i in range(1,a+1):
    ans1*=pow(i,p-2,p)
    ans1%=p
    
for i in range(n-b+1,n+1):
    ans2*=i
    ans2%=p

for i in range(1,b+1):
    ans2*=pow(i,p-2,p)
    ans2%=p

print((pow(2,n,p)-ans1-ans2-1)%p)
### BUGGY CODE ###

import math

K = int(input());
gcd = 0;
gcd1 = 0;
gcd2 = 0;

for a in range(K):
  aa = a + 1 ;
  
  for b in range(K):
    bb = b + 1;
    
    for c in range(K):
      cc = c + 1;
      gcd1 = math.gcd(aa,bb);
      gcd2 = math.gcd(bb,cc);
      gcd += math.gcd(gcd1,gcd2);
      
print(gcd)
 
  


### FIXED CODE ###

from math import gcd
 
K = int(input());
sum = 0;

for a in range(1,K+1):
  for b in range(1,K+1):
    for c in range(1,K+1):
      sum += gcd(gcd(a,b),c);

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

from fractions import Fraction
from functools import reduce

n = int(input())
num = list(map(int, input().split()))
num = [ Fraction(i) for i in num ]

if 0 in num:
    print(0)
else:
    mult = reduce(lambda x, y: x*y, num)
    if mult > 10**18:
        print(-1)
    else:
        print(int(mult))

### FIXED CODE ###

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

limit = 10 ** 18
A.sort()
result = A[0]
for a in A[1:]:
    result *= a
    if result > limit:
        print(-1)
        exit()
print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import itertools

def main():
    n, k = map(int, input().split())

    n_li = list(range(n+1))

    ans = 0

    for i in range(k, n+2):
        ans += len(set(map(sum, itertools.combinations(n_li,i))))

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    MOD = 1000000007
    n, k = map(int, input().split())

    n_li = list(range(n+1))

    ans = 0

    while(k <= n+1):
        p = (k - 1) * k / 2
        q = ((n + n - k + 1) * k) / 2

        ans += q - p + 1
        ans %= MOD
        k += 1

    print(int(ans))

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

N=int(input())
List = list(map(int, input().split()))
AList = []

#i=1
for i in range(1,N+1):
    AList.append((List.index(i))+1)
    #i+=1
    
print(*AList)

### FIXED CODE ###

N=int(input())
List = list(map(int, input().split()))
AList = [0]*N
for i in range(0,N):
    S=List[i]
    AList[S-1]=i+1
    
print(*AList)
### BUGGY CODE ###

N,Q=map(int, input().split())
S=input()
for q in range(Q):
    l,r=map(int, input().split())
    print(S.count('AC',l-1,r))

### FIXED CODE ###

N,Q=map(int, input().split())
S=input()
lr=[list(map(int,input().split())) for i in range(Q)]
a=[0]*(N+1)
for i in range(2,N+1):
    if S[i-2:i]=='AC':
        a[i]=a[i-1]+1
    else:
        a[i]=a[i-1]
for q in range(Q):
    print(a[lr[q][1]]-a[lr[q][0]])
### BUGGY CODE ###

import bisect

N = int(input())
S = sorted([int(x) for x in input().split()])

Slimes = [S.pop(-1)]

flag = True
for i in range(1, N + 1):
    newSlimes = []
    for j in Slimes:
        idx = bisect.bisect_left(S, j)
        if idx == 0:
            flag = False
            break
        newSlimes.append(S.pop(idx-1))
    if not flag:
        break
    Slimes.extend(newSlimes)

print('Yes' if flag else 'No')

### FIXED CODE ###

N = int(input())
N2 = 1 << N

S = sorted([int(x) for x in input().split()])

s = []
s.append(S[-1])
S[-1] = -1

flag = True
for i in range(N):
    p = sorted([x for x in s])

    Si = N2 - 1
    while len(p) > 0 and Si >= 0:
        if S[Si] == -1:
            Si -= 1
            continue

        if S[Si] < p[-1]:
            s.append(S[Si])
            del p[-1]
            S[Si] = -1
        
        Si -= 1
    
    if len(p) > 0:
        flag = False

print('Yes' if flag else 'No')
### BUGGY CODE ###

a = int(input())
b = list(map(int, input().split()))
n = 0
for i in range(0,a):
    l = 0
    for j in range(0,i):
               if b[i] <= b[j]:
                    l += 1
    if l == i:
        n += 1
print(n)

### FIXED CODE ###

n = int(input())
m = list(map(int, input().split()))
l = 0
s = m[0]
for i in range(0,n):
    if s >= m[i]:
        s = m[i]
        l += 1
print(l)
### BUGGY CODE ###

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

for i in range(M):
  A_max = A[-1]
  if A_max==0: break
  A[-1] //= 2
  A = sorted(A)
print(sum(A))

### FIXED CODE ###

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

while M>0:
  A = sorted(A, reverse=True)
  a_ = A[0]//2
  for i,a_i in enumerate(A):
    if a_i > a_ and M>0:
      A[i] = a_i//2
      M -= 1
    else: break
  if a_==0: break
print(sum(A))
### BUGGY CODE ###

s = (input())
l = len(s)
c = 0
ans = [0] * l
answk = [1] * l

for x in range(10000) :
    ans = [0] * l

    for c in range(l) :
        if s[c] == 'R':
            ans[c+1] = ans[c+1] + answk[c]
        elif s[c] == 'L':
            ans[c-1] = ans[c-1] + answk[c]

    answk = ans.copy()

#print(ans)
print(str(ans).replace(',','').replace('[','').replace(']',''))

### FIXED CODE ###


s = (input())
l = len(s)
c = 0
ans = [0] * l
answk = [1] * l
cnt = 0
for c in range(l) :
    if s[c] == 'R':
        cnt += 1
    elif s[c] == 'L':
        ans[c-1] += cnt // 2 + cnt % 2
        ans[c] += cnt // 2
        cnt = 0
    

for d in range(l-1,-1,-1) :
    if s[d] == 'L':
        cnt += 1
    elif s[d] == 'R':
        ans[d+1] += cnt // 2 + cnt % 2
        ans[d] += cnt // 2
        cnt = 0

#print(ans)
print(str(ans).replace(',','').replace('[','').replace(']',''))