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

s = int(input())
k = int(input())

ans=0

n  = 5000000000000000

S = str(s) #文字列にする
saisho = 0

for i in range(len(S)):
  N = int(S[i])
  if saisho <= k <= saisho + N**n:#最初からの文字数
    ans = N
    break
    
  else:
    saisho += N**n
    
print(ans)

### FIXED CODE ###

s = int(input())
k = int(input())
S = str(s) #文字列にする

ans=0

for i in range(k):
  N = int(S[i])
  
  if N == 1:
    ans = 1
  else:
    ans = N
    break  
print(ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = [int(a) for a in input().split()]

A.sort()

# 積がx未満となる組み合わせの数を求める
def n_comb_lt(x):
    n_comb = 0
    for i in range(n - 1): # A[0], A[1], ..., A[n-2]について
        # i < jであるjのうち、A[i] * A[j] < xとなるjの数を求める
        if A[i] > 0:
            if A[i] * A[i + 1] >= x:
                n_partner = 0
            elif A[i] * A[n - 1] < x:
                n_partner = n - 1 - i
            else:
                ok = i + 1
                ng = n - 1

                # ok >= 1, ng <= 200000 - 1
                # log2(200000) < 18
                for _ in range(18):
                # while ng - ok > 1:
                    mid = (ng + ok) // 2
                    if A[i] * A[mid] < x:
                        ok = mid
                    else:
                        ng = mid
                n_partner = ok - i
        else:
            if A[i] * A[i + 1] < x:
                n_partner = n - 1 - i
            elif A[i] * A[n - 1] >= x:
                n_partner = 0
            else:
                ng = i + 1
                ok = n - 1
                # ok >= 1, ng <= 200000 - 1
                # log2(200000) < 18
                for _ in range(18):
                # while ok - ng > 1:
                    mid = (ng + ok) // 2
                    if A[i] * A[mid] < x:
                        ok = mid
                    else:
                        ng = mid
                n_partner = n - 1 - ng
        n_comb += n_partner

    return n_comb


ok = -10 ** 18 - 1
ng = 10 ** 18 + 1

for _ in range(62):
# while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid) < k:
        ok = mid
    else:
        ng = mid

print(ok)


### FIXED CODE ###

import numpy as np
import sys

input = sys.stdin.readline

n, k = [int(x) for x in input().split()]
A = np.array([int(a) for a in input().split()], dtype="int64")

A = np.sort(A)

A_pos = A[A > 0]
A_neg = A[A < 0]
A_zero = A[A == 0]

# 積がc以下となる組み合わせの数を求める
def n_comb_lt(c):
    n_comb = 0
    # A[i] > 0であるA[i]について
    target = c // A_pos  # target以下の値がA[i]の相方
    n_comb += np.searchsorted(A, target, side="right").sum()

    # A[i] == 0であるA[i]について
    n_comb += n * len(A_zero) if c >= 0 else 0

    # A[i] < 0であるA[i]について
    target = -(-c // A_neg)
    n_comb += (n - np.searchsorted(A, target, side="left")).sum()

    # 組み合わせのうち、A[i]*A[i]となっているものを引いて、2で割る
    n_comb -= A[A * A <= c].size
    n_comb //= 2

    return n_comb

ok = -10 ** 18 - 1
ng = 10 ** 18 + 1

# k番目の積は、積がm未満となる組み合わせがk個未満となる最大のm
# ←→積が(m-1)以下となる組み合わせがk個未満となる最大のm
while ng - ok > 1:
    mid = (ng + ok) // 2
    if n_comb_lt(mid - 1) < k:
        ok = mid
    else:
        ng = mid

print(ok)
### BUGGY CODE ###

#https://atcoder.jp/contests/agc033/tasks/agc033_a

HW = [int(i) for i in input().split()]
A = []
for i in range(HW[0]):
    A.append(list(str(input())))

B = []
for i in range(len(A)):
    B.append([])
    for j in range(len(A[i])):
        B[i].append(A[i][j])

count = 0
count2 = 0
flag = False
while True:
    for i in range(len(A)):
        for j in range(len(A[i])):
            if flag == True:
                if A[i][j] == '.':
                    B[i][j] = '#'
                else:
                    count += 1
                flag = False
            elif A[i][j] == '.':
                if i < len(A) - 1 and A[i+1][j] == '#':
                    B[i][j] = '#'
                elif i > 0 and A[i-1][j] == '#':
                    B[i][j] = '#'
                elif j < len(A[i]) - 1 and A[i][j+1] == '#':
                    B[i][j] = '#'
                elif j > 0 and A[i][j-1] == '#':
                    B[i][j] = '#'
            else:
                count += 1
                flag = True
    
    for i in range(len(A)):
        for j in range(len(A[i])):
            A[i][j] = B[i][j]
    if count == HW[0] * HW[1]:
        break
    else:
        count = 0
        count2 += 1

print(count2)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin
from itertools import permutations, combinations, product, accumulate
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from fractions import gcd
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 0, 1, -1, 1, -1, -1, 1]
dy = [1, -1, 0, 0, 1, -1, 1, -1]

h, w = MAP()
a = [STR() for _ in range(h)]
b = [[inf for _ in range(w)] for _ in range(h)]
ans = 0
for i in range(h):
    for j in range(w):
        if a[i][j] == '#':
            b[i][j] = 0
        else:
            for k in range(4):
                ny = i + dy[k]
                nx = j + dx[k]
                if 0 <= ny < h and 0 <= nx < w:
                    b[i][j] = min(b[ny][nx] + 1, b[i][j])
for i in reversed(range(h)):
    for j in reversed(range(w)):
        if a[i][j] == '#':
            b[i][j] = 0
        else:
            for k in range(4):
                ny = i + dy[k]
                nx = j + dx[k]
                if 0 <= ny < h and 0 <= nx < w:
                    b[i][j] = min(b[ny][nx] + 1, b[i][j])
ans = 0
for i in range(h):
    ans = max(ans, max(b[i]))
print(ans)
### BUGGY CODE ###

N, K, Q = map(int, input().split())
li = [K]*N
for i in range(Q):
    a = int(input())
    li = list(map(lambda x: x-1, li))
    li[a-1] += 1

for i in range(N):
    if li[i] <= 0:
        print("No")
    else:
        print("Yes")

### FIXED CODE ###

N, K, Q = map(int, input().split())
li = [K]*N
li = list(map(lambda x: x-Q, li))

for i in range(Q):
    a = int(input())
    li[a-1] += 1

for i in range(N):
    if li[i] <= 0:
        print("No")
    else:
        print("Yes")
### BUGGY CODE ###

A, B, C, X, Y = map(int, input().split())
ans = 1e1000
for i in range(X+1):
  for j in range(Y+1):
    for k in range(0, X+Y+1, 2):
      if i+k/2==X and j+k/2==Y:
        ans = min(ans, A*i+B*j+C*k)
print(ans)

### FIXED CODE ###

A, B, C, X, Y = map(int, input().split())
ans = float('INF')
for i in range(0, 2*max(X, Y)+1, 2):
  ans = min(ans, int(A*max(0, X-i/2)+B*max(0, Y-i/2)+C*i))
print(ans)
### BUGGY CODE ###

N=int(input())
x=input()

def popcount(X,ones,count): 
 
    if ones==0:
        return count
    else:
      
        X=X%ones
        
        count+=1
 
        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)
 
GroundOnes=x.count("1")
GroundX=int(x,2)
 
for i in range(N):
    if x[i]=="1":
        #x_ith="0"
        ones=GroundOnes-1
        X=GroundX-2**(N-i-1)
    else:
        #x_ith="1"
        ones=GroundOnes+1
        X=GroundX+2**(N-i-1)
            
 
    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    # print(" ------ return --- ",popcount(X,ones,0))
    print(popcount(X,ones,0))
        
    
    

### FIXED CODE ###

N=int(input())
x=input()
def popcount(X,ones,count): 
    #print(count,bin(X),X,ones)
    if ones==0:
        return count
    else:
      
        X=X%ones
        
        count+=1
 
        ones=str(bin(X)).count("1")
        
        return popcount(X,ones,count)
 

    
GroundOnes=x.count("1")
GroundX=int(x,2)

if GroundOnes>1:
    CaseOne= GroundX%(GroundOnes-1)
else:
    CaseOne=2

CaseZero= GroundX%(GroundOnes+1)

TwoPowerCaseOne=[]
TwoPowerCaseZero=[]

# if GroundOnes>1:
#     for j in range(N):
#       TwoPowerCaseOne.append(pow(2,(N-j-1) , (GroundOnes-1)))
#       TwoPowerCaseZero.append(pow(2**(N-j-1), (GroundOnes+1)))
# else:
#     for j in range(N):
#       TwoPowerCaseZero.append(pow(2**(N-j-1), (GroundOnes+1)))
  
    
for i in range(N):
    
    #CaseOne
    if x[i]=="1":
        ones=GroundOnes-1
        if ones>0:
            X=CaseOne-pow(2,N-i-1,ones)
        else:
            X=0
    #CaseZero
    else:
        ones=GroundOnes+1
        X=CaseZero+pow(2,N-i-1,ones)
            
 
    # print("for loop",i)
    # print("ones",ones)
    # print("new2bit",new2bit)
    #print(" ------ return --- ",popcount(X,ones,0))
    print(popcount(X,ones,0))
### BUGGY CODE ###

def main(n):
    l=[i for i in range(1,n+1)]
    ans=0
    for i in l:
        for j in l:    
            if str(i)[0]==str(j)[-1] and str(j)[0]==str(i)[-1]:
                # print(i,j)
                ans+=1
                
    print(ans)
n=int(input())
main(n)

### FIXED CODE ###

c={}
for i in range(1,10):
  for j in range(1,10):
    l=str(i)
    r=str(j)
    c[l+r]=0


n=int(input())
for i in range(1,n+1):
  l=str(i)[0]
  r=str(i)[-1]
  try:
    c[l+r]+=1
  except:
    pass
  
      
ans=0
for i in range(1,10):
  for j in range(1,10):
    l=str(i)
    r=str(j)
    ans+=c[l+r]*c[r+l]
    
    
print(ans)
### BUGGY CODE ###

n = int(input())
d = list(map(int,input().split()))
m = int(input())
tl = list(map(int,input().split()))
for t in tl:
  if t in d:
    d.remove(t)
  else:
    print('NO')
    exit()
print('YES')

### FIXED CODE ###

n = int(input())
dl = list(map(int,input().split()))
m = int(input())
tl = list(map(int,input().split()))
d_dic = dict()
t_dic = dict()
for d in dl:
  if d in d_dic:
    d_dic[d] += 1
  else:
    d_dic[d] = 1
for t in tl:
  if t in t_dic:
    t_dic[t] += 1
  else:
    t_dic[t] = 1
for v in t_dic.keys():
  if not v in d_dic.keys():
    print('NO')
    exit()
  if t_dic[v] > d_dic[v]:
    print('NO')
    exit()
print('YES')
### BUGGY CODE ###

N = int(input())
list = [int(input()) for i in range(N)]
list_max = sorted(list)
for i in range(N):
	if(list[i] == max(list)):
		print(list_max[-2])
	else:
		print(max(list))

### FIXED CODE ###

N = int(input())
list = [int(input()) for i in range(N)]
list_max = sorted(list)
max = max(list)
for i in range(N):
	if(list[i] == max):
		print(list_max[-2])
	else:
		print(max)
### BUGGY CODE ###

a,b,n=map(int,input().split())
max=0
for i in range(n,-1,-1):
    if max < (int((a*i)//b) - a*(int(i//b))):
        max=(int((a*i)//b) - a*(int(i//b)))
    if (int((a*i)//b) - a*(int(i//b))) < 0:
        break
print(max)


### FIXED CODE ###

A,B,N= map(int,input().split())
max_num = 0
x = min(B-1,N)
print(int((A*x)/B)-(A*int(x/B)))
### BUGGY CODE ###

N,Q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N-1)]
B = [list(map(int,input().split())) for i in range(Q)]

from collections import defaultdict,deque

G = defaultdict(list)

for i in range(N-1):
    G[A[i][0]].append(A[i][1])
    G[A[i][1]].append(A[i][0])

H = defaultdict(int)

for i in range(Q):
    H[B[i][0]] += B[i][1]

#bfs

r = 0
P = [0]*(N+1)  #ポイント

D = [0]+[-1]*(N)
D[1] = 1
P[1] = H[1]
q = deque([1])

while q:
    n = q.pop()
    for d in G[n]:
        if D[d] != -1:
            continue
        else:
            D[d] = 1
            q.appendleft(d)
            P[d] = P[n] + H[d]
del P[0]

print(*P)

### FIXED CODE ###

N,Q = map(int,input().split())
A = [list(map(int,input().split())) for i in range(N-1)]
B = [list(map(int,input().split())) for i in range(Q)]

G = {}
for i in range(1,N+1):
    G[i] = []

for i in range(N-1):
    G[A[i][0]].append(A[i][1])
    G[A[i][1]].append(A[i][0])

from collections import deque

H = {}
for i in range(1,N+1):
    H[i] = 0

for i in range(Q):
    H[B[i][0]] += B[i][1]

#bfs

r = 0
P = [0]*(N+1)  #ポイント

D = [0]+[-1]*(N)
D[1] = 1
P[1] = H[1]
q = deque([1])

while q:
    n = q.pop()
    for d in G[n]:
        if D[d] != -1:
            continue
        else:
            D[d] = 1
            q.appendleft(d)
            P[d] = P[n] + H[d]
del P[0]

print(*P)
### BUGGY CODE ###

def main():
    from collections import defaultdict,deque
    from math import ceil
    from sys import setrecursionlimit
    setrecursionlimit(10**6)
    f = lambda :map(int,input().split())
    n,u,v = f() # u:高橋
    edge = defaultdict(list)
    for i in range(n-1):
        a,b = f()
        edge[a].append(b)
        edge[b].append(a)
    
    distance = [[-1]*2 for _ in range(n+1)]
    distance[u][0] = 0
    distance[v][1] = 0
    def dfs(parent, start):
        distance_parent = distance[parent][start]
        for child in edge[parent]:
            if distance[child][start] == -1:
                distance[child][start] = distance_parent + 1
                dfs(child, start)
    dfs(u,0)
    dfs(v,1)
    ans = 0
    for u_d, v_d in distance:
        if u_d < v_d:
            ans = max(ans,v_d)
    print(ans-1)


        


main()
        



                
        
        
        
        
        



    


### FIXED CODE ###

def main():
    from collections import defaultdict,deque
    from math import ceil
    from sys import setrecursionlimit
    setrecursionlimit(10**6)
    f = lambda :map(int,input().split())
    n,u,v = f() # u:高橋
    edge = defaultdict(list)
    for i in range(n-1):
        a,b = f()
        edge[a].append(b)
        edge[b].append(a)
    
    distance = [[-1]*2 for _ in range(n+1)]
    distance[u][0] = 0
    distance[v][1] = 0
    def dfs(node,start):
        targets = deque([node])
        while targets:
            parent = targets.popleft()
            distance_parent = distance[parent][start]
            for child in edge[parent]:
                if distance[child][start] == -1:
                    distance[child][start] = distance_parent + 1
                    targets.append(child)
    dfs(u,0)
    dfs(v,1)
    ans = 0
    for u_d, v_d in distance:
        if u_d < v_d:
            ans = max(ans,v_d)
    print(ans-1)


        


main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A = list(map(int,input().split()))

B = [0 for _ in range(N)]
for i in A:
    B[i-1] += 1

for i in range(N):
    ans = 0
    C = B
    C = sorted(C, reverse = True)
    while C[i] != 0:
       
        for j in range(i+1):
               C[j] -= 1
        C = sorted(C, reverse = True)
        ans += 1
    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from collections import Counter
from itertools import accumulate

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

B = list(Counter(A).values())

C = [0] * N 
for i in B:
    C[i-1] += 1

F = list(accumulate(C))

S = [0] * N
f = [0] * N
S[0] = f[0] = sum(C) 
for i in range(2, N+1):
    S[i-1] = (S[i-2] + C[i-1] + S[0] - F[i-1] ) 
    f[i-1] = S[i-1] / i

f.sort()
n = 0     
K = 1
    
while K != N+1:
    if K <= f[n]:
        print(N-n)
        K += 1
    else:
        n += 1
    if n == N:
        for i in range(N-K+1):
            print(0)
        K = N+1
### BUGGY CODE ###

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

ans = 0
if 1 not in a:
  print(-1)
  sys.exit()
for i in range(1,n+1):
  if i in a:
    idx = a.index(i)
  else:
    ans += len(a) 
    break 
  ans += idx
  a = a[idx+1:]
  
print(ans)


### FIXED CODE ###

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

ans = 0
if 1 not in a:
  print(-1)
  sys.exit()
  
index = 1
for i in a:
  if i != index:
    ans+=1
  else:
    index+=1
    
print(ans)
### BUGGY CODE ###

import itertools
n,k = map(int,input().split())
p = list(map(int,input().split()))
lstp = []
for i in range(n-k+1):
    lstp.append(p[i:i+k])
#lstpp = []
#for j in lstp:
#    lstpp.append(0.5*(sum(j)+k))
lstpp = map(lambda x: 0.5*(sum(x)+k), lstp)
print("{:.10f}".format(max(lstpp)))

### FIXED CODE ###

n,k = map(int,input().split())
p = list(map(int,input().split()))
wa = sum(p[0:k])
next_wa = wa
for i in range(n-k):
    next_wa = next_wa - p[i] + p[i+k]
    if  next_wa > wa:
        wa = next_wa
print(0.5*(wa+k))
### BUGGY CODE ###

import numpy as np

N = int(input())

#A = [(i, a) for i, a in enumerate(map(int, input().split()), start=1)]
A = np.array(list(map(int, input().split())))
ind = [i for i in range(N)]
cnt = 0
for i in range(N):
    B = ind - np.array([i] * N)#マイナスは気にせず
    C = A + np.array(A[i])
    D = B - C
    cnt += np.count_nonzero(D == 0)
    #print(A,B,C,D)
print(cnt)

### FIXED CODE ###

import collections

N = int(input())
A = list(map(int, input().split()))
B = collections.defaultdict(int)
C = collections.defaultdict(int)

for i in range(N):
    B[i-A[i]] += 1 
    C[i+A[i]] += 1
#print(B)
#print(C)
ans = 0
for i in B:
    #print(i) i=Key
    if i in C:
        ans += B[i]*C[i]
print(ans)
### BUGGY CODE ###

l,r = map(int,input().split())
ans=2019
for i in range(l,r+1):
    for j in range(i+1,r+1):
        ans=min((i*j)%2019,ans)
        
        
print(ans)

### FIXED CODE ###

l,r = map(int,input().split())
ans=2019

for i in range(l,r+1):  
    if r-l>=2019:
        ans=0
        break
    for j in range(i+1,r+1):
        ans=min((i*j)%2019,ans)
                
print(ans)
### BUGGY CODE ###

# cook your dish here
n=int(input())
a=[int(x) for x in input().split()]
ans=1 
for i in range(n):
    ans*=a[i] 
if ans>(int)(1e18):
    ans=-1
print(ans)

### FIXED CODE ###

# cook your dish here
n=int(input())
a=[int(x) for x in input().split()]
ans=1  
mod=int(1e18)
for i in range(n):
    if a[i]==0:
        ans=0 
        break 
for i in range(n):
    ans*=a[i]
    if ans>mod:
        ans=-1 
        break 
    if ans==0:
        break
print(ans)
### BUGGY CODE ###

#%%
n = int(input())
a, b, c = [0] * n, [0] * n, [0] * n
for i in range(n-1):
    a[i], b[i], c[i] = map(int, input().split())

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

l = [[] for _ in range(n+1)]
for i in range(n-1):
    l[a[i]].append([b[i],c[i]])
    l[b[i]].append([a[i],c[i]])

d = [0] * (n+1)
check = [0] * (n+1)
check[k] = 1
que = [k]

while len(que) > 0:
    tmp = que.pop(0)
    for i in l[tmp]:
        if check[i[0]] == 0:
            que.append(i[0])
            check[i[0]] = 1
            d[i[0]] = d[tmp] + i[1]
        else:
            pass

x, y = [0] * q, [0] * q
for i in range(q):
    x[i], y[i] = map(int, input().split())
    print(d[x[i]] + d[y[i]])

### FIXED CODE ###

#%%
n = int(input())
a, b, c = [0] * n, [0] * n, [0] * n
for i in range(n-1):
    a[i], b[i], c[i] = map(int, input().split())

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

l = [[] for _ in range(n+1)]
for i in range(n-1):
    l[a[i]].append([b[i],c[i]])
    l[b[i]].append([a[i],c[i]])

d = [0] * (n+1)
check = [0] * (n+1)
check[k] = 1
que = [k]
count = 1

while len(que) > 0:
    tmp = que.pop(0)
    for i in l[tmp]:
        if check[i[0]] == 0:
            que.append(i[0])
            check[i[0]] = 1
            d[i[0]] = d[tmp] + i[1]
            count += 1
        else:
            pass
    if count >= n:
        break

x, y = [0] * q, [0] * q
for i in range(q):
    x[i], y[i] = map(int, input().split())
    print(d[x[i]] + d[y[i]])
### BUGGY CODE ###

from scipy.misc import comb
N = int(input())
s = []
for i in range(N):
  s += [''.join(sorted(input()))]
set_s = set(s)
cnt = 0
for j in set_s:
  cnt += comb(s.count(j),2)
print(int(cnt+0.5))

### FIXED CODE ###

from collections import Counter

N = int(input())
s = []
for i in range(N):
  s += [''.join(sorted(input()))]
cnt = sum([x*(x - 1) // 2 for x in Counter(s).values()])
print(int(cnt+0.5))
### BUGGY CODE ###

s = input()
p = 0
dp = [0] * 2019
dp[0] = 1
for i in range(len(s)):
    p = (p + (int(s[-1 - i]) * (10 ** (i)))) % 2019
    dp[p] += 1
ans = 0
for i in dp:
    ans += i * (i - 1) / 2
print(int(ans))

### FIXED CODE ###

s = input()[::-1]
p = 0
dp = [0] * 2019
dp[0] = 1
d = 1
for i in s:    
    p = (int(i) * d + (p)) % 2019
    dp[p] += 1
    d *= 10
    d = d % 2019
ans = 0
for i in dp:
    ans += i * (i - 1) // 2
print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

ans = 0
for i in range(N - 1):
    ans += (A[i] * sum(A[(i + 1):]))

print(ans % mod)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7

ans = 0
total = sum(A)
for i in range(N - 1):
    total -= A[i]
    ans += (A[i] * total) 

print(ans % mod)
### BUGGY CODE ###

n, k, q = map(int, input().split())
#print(n,k,q)
l = [0] * n
#print(l)
katen = []
my_append = katen.append
for i in range(q):
    my_append(int(input()))
#print(katen)

my_pop = l.pop
my_insert = l.insert
for j in katen:
    x = my_pop(j-1)
    my_insert(j-1, x+1) 
#print(l)

for y in range(n):
    if l[y] > q-k:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

n, k, q = map(int, input().split())
#print(n,k,q)
l = [0] * n
#print(l)
katen = []
my_append = katen.append
for i in range(q):
    my_append(int(input()))
#print(katen)

    
for j in katen:
    l[j-1] += 1 

    
#print(l)

for y in range(n):
    if l[y] > q-k:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = set()
stock = []
setmada = [start]
mode = 1
cost = 0

while len(setmada) > 0:
	while len(setmada) > 0:
		for i, j in list(setmada):
			stock.append((i, j))
			setmada.append((i, j))
			for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
				if k in yukaset:
					if k not in settansaku:
						setmada.append(k)
						settansaku.add((i, j))
	
	if goal in settansaku:
		mode = 0
		break
	
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					setmada.append(k)
	
	stock = []
	
	if goal in settansaku:
		mode = 0
		break

if mode == 0:
	print(cost)
else:
	print(-1)

### FIXED CODE ###

h,w = map(int,input().split())
sy, sx = map(int,input().split())
start = (sy-1, sx-1)
gy, gx = (map(int,input().split()))
goal = (gy-1, gx-1)

yukaset = set()

for i in range(h):
	chizu = input()
	for j in range(w):
		if chizu[j] == ".":
			yukaset.add((i, j))

settansaku = {start}
stock = []
listmada = [start]
mode = 1
cost = 0

while len(listmada) > 0:
	for i, j in listmada:
		stock.append((i, j))
		for k in [(i+1, j), (i-1, j), (i, j-1), (i, j+1)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)

	if goal in settansaku:
		mode = 0
		break
	
	listmada = []
	cost += 1
	for i, j in stock:
		for k in [(i-2, j-2), (i-1, j-2), (i, j-2), (i+1, j-2), (i+2, j-2), (i-2, j-1), (i-1, j-1), (i, j-1), (i+1, j-1), (i+2, j-1), (i-2, j), (i-1, j), (i+1, j), (i+2, j), (i-2, j+1), (i-1, j+1), (i, j+1), (i+1, j+1), (i+2, j+1), (i-2, j+2), (i-1, j+2), (i, j+2), (i+1, j+2), (i+2, j+2)]:
			if k in yukaset:
				if k not in settansaku:
					listmada.append(k)
					settansaku.add(k)
	
	stock = []

if mode == 0:
	print(cost)
else:
	print(-1)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
list = []
for i in range(N):
    if S[i:i+2] == 'AC':
        list.append(i)
count = 0
for i in range(Q): #l,rをそれぞれ代入
    l, r = map(int, input().split())
    for k in list: 
        if l-1 <= k <= r-1 and l-1 <= k+1 <= r-1:
            count += 1
    print(count)
    count = 0

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
count = [0]*N
for i in range(1, N): #i番目までに何個の'AC'があったかをリスト格納
    count[i] += count[i-1]
    if S[i-1:i+1] == 'AC':
        count[i] += 1
for i in range(Q):
    l, r = map(int, input().split())
    print(count[r-1]-count[l-1])