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

from collections import deque
X, Y, Z, K = map(int,input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

out = deque()
out2 = deque()

for i in range(X):
    for j in range(Y):
        out.append(A[i]+B[j])
out = list(out)
out.sort(reverse = True)
del out[K:]
for i in range(len(out)):
    for j in range(Z):
        out2.append(out[i]+C[j])
out2 = list(out2)
out2.sort(reverse = True)
for i in range(K):
    print(out2[i])


### FIXED CODE ###

from collections import deque
X, Y, Z, K = map(int,input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

out = deque()
out2 = deque()

for i in range(X):
    for j in range(Y):
        out.append(A[i]+B[j])
out = sorted(out, reverse=True)
del out[K:]
for i in range(len(out)):
    for j in range(Z):
        out2.append(out[i]+C[j])
out2 = sorted(out2, reverse=True)
for i in range(K):
    print(out2[i])
### BUGGY CODE ###

N, M = map(int, input().split())
cnt = 0
while N>0 and M>1:
    N -= 1
    M -= 2
    cnt += 1

while M>3:
    M -= 4
    cnt += 1
print(cnt)

### FIXED CODE ###

N, M = map(int, input().split())
cnt = 0

if N<=M//2:
    cnt = N
    N,M =0,M-2*N
    cnt += M//4
    print(cnt)
else:
    cnt = M//2
    print(cnt)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

S = input().strip()
Q = int(input())

reverse = False

before = ""
after = ""

for _ in range(Q):
    s = input().strip()
    if s[0] == "1":
        reverse = not reverse
    else:
        _, f, c = s.split()
        if f == "1":
            if reverse:
                after = after + c
            else:
                before = c + before
        else:
            if reverse:
                before = c + before
            else:
                after = after + c

if reverse:
    print(after[::-1] + S[::-1] + before[::-1])
else:
    print(before + S + after)


### FIXED CODE ###

import sys
input = sys.stdin.readline

S = input().strip()
Q = int(input())

reverse = False

before = ""
after = ""

for _ in range(Q):
    s = input().strip()
    if s[0] == "1":
        reverse = not reverse
    else:
        _, f, c = s.split()
        if f == "1":
            if reverse:
                after = after + c
            else:
                before = c + before
        else:
            if reverse:
                before = c + before
            else:
                after = after + c

if reverse:
    print(after[::-1] + S[::-1] + before[::-1])
else:
    print(before + S + after)
### BUGGY CODE ###

from queue import Queue
import sys
N, M = map(int,input().split())
edges = [[] for _ in range(3 * N)]
flag = [0] * (3 * N)
for _ in range(M):
    u, v = map(int,input().split())
    u -= 1
    v -= 1
    edges[u % (3 * N)].append((v + N) % (3 * N))
    edges[(u + N) % (3 * N)].append((v + 2 * N) % (3 * N))
    edges[(u + 2 * N) % (3 * N)].append(v % (3 * N))

S, T = map(int,input().split())
q = Queue()
q.put([0,S-1])
while not q.empty():
    p = q.get()
    if p[1] == T-1:
        print(p[0] // 3)
        sys.exit()
    for i in edges[p[1]]:
        if flag[i] == 0:
            flag[i] = 1
            q.put([p[0]+1,i])
print(-1)

### FIXED CODE ###

from queue import Queue
import sys
N, M = map(int,input().split())
edges = [[] for _ in range(3 * N)]
flag = [0] * (3 * N)
for _ in range(M):
    u, v = map(int,input().split())
    u -= 1
    v -= 1
    edges[u % (3 * N)].append((v + N) % (3 * N))
    edges[(u + N) % (3 * N)].append((v + 2 * N) % (3 * N))
    edges[(u + 2 * N) % (3 * N)].append(v % (3 * N))

S, T = map(int,input().split())
q = Queue()
q.put([0,S-1])
while not q.empty():
    p = q.get()
    if p[1] == T-1:
        print(p[0] // 3)
        sys.exit()
    for i in edges[p[1]]:
        if flag[i] == 0:
            flag[i] = 1
            q.put([p[0]+1,i])
print(-1)
### BUGGY CODE ###

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    print(0)
    g = {'Vacant':0, 'Male':1, 'Female':2}
    sl = g[input()]
    if sl == 0:
        return
    print(N-1)
    sr = g[input()]
    if sr == 0:
        return
    l = 0
    r = N-1
    while True:

        m = (l+r)//2
        print(m)
        a = g[input()]
        if a == 0:
            return
        
        if (m-l) % 2 == 1 and sl == a:
            r = m-1
            sr = a
        else:
            l = m+1
            sl = a
        




if __name__ == '__main__':
    main()

### FIXED CODE ###

#coding:utf-8
import sys,os
from collections import defaultdict, deque
from fractions import gcd
from math import ceil, floor
sys.setrecursionlimit(10**6)
write = sys.stdout.write
dbg = (lambda *something: print(*something)) if 'TERM_PROGRAM' in os.environ else lambda *x: 0
def main(given=sys.stdin.readline):
    input = lambda: given().rstrip()
    LMIIS = lambda: list(map(int,input().split()))
    II = lambda: int(input())
    XLMIIS = lambda x: [LMIIS() for _ in range(x)]
    YN = lambda c : print('Yes') if c else print('No')
    MOD = 10**9+7

    N = II()
    g = {'Vacant':0, 'Male':1, 'Female':2}



    print(0,flush=True)
    sl = g[input()]
    if sl == 0:
        return

    print(N-1,flush=True)
    sr = g[input()]
    if sr == 0:
        return
    
    l = 0
    r = N-1
    while r-l>1:

        m = (l+r)//2
        print(m,flush=True)
        a = g[input()]
        if a == 0:
            return
        
        if (m-l) % 2 == 1:
            if sl == a:
                r = m
                sr = a
            else:
                l = m
                sl = a

        else:
            if a != sl:
                r = m
                sr = a
            else:
                l = m
                sl = a
        

    print(-1)


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

n = int(input())
s = input()
passwords = []

for i in range(n-2):
    first =  s[i]
    for j in range(i+1,n-1):
        second = s[j]
        for k in range(j+1, n):
            password = first + second + s[k]
            if password not in passwords:
                passwords.append(password)

print(len(passwords))


### FIXED CODE ###

n = int(input())
s = input()
passwords = []

firsts = []
firsts_seconds = [[]*10 for _ in range(10)]
firsts_seconds_thirds = [[]*10 for _ in range(100)]

for i in range(n-2):
    if len(firsts) == 10:
        break
    first =  s[i]
    if first in firsts:
        continue
    firsts.append(first)
    for j in range(i+1,n-1):
        if len(firsts_seconds[int(first)]) == 10:
            break
        second = s[j]
        first_second = first + second
        if first_second in firsts_seconds[int(first)]:
            continue
        firsts_seconds[int(first)].append(first_second)
        for k in range(j+1, n):
            password = first_second + s[k]
            if password not in firsts_seconds_thirds[int(first_second)]:
                firsts_seconds_thirds[int(first_second)].append(password)
                passwords.append(password)

print(len(passwords))
### BUGGY CODE ###

import sys
import bisect
import math
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from operator import itemgetter

def calc(n,p,q,r,s,t,u):
    dp=[-1]*(n+1)
    for i in range(n+1):
        dp[i]=i
    dp[0]=0
    for i in range(1,n+1):
        if i>=p and dp[i-p]>=0:
            if dp[i]<dp[i-p]+s:
                dp[i]=dp[i-p]+s
        if i>=q and dp[i-q]>=0:
            if dp[i]<dp[i-q]+t:
                dp[i]=dp[i-q]+t
        if i>=r and dp[i-r]>=0:
            if dp[i]<dp[i-r]+u:
                dp[i]=dp[i-r]+u
    
    return max(dp)

n=int(input())
p,q,r=map(int,readline().split())
s,t,u=map(int,readline().split())

res=calc(n,p,q,r,s,t,u)
ans=calc(res,s,t,u,p,q,r)
print(ans)

### FIXED CODE ###

import sys
import bisect
import math
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from operator import itemgetter

def calc(n,p,q,r,s,t,u):
    dp=[-1]*(n+1)
    for i in range(n+1):
        dp[i]=i
    dp[0]=0
    for i in range(1,n+1):
        if i>=p and dp[i-p]>=0:
            if dp[i]<dp[i-p]+s:
                dp[i]=dp[i-p]+s
        if i>=q and dp[i-q]>=0:
            if dp[i]<dp[i-q]+t:
                dp[i]=dp[i-q]+t
        if i>=r and dp[i-r]>=0:
            if dp[i]<dp[i-r]+u:
                dp[i]=dp[i-r]+u
    
    return max(dp)

n=int(input())
p,q,r=map(int,readline().split())
s,t,u=map(int,readline().split())

res=calc(n,p,q,r,s,t,u)
ans=calc(res,s,t,u,p,q,r)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.buffer.readline().rstrip()
def resolve():
    n,q=map(int,input().split())
    S,T,X=[0]*n,[0]*n,[0]*n
    D=[0]*q
    for i in range(n):
        S[i],T[i],X[i]=map(int,input().split())
    for j in range(q):
        D[j]=int(input())

    E=[]
    E+=[(s-x,1,x) for s,x in zip(S,X)]
    E+=[(t-x,2,x) for t,x in zip(T,X)]
    E+=[(d,3,i) for i,d in enumerate(D)]
    E.sort()
    cnt={x:0 for x in X}
    cnt[INF]=1

    from heapq import heappop,heappush
    Q=[INF]
    ans=[-1]*q
    for a,b,c in E:
        if(b==1):
            heappush(Q,c)
            cnt[c]+=1
        elif(b==2): # 本来はここでqからcを削除したいが、できないためb==3で処理する
            cnt[c]-=1
        else:
            while(cnt[Q[0]]==0): # 本来削除されるべき通行止めをここで消す
                heappop(Q)
            x=Q[0]
            if(x!=INF): ans[c]=x
    print(*ans,sep="\n")
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.buffer.readline().rstrip()
read = sys.stdin.buffer.read
def resolve():
    n,q=map(int,input().split())
    data = list(map(int,read().split()))
    S = data[:3*n:3]
    T = data[1:3*n:3]
    X = data[2:3*n:3]
    D = data[3*n:]

    E=[]
    E+=[(s-x,1,x) for s,x in zip(S,X)]
    E+=[(t-x,2,x) for t,x in zip(T,X)]
    E+=[(d,3,i) for i,d in enumerate(D)]
    E.sort()
    from collections import defaultdict
    cnt=defaultdict(int)
    cnt[INF]=1

    from heapq import heappop,heappush
    Q=[INF]
    ans=[None]*q
    for a,b,c in E:
        if(b==1):
            heappush(Q,c)
            cnt[c]+=1
        elif(b==2): # 本来はここでqからcを削除したいが、できないためb==3で処理する
            cnt[c]-=1
        else:
            while(cnt[Q[0]]==0): # 本来削除されるべき通行止めをここで消す
                heappop(Q)
            x=Q[0]
            ans[c]=x if(x!=INF) else -1
    print(*ans,sep="\n")
resolve()
### BUGGY CODE ###

s = input()
q = int(input())
arr = [list(map(str, input().split())) for _ in range(q)]
ans = s
for i in range(q):
    if arr[i][0] == '1':
        ans = ans[::-1]
    else:
        if arr[i][1] == '1':
            ans = arr[i][2] + ans
        else:
            ans += arr[i][2]
print(ans)


### FIXED CODE ###

from collections import deque


s = list(input())
q = int(input())
ans = deque(s)
cnt = 0
for i in range(q):
    arr = list(map(str, input().split()))
    if arr[0] == '1':
        cnt += 1
        cnt %= 2
    else:
        if (arr[1] == '1' and cnt == 0) or (arr[1] == '2' and cnt == 1):
            ans.appendleft(arr[2])
        else:
            ans.append(arr[2])
if cnt == 0:
    print(*ans, sep='')
else:
    ans.reverse()
    print(*ans, sep='')
### BUGGY CODE ###

from collections import Counter
import math
import random
n=int(input())
a=list(map(int,input().split()))
ma=max(a)
sa=set(a)
ans=[]
era=[1]*(10**6+1)
era[0]=0
ca=Counter(a)

k=2
while k<(10**6+1):
  if era[k]==1:
    for i in range(k,10**6+1,k):
      if i!=k:
        era[i]=0
      if i in sa:
        for t in range(ca[i]):
          ans.append(k)
  if k==2:
    k+=1
  else:
    k+=2

pflag=True
if len(ans)!=len(set(ans)):
  pflag=False
  
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')


### FIXED CODE ###

import math
n=int(input())
a=list(map(int,input().split()))
pflag=True
def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a
sosu=[1]*(10**6+1)
sosu[0]=0

k=2
while k<(10**6+1)**0.5+1:
  for i in range(2*k,10**6+1,k):
    sosu[i]=0
  if k==2:
    k+=1
  else:
    k+=2
gu=0
import copy
ans=copy.deepcopy(sosu)

for i in range(n):
  if gu>1:
    pflag=False
  if ans[a[i]]==0:
    ai = set(prime_factorize(a[i]))
    for j in ai:
      if ans[j]==0:
        pflag=False
        break
      else:
        ans[j]=0
  else:
    ans[a[i]]=0
  if a[i]%2==0:
    gu+=1
  ans[a[i]]=0
    
if pflag == False:
  setwise=a[0]
  for i in range(1,n):
    setwise=math.gcd(setwise,a[i])
  if setwise == 1:
    print("setwise coprime")
  else:
    print("not coprime")
else:
  print('pairwise coprime')
### BUGGY CODE ###

n = int(input())
l = []
 
for _ in range(n):
    a = int(input())
    l.append(a)

tmp = set(l)
tmp = list(tmp)
ans = []

for i in range(len(tmp)):
    b = l.count(tmp[i])
    if b%2 != 0:
        ans.append(tmp[i])


print(len(ans))

### FIXED CODE ###

n = int(input())
l = []
 
for _ in range(n):
    a = int(input())
    l.append(a)

l.sort()

ans = 0
cnt = 1
tmp = l[0]
for i in range(1,len(l)):
    if tmp == l[i]:
        cnt += 1
        tmp = l[i]
    else:
        if cnt%2 != 0:
            ans += 1
            cnt = 1
            tmp = l[i]
        else:
            cnt = 1
            tmp = l[i]
if cnt%2 != 0:
    ans += 1

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

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

### FIXED CODE ###

n = int(input())
a = [int(s) for s in input().split()]
b = []
val = 0
sum_val= 0
for i in range(0, n):
    b.append(a[i] * sum_val) 
    sum_val+= a[i] 
val = sum(b)
print(val % (10 ** 9 + 7))
### BUGGY CODE ###

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

current = []
for i in range(n):
    current.append(lst[i].pop(0))

count = 0
while True:
    index_lst = []
    for i in range(len(current)):
        candidate = current[i]
        if candidate == 0:
            continue
        if current[candidate-1] == i+1:
            index_lst += [i+1, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in set(index_lst):
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].pop(0)
    count += 1

### FIXED CODE ###

from collections import deque
 
n = int(input())
lst = [deque(map(int, input().split())) for _ in range(n)]
 
current = []
for i in range(n):
    current.append(lst[i].popleft())

count = 0
players = set(range(1, n+1))
while True:
    index_lst = []
    for i in players:
        candidate = current[i-1]
        if candidate in index_lst:
            continue
        if current[candidate-1] == i:
            index_lst += [i, candidate]   
    if len(index_lst) == 0:
        if sum(current) == 0:
            print(count)
            break
        else:
            print(-1)
            break
    for i in index_lst:
        if len(lst[i-1]) == 0:
            current[i-1] = 0
        else:
            current[i-1] = lst[i-1].popleft()
    players = set(index_lst)
    count += 1
### BUGGY CODE ###

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

#iを篩にかけた数をmemo
def sieve_table(n):
    table = [0] * (n+1)
    for i in range(2, n+1):
        if table[i] > 0:
            continue

        table[i] = i
        for j in range(2 * i, n+1, i):
            table[j] = i
    return table

#tableから素因数分解
def factorization_from_table(x, table):
    res = set()
    while x > 1:
        res.add(table[x])
        x //= table[x]
    
    return res

table = sieve_table(10 ** 6)
set_primes = set()

flg = True
for i in range(n):
    res = factorization_from_table(a[i], table)
    if len(set_primes & res) > 0:
        flg = False
        break
    
    set_primes = set_primes | res

if flg:
    print('pairwise coprime')
else:
    from math import gcd
    tmp = a[0]
    for i in range(1, n):
        tmp = gcd(tmp, a[i])
    
    if tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')

### FIXED CODE ###

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

#iを篩にかけた数をmemo
def sieve_table(n):
    table = [0] * (n+1)
    for i in range(2, n+1):
        if table[i] > 0:
            continue

        table[i] = i
        for j in range(2 * i, n+1, i):
            table[j] = i
    return table

#tableから素因数分解
def factorization_from_table(x, table):
    res = set()
    while x > 1:
        res.add(table[x])
        x //= table[x]
    
    return res

table = sieve_table(10 ** 6)
set_primes = set()

flg = True
for i in range(n):
    res = factorization_from_table(a[i], table)
    if len(set_primes & res) > 0:
        flg = False
        break
    
    for x in res:
        set_primes.add(x)
        
if flg:
    print('pairwise coprime')
else:
    from math import gcd
    tmp = a[0]
    for i in range(1, n):
        tmp = gcd(tmp, a[i])
    
    if tmp == 1:
        print('setwise coprime')
    else:
        print('not coprime')
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split())) 
ans = 0
cnt = 1

for i in range(n-1):
    tmp = a[i] + a[i+1]
    for j in range(i+2,n):
        tmp = tmp - a[j-1] + a[j]
        #print(cnt,tmp)
        cnt += 1
        if cnt == tmp:
            ans += 1
    cnt = 1

print(ans)

### FIXED CODE ###

import collections
n=int(input())
a=list(map(int, input().split())) 
ans = 0
ru = []

for i in range(n):
    ru.append(int(i + 1 + a[i]))

c = collections.Counter(ru)
#print(c)

for i in range(n):
    tmp = i + 1 - a[i]
    ans += c[tmp]

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

from collections import deque

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

INF = -1
n_i = [-1, 0, 1, 0]
n_j = [0, -1, 0, 1]
dist_map = [[INF]*W for _ in range(H)]

# 黒マスの位置を記録
q = deque()
for i in range(H):
    a = input()
    for j in range(W):
        if a[j] == "#":
            q.append([i, j, 0])
            dist_map[i][j] = 0

max_dist = 0

while len(q) > 0:
    current_h, current_w, dist = q.popleft()
    if max_dist < dist:
        max_dist = dist
    dist_map[current_h][current_w] = dist
    for dir in range(4):
        nh = current_h + n_i[dir]
        nw = current_w + n_j[dir]
        if nh < 0 or H <= nh or nw < 0 or W <= nw:
            continue
        if dist_map[nh][nw] != INF:
            continue
        q.append((nh, nw, dist+1))


print(max_dist)


### FIXED CODE ###

from collections import deque
h,w = list(map(int,input().split()))
f = []
q = deque()
for i in range(h):
    a = list(input())
    for j in range(w):
        if a[j] == '#':
            q.append([0,i,j])
    f.append(a)
 
ans =0
dxy = [0,1,0,-1,0]
while(len(q)):
    c,y,x = q.popleft()
    for i in range(4):
        ny = y+dxy[i]
        nx = x+dxy[i+1]
        if nx >= w or ny >= h or nx <0 or ny <0:
            continue
        if f[ny][nx] == '.':
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
        elif f[ny][nx] != '#' and f[ny][nx] > c+1:
            f[ny][nx] = c+1
            q.append([c+1,ny,nx])
            ans = max(ans,c+1)
 
print(ans)
### BUGGY CODE ###

def calc_cost2(h, k):
    n = len(h)
    if (n == 0):
        return 0

    cost = n * [None]
    cost[0] = 0
    for i in range(1, len(h)):
        tmp = cost[i-1] + abs(h[i] - h[i-1])
        for s in range(max(0, i-k), i):
            tmp = min(tmp, cost[s] + abs(h[i] - h[s]))

        cost[i] = tmp

    return cost[n-1]

if __name__ == "__main__":
    n, k = list(map(int, input().split(" ")))
    h = list(map(int, input().split(" ")))
    res = calc_cost2(h, k)
    print(res)

### FIXED CODE ###

def calc_cost2(h, k):
    n = len(h)
    if (n == 0):
        return 0

    cost = n * [None]
    cost[0] = 0
    for i in range(1, len(h)):
        cost[i] = min([cost[s] + abs(h[i] - h[s]) for s in range(max(0, i-k), i)])
        #cost[i] = min(map(lambda s: cost[s] + abs(h[i] - h[s]), range(max(0, i-k), i)))

    return cost[n-1]


if __name__ == "__main__":
    n, k = list(map(int, input().split(" ")))
    h = list(map(int, input().split(" ")))
    res = calc_cost2(h, k)
    print(res)
### BUGGY CODE ###

# Linear Approximation
from statistics import median
n = int(input())
a = sorted((lambda x: [list(map(int, x.split()))[i] - i - 1 for i in range(n)])(input()))
print(int(sum([abs(i - median(a)) for i in a])))


### FIXED CODE ###

# Linear Approximation
from statistics import median
n = int(input())
a = list(map(int, input().split()))
b = []
_sum = 0
for i in range(n):
    b.append(a[i] - i - 1)
med = median(b)
for i in range(n):
    _sum += abs(b[i] - med)
print(int(_sum))
### BUGGY CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
species = list(set(A))
dic = {}
for i in species:
    dic[i] = 0
for i in A:
    dic[i] += 1
if K >= len(species):
    print(0)
else:
    ans = 0
    while len(dic) > K:
        ans += min(dic.values())
        dic.pop(min(dic, key=dic.get))
    print(ans)

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
species = list(set(A))
dic = {}
for i in species:
    dic[i] = 0
for i in A:
    dic[i] += 1
if K >= len(species):
    print(0)
else:
    tmp = sorted(dic.values(),reverse=1)
    print(sum(tmp[K:]))
### BUGGY CODE ###

n, q = map(int, input().split())
s = list(input())

l = []

num_list = []
for i in range(len(s)-1):
    if s[i] == 'A' and s[i+1] == 'C':
        num_list.append(i)

for i in range(q):
    array = list(map(int, input().split()))
    l.append(array)

for i in range(q):
    count = 0
    for j in num_list:
        if l[i][0]-1 <= j < l[i][1]-1:
            count += 1
    print(count)

### FIXED CODE ###

n, q = map(int, input().split())
s = list(input())

l = [0]
ll = []
count = 0

for i in range(n-1):
    if s[i] == 'A' and s[i+1] == 'C':
        count += 1
    l.append(count)


for i in range(q):
    array = list(map(int, input().split()))
    ll.append(array)

for i in range(q):
    print(l[ll[i][1]-1] - l[ll[i][0]-1])