Harryxun/stf_run huggingface dataset:
n,m,X,Y=sorted(map(int,input().split()))
x=max([X],max(map(int,input().split())))
y=min([Y],min(map(int,input().split())))
print("No War" if x<y else "War")

### FIXED CODE ###

n,m,X,Y=map(int,input().split())
x=max(X,max(map(int,input().split())))
y=min(Y,min(map(int,input().split())))
print(["War","No War"][x<y])
import sys
sys.setrecursionlimit(2000000)
t=input()
tl=list(t)
x=t.find("?")
while x != -1:
    if tl[x+1]=="D":
        tl[x]="P"
    elif tl[x+1]=="?":
        tl[x]="P"
    else:
        tl[x]="D"
    t="".join(tl)
    x=t.find("?")
print(t)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
t=input()
tl=list(t)
tln=len(t)
x=0
for x in range(tln):
    if tl[x] == "?":
        if x == tln-1:
            tl[x]="D"
            break
        elif x==0:
            if tl[x+1]=="?":
                tl[x]="P"
                tl[x+1]="D"
            else:
                tl[x]="D"
        elif tl[x-1]=="P":
            tl[x]="D"
        elif tl[x+1]=="?":
            tl[x]="P"
            tl[x+1]="D"
        elif tl[x+1]=="D":
            tl[x]="P"
        else:
            tl[x]="D"
t="".join(tl)
print(t)
s = input()
s_set = list(set(s))    #重複削除

s_set.sort()

chk = list("abcdefghijklmnopqrstuvwxyz")

i = 0

while 1:
    if s_set[i] != chk[i]:
        print(chk[i])
        break
    i +=1
    if i >= 26:
        print("None")
        break
    
    

### FIXED CODE ###

s = input()
s_set = list(set(s))    #重複削除

s_set.sort()

chk = list("abcdefghijklmnopqrstuvwxyz")

i = 0

while 1:
    if s_set[i] != chk[i]:
        print(chk[i])
        break
    i += 1
    
    if i >= (len(s_set)):
        print(chk[i])
        break
    if i >= 25:
        print("None")
        break
N = int(input())
S = N % 10
if(S == 0||1||6||8):
  print('pon')
else if(S == 3):
  print('bon')
else:
  print('hon')

### FIXED CODE ###

N = int(input())
S = N % 10
if(S == 0):
  print("pon")
elif(S == 1):
  print("pon")
elif(S == 6):
  print("pon")
elif(S == 8):
  print("pon")
elif(S == 3):
  print("bon")
else:
  print("hon")
import math


def C(k, n, mod):
    return math.factorial(n) // math.factorial(n - k) // math.factorial(k) % mod


n, k = map(int, input().split())
mod = int(1e9) + 7
s = 0
for i in range(1, k + 1):
    print(C(i - 1, k - 1, mod) * C(i, n - k + 1, mod))


### FIXED CODE ###

import math


def C(k, n, mod):
    return math.factorial(n) // math.factorial(n - k) // math.factorial(k) % mod


n, k = map(int, input().split())
mod = int(1e9) + 7
s = 0
for i in range(1, k + 1):
    if n + 1 - k - i >= 0:
        print((C(i - 1, k - 1, mod) * C(i, n - k + 1, mod)) % mod)
    else:
        print(0)
def eratosthenes_2017like(x): #エラトステネスからちょっと変更
    prime = []
    if x < 3:
        return prime
    search = [i for i in range(2,x+1)]
    while search[0] <= math.sqrt(x):
        add = search.pop(0)
        prime.append(add)
        multiple = 1
        while add*multiple <= x:
            multiple += 1
            if add*multiple in search:
                search.remove(add*multiple)
    prime.extend(search)

    for p in prime[::-1]:
        if not((p+1)/2 in prime):
            prime.remove(p)
    return prime

for i in range(q):
    l, r = map(int,input().split())
    left_len = len(eratosthenes_2017like(l-1))
    right_len = len(eratosthenes_2017like(r))
    print(right_len - left_len)

### FIXED CODE ###

sieve = [True] * 100001
#one-based-index
def mark(sieve,x):
    for i in range(x+x,len(sieve),x):
        sieve[i] = False

for x in range(2,int(len(sieve) ** 0.5) + 1):
    if sieve[x]: mark(sieve,x)

sieve[0] = False
sieve[1] = False

for i in range(len(sieve)-2,2,-2):
    if sieve[i]:
        if not(sieve[(i+1)//2]):
            sieve[i] = False #2017likeでない

sieve[2] = False

cnt = [0] * 100002
for i,s in enumerate(sieve):
    if s:
        cnt[i] = cnt[i-1] + 1
    else:
        cnt[i] = cnt[i-1]

q = int(input())

for i in range(q):
    l, r = map(int,input().split())
    print(cnt[r] - cnt[l-1])
import math
from functools import reduce

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


def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


lcm_num = lcm_list(a) - 1
ans = 0
for i in range(N):
    ans += lcm_num % a[i]
print(ans)


### FIXED CODE ###

from functools import reduce


def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


def lcm_base(x, y):
    return (x * y) // gcd(x, y)


def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)


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

lcm_num = lcm_list(a) - 1
ans = 0
for i in range(N):
    ans += lcm_num % a[i]
print(ans)
n,m=map(int,input().split())

def conbi(arg1, arg2):
    k=1
    l=1
    for i in range(arg2):
        k=k*(arg1-i)
        l=l*(i+1)
    if arg1==0:
        k=1
    return k/l
        
for i in range(1,m+1):
    print(int(conbi(n-m+1,i)*conbi(m-1,i-1))%(1000000007))

### FIXED CODE ###

s=input()
st=[]
d=[]
for i in s:
    if i in d:
        st[d.index(i)]+=1
    else:
        d.append(i)
        st.append(1)

if len(st)==2 & st[0]==2 & st[1]==2:
    print('Yes')
else:
    print('No')
S=input()
S[3]=8
print(S)

### FIXED CODE ###

S=list(input())
S[3]='8'
print("".join(S))
import numpy as np
Sa = input()
Sb = input()
Sc = input()

def string2int(in_list):
  out_list = np.array(in_list, dtype='S')
  out_list[out_list=='a'] = 0
  out_list[out_list=='b'] = 1
  out_list[out_list=='c'] = 2
  return np.array(out_list, dtype=int)
Sa = string2int(list(Sa))
Sb = string2int(list(Sb))
Sc = string2int(list(Sc))
ALL = [list(Sa), list(Sb), list(Sc)]

current = 0
pre = 0
while True:
  left = len(ALL[current])
  if left == 0:
    break
  current = ALL[current][0]
  ALL[pre] = ALL[pre][1:]
  pre = current

cor = ['A','B','C']
print( cor[current] )

### FIXED CODE ###

import numpy as np
Sa = input()
Sb = input()
Sc = input()

def string2int(in_list):
    out_list = np.array(in_list, dtype='S')
    out_list[out_list==b'a'] = 0
    out_list[out_list==b'b'] = 1
    out_list[out_list==b'c'] = 2
    return np.array(out_list, dtype=int)
Sa = string2int(list(Sa))
Sb = string2int(list(Sb))
Sc = string2int(list(Sc))
ALL = [list(Sa), list(Sb), list(Sc)]

current = 0
pre = 0
while True:
    left = len(ALL[current])
    if left == 0:
        break
    current = ALL[current][0]
    ALL[pre] = ALL[pre][1:]
    pre = current

cor = ['A','B','C']
print( cor[current] )
import sys 
[print(d) for i, d in enumerate([i for i in sys.stdin].reverse()) if i < 3]

### FIXED CODE ###

[print(i) for i in sorted([int(input()) for _ in range(10)], reverse=True)[0:3]]
#「県ごとの市の「市番号(id)、誕生年(year)」リスト」と「市番号順の市の認識番号(tag)リスト」を用意する

class City:
    #市番号と誕生年を管理する
    def __init__(self,id,y):
        self.id = id
        self.year = y


def main():
    n,m = map(int,input().split())
    pre_lst = [[] for _ in range(n)]  #各県に含まれる市のリスト
    city_tags = [0 for _ in range(m)] #上記のリストから作った市の認識番号を格納するためのリスト

    for i in range(m):
        p,y = map(int,input().split())
        pre_lst[p-1].append(City(i,y))　#入力を受け取り、県ごとのリストを作る

    for pre_num,pre in enumerate(pre_lst):
        if len(pre) <= 0:
            continue
        pre.sort(key = lambda x:x.year) #各県ごとに誕生年順にソート

        counter = 0 #認識番号の右側、何番目に誕生した都市かを作るためのカウンター
        for city in pre:
            city_tags[city.id] = str(pre_num+1).zfill(6) + str(counter+1).zfill(6)
            counter += 1
    for tag in city_tags:
        print(tag)


if __name__ == '__main__':
    main()


### FIXED CODE ###

class City:
    def __init__(self,id,y):
        self.id = id
        self.year = y


def main():
    n,m = map(int,input().split())
    pre_lst = [[] for _ in range(n)]
    city_tags = [0 for _ in range(m)]

    for i in range(m):
        p,y = map(int,input().split())
        pre_lst[p-1].append(City(i,y))

    for pre_num,pre in enumerate(pre_lst):
        if len(pre) <= 0:
            continue
        pre.sort(key = lambda x:x.year)
        counter = 0
        for city in pre:
            city_tags[city.id] = str(pre_num+1).zfill(6) + str(counter+1).zfill(6)
            counter += 1
    for tag in city_tags:
        print(tag)


if __name__ == '__main__':
    main()
n = int(input())
a = list(map(int,input().split()))
b = []
cnt = 1
for num in a:
    num -= cnt
    b.append(num)
    cnt += 1
test = [int(mean(b))-1,int(mean(b)),int(mean(b))+1]
ans = []
s = 9999999999999
for i in test:
    cnt = 1
    c = []
    for num in a:
        st = 0
        st = abs(num - (i+cnt))
        c.append(st)
        cnt += 1
    ans.append(sum(c))
print(min(ans))

### FIXED CODE ###

import numpy as np

n = int(input())
a = list(map(int,input().split()))
b = []
cnt = 1
for num in a:
    num -= cnt
    b.append(num)
    cnt += 1
test = [int(np.mean(b))-1,int(np.mean(b)),int(np.mean(b))+1,int(np.median(b))]
test = list(set(test))
ans = []
s = 9999999999999
for i in test:
    cnt = 1
    c = []
    for num in a:
        st = 0
        st = abs(num - (i+cnt))
        c.append(st)
        cnt += 1
    ans.append(np.sum(c))
print(np.min(ans))
S = input()
for _ in range(S - 1):
    if S[_:_ + 2] == "AC":
        print("Yes")
        break
else:
    print("No")


### FIXED CODE ###

S = input()
for _ in range(len(S) - 1):
    if S[_:_ + 2] == "AC":
        print("Yes")
        break
else:
    print("No")
def LCS(Xs, Ys):
  Xs = raw_input()
  Ys = raw_input()
  dp = {}
  count = 0
  a = 1

  for i in range(len(Ys) + 1):
    dp[0][i + 1] = Ys[i] 
  for j in range(len(Xs) + 1):
    dp[j + 1][0] = Xs[j]

  for i in range(a, len(Ys) + 1):
    for j in range(a, len(Xs) + 1):
      if dp[j][0] == dp[i][1]:
         count = count + 1
         a = j
         break
    if dp[j][0] == dp[i][1]:
      break

   print count

### FIXED CODE ###

def solve_lcs():
    x = raw_input()
    y = raw_input()
 
    a = len(x)
    b = len(y)
    c1 = [0 for i in range(b+1)]
    for i in range(a):
        e1 = x[i]
        c2 = c1+[]
        for j in range(b):
            if e1 == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
 
n = input()
for i2 in range(n):
    print solve_lcs()
a,b=map(int,input().split())
c=[]
for i in range(a):
	c.append(int(input()))
c=sorted(c)
#print(c)
f=[]
for k in range(a-b+1):
	e=[]
	f.append(e)
	for i in range(b):
		e.append(c[i+k])
#print(f)
g=[]
for i in range(len(f)):
	g.append(max(f[i])-min(f[i]))
print(min(g))


### FIXED CODE ###

a=int(input())
if a==25:
	print("Christmas")
elif a==24:
	print("Christmas Eve")
elif a==23:
	print("Christmas Eve Eve")
else:
	print("Christmas Eve Eve Eve")
N=int(input())
h = list(map(int , input().split()))
dp = [10**9+1]*N
dp[0] = 0
dp[1] = abs(h[0]-h[1])
for i in range(2,N):
    for j in range(1, i-1):
        dp[i] = min(dp[i-j]+abs(h[i]-h[i-j]), dp[]+abs(h[i]-h[i-j]))
print(dp[N-1])

### FIXED CODE ###

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

dp = [1e9]*N
dp[0] = 0
for i, b in enumerate(H):
  if i != 0:
    x = max(0, i-K)
    dp[i] = min([abs(b-d)+p for d, p in zip(H[x:i], dp[x:i])])
print(dp[-1])
A = list(map(int, input().split()))
icount = 0
if A[2] - A[1] >= A[0]:
  print('OK')
  icount = icount + 1
else:
  for i in range(A[1]:A[2]+1):
    if i % A[0] == 0:
      print('OK')
      icount = icount + 1
      if icount == 1:
        break
      
if icount == 0:
  print('NG')
    


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))  # 入力のときに N を使う必要はありません
icount = 0
if A[1] - A[0] >= N:
  print('OK')
  icount = icount + 1
else:
  for i in range(A[0], A[1]+1):
    if i % N == 0:
      print('OK')
      icount = icount + 1
      if icount == 1:
        break
      
if icount == 0:
  print('NG')
values = [int(input()) for i in range(int(input()))]
maxv = - 1000000
minv = values[0]

for val in enumerate(values):
    maxv = max(maxv, (val - minv))
print(maxv)


### FIXED CODE ###

values = [int(input()) for _ in range(int(input()))]
maxv = values[1] - values[0]
minv = values[0]

for val in values[1:]:
    maxv = max(maxv, val - minv)
    minv = min(minv, val)         # 今までの最小値を保持(自分と自分を比較しない様に、最大値の評価後に計算)
print(maxv)
import math
n,k=map(int,input().split())
a=list(map(int,input().split()))
a.sort(revese=True)
for i in range(k):
  t=max(a)
  a.insert(0,t/2)
  a.remove(t)
print(math.ceil(max(a)))

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
l,r=0,max(a)
def test(x):
  num=0
  for i in a:
    num+=i//x
    if i%x==0:
      num-=1
  if num<=k:
    return num
while r-l>1:
  mid=(l+r)//2
  if test(mid):
    r=mid
  else:
    l=mid
print(r)
import math
a,b,c,d=map(int,input().split())
cd=int(c*d/(math.gcd(c,d)))
#print(cd)
c1=b//c
c2=(a-1)//c
c3=c1-c2
d1=b//d
d2=(a-1)//d
d3=d1-d2
cd1=b//(cd)
cd2=(a-1)//(cd)
cd3=cd1-cd2
print((b-a+1)-(c3+d3-cd3))
#print(str(c3)+" "+str(d3)+" "+str(cd3))

### FIXED CODE ###

import fractions
a,b,c,d=map(int,input().split())
cd=int(c*d/(fractions.gcd(c,d)))
#print(cd)
c1=b//c
c2=(a-1)//c
c3=c1-c2
d1=b//d
d2=(a-1)//d
d3=d1-d2
cd1=b//(cd)
cd2=(a-1)//(cd)
cd3=cd1-cd2
print((b-a+1)-(c3+d3-cd3))
#print(str(c3)+" "+str(d3)+" "+str(cd3))
N =int(input())
Nans = N
ans = ""

while True:
    if N <= 26:
        matsubi = chr(96+N)
        ans += matsubi
        break
    else:
        if N % 26==0:
            matsubi = "z"
        else:
            a = int(N%26)
            matsubi = chr(96+a)
        ans += matsubi
        if N>26:
            N /= 26
    # if N<26:
    #     last = chr(96+N)
    #     ans += last
    #     break


ans2 = ans[::-1]
print(ans2)


### FIXED CODE ###

N =int(input())
ans = ""

while True:
  N-=1
  matsubi = N%26
  matsubi = chr(96+matsubi+1)
  ans += matsubi

  if N//26 == 0:
      break
  else:
      N//=26

ans = ans[::-1]
print(ans)
N = int(input())
A = list(map(int, input().split()))
cnt = [0 for _ in range(N)]
for i in range(N):
    cnt[A[i]-1] += 1
S = 0
for i in range(N):
    S += cnt[i]*(cnt[i]-1)/2
for i in range(N):
    if cnt[A[i]] == 1:
        print(S)
    else:
        print(int(S+(3-2*cnt[A[i]-1])/2))


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
cnt = [0 for _ in range(N)]
for i in range(N):
    cnt[A[i]-1] += 1
S = 0
for i in range(N):
    S += cnt[i]*(cnt[i]-1)/2
for i in range(N):
    if cnt[A[i]-1] == 1:
        print(int(S))
    else:
        print(int(S+(3-2*cnt[A[i]-1])/2))
n = int(input())
listA = [int(input()) for i in range(n)]
a = listA[0]
b = 0
for j in range(n):
  if a != 2:
    a = listA[a]
    b = b+1
  elif a == 2:
    b = b+1
    break
if b == n:
  print(-1)
else:
  print(b)

  

### FIXED CODE ###

n = int(input())
listA = [int(input()) for i in range(n)]
a = listA[0]
b = 0
for j in range(n):
  if a != 2:
    a = listA[a-1]
    b = b+1
  elif a == 2:
    b = b+1
    break
if b == n:
  print(-1)
else:
  print(b)
import math

A, B, C, D = map(int, input().split())
ans=0

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

lcmCD=lcm(C, D)
ans=B-A+1
ans-=((B//C) - (A//C))
ans-=((B//D) - (A//D))
ans+=((B//lcmCD) - (A//lcmCD))
print(ans)


### FIXED CODE ###

A, B, C, D = map(int, input().split())
ans=0

def gcd(m, n):
    x=max(m, n)
    y=min(m, n)
    if x%y == 0:
        return y
    else:
        while x%y!=0:
            z=x%y
            x=y
            y=z
        else:
            return z

def lcm(x, y):
    return (x * y) // gcd(x, y)

lcmCD=lcm(C, D)
ans=B-A+1
ans-=((B//C) - ((A-1)//C))
ans-=((B//D) - ((A-1)//D))
ans+=((B//lcmCD) - ((A-1)//lcmCD))
print(ans)
n=len(s)
set=set(s)
m=len(set)
a=s.count('a')
b=s.count('b')
c=s.count('c')
if m==1:
  if n==1:
    print('YES')
  else:
    print('NO')
elif m==2:
  if c==0:
    if a==b:
      print('YES')
    else:
      print('NO')
  elif b==0:
    if a==c:
      print('YES')
    else:
      print('NO')
  else:
    if b==c:
      print('YES')
    else:
      print('NO')
else:
  d=n//m
  res=0
  if a<=d:
    res+=1
  if b<=d:
    res+=1
  if c<=d:
    res+=1
  if res<=1:
    print('YES')
  else:
    print('NO')

### FIXED CODE ###

s=input()
n=len(s)
set=set(s)
m=len(set)
a=s.count('a')
b=s.count('b')
c=s.count('c')
if m==1:
  if n==1:
    print('YES')
  else:
    print('NO')
elif m==2:
  if n==2:
    print('YES')
  else:
    print('NO')
else:
  if n%3==0:
    if a==b==c:
      print('YES')
    else:
      print('NO')
  elif n%3==2:
    if (a==n//3+1 and b==n//3+1) or (c==n//3+1 and b==n//3+1) or (a==n//3+1 and c==n//3+1):
      print('YES')
    else:
      print('NO')
  else:
    if (a==n//3 and b==n//3) or (c==n//3 and b==n//3) or (a==n//3 and c==n//3):
      print('YES')
    else:
      print('NO')
n, k, q = map(int, input().split(" "))
liste = [k-q for i in range(n)]
for i in range(q):
    a = int(input())
    liste[a-1] += 1
for i in liste:
    if i > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

s = input()
if s == 'Sunny':
    print('Cloudy')
elif s == 'Cloudy':
    print('Rainy')
elif s == 'Rainy':
    print('Sunny')
def gcd(a, b):
  if a < b:
    a, b = b, a
  while a % b:
    a, b = b, a % b
  return b

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

k = int(input())
total = 0
for a in range(1, k+1):
  for b in range(1, k+1):
    for c in range(1, k+1):
      total += gcd(a, b, c)
print(total)

### FIXED CODE ###

def gcd(a, b):
  if a < b:
    a, b = b, a
  while a % b:
    a, b = b, a % b
  return b

k = int(input())
total = 0
for a in range(1, k+1):
  for b in range(a, k+1):
    for c in range(b, k+1):
      if a == b == c:
        total += gcd(gcd(a, b), c)
      elif a == b or b == c:
        total += 3*gcd(gcd(a, b), c)
      else:
        total += 6*gcd(gcd(a, b), c)
print(total)
N, M = map(int, input().split(' '))
AB = [[] for _ in range(N + 10)]
ans = 0
for _ in range(N):
  a, b = map(int, input().split())
  AB[a].append(b)
import heapq
reward = []
heapq.heapify(reward)
for i in range(1, M + 1):
  for item in AB[i]:
    heapq.heappush(reward, -item)
  if reward:
    ans -= heapq.heappop(reward)
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
AB = [[] for _ in range(M + 10)]
ans = 0
for _ in range(N):
  a, b = map(int, input().split())
  if a > M:
    continue
  AB[a].append(b)
import heapq
reward = []
heapq.heapify(reward)
for i in range(1, M + 1):
  for item in AB[i]:
    heapq.heappush(reward, -item)
  if reward:
    ans -= heapq.heappop(reward)
print(ans)
N = input()
lst_A = [1/int(input()) for i in range(N)]

print(1/sum(lst_A))

### FIXED CODE ###

n = input()
lst_A = map(int, input().split())
lst_A_inv = [1/x for x in lst_A]
print(1/sum(lst_A_inv))
N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

values = [0] * (N+1)
for p,x in PX:
    values[p] += x
def dfs(v,parent,add):
    values[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,values[v])
        
dfs(1,0,0)
answer = ' '.join(map(str,values[1:]))
print(answer)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

# 遅延評価で加えてあげるだけ

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)
n = int(input())
y = int(input())

x = -1
y = -1
z = -1

for i in range(n):
  for t in range(i, n):
    sum = 10000 * i + 5000 * (t - i)  + 1000 * (n - t)
    if sum == y:
      x = i
      y = t - i
      z = n - t
      
print(x, y, z)

### FIXED CODE ###

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

a = -1
b = -1
c = -1

for i in range(n + 1):
  for t in range(i, n + 1):
    sum = 10000 * i + 5000 * (t - i)  + 1000 * (n - t)
    if sum == y:
      a = i
      b = t - i
      c = n - t
      
print(a, b, c)
def main():
    W , H , x, y, r = [int(i) for i in input().split()]


    if (x-r>= 0, x+r <= w , y-r >=0, y+r <= H) 
        print("Yes")
    else
        print("No")

    if __name__ == '__main__' :
        main()
    

### FIXED CODE ###

def main() :
    W, H, x, y, r = [int(i) for i in input().split()]

    if ((x-r)>=0) and ((x+r)<=W) and ((y-r)>=0) and ((y+r)<=H) :
        print("Yes")
    else :
        print("No")

if __name__ == '__main__' :
    main()
N = int(input())
pt, px, py = 0, 0, 0

for i in range (N):
    t, x, y = map(int, input().split())
    dt = t - pt
    dxy = x-px+y-py
    if dxy > dt or (dxy - dt)%2:
        print("No")
        exit()
    pt, px, py = t, x, y
print("Yes")

### FIXED CODE ###

a, b = map(int, input().split())
if a*b%2 == 0:
    print("Even")
else:
    print("Odd")
import bisect
N, K, *A = [int(_) for _ in open(0).read().split()]
K -= 1
L = [[] for _ in range(10)]
for i, a in enumerate(A * 2):
    L[a] += [i]
exit()
before_next = [L[a][bisect.bisect(L[a], i)] for i, a in enumerate(A)]
first_cycle = [None] * N
now = 0
idx = 0
cycle = 0
while True:
    if first_cycle[now] is not None:
        break
    first_cycle[now] = cycle
    now = before_next[now] + 1
    dcycle, now = divmod(now, N)
    cycle += dcycle
cycle2 = cycle
cycle1 = first_cycle[now]
#K cycle目=cycle1+(K-cycle1)%(cycle2-cycle1) cycle目
K2 = cycle1 + (K - cycle1) % (cycle2 - cycle1)
if K2:
    f1 = f2 = 0
    for i in range(N - 1, -1, -1):
        if first_cycle[i] == K2 - 1:
            f1 = 1
            break
    for j in range(N - 1, -1, -1):
        if first_cycle[j] == K2:
            f2 = 1
            break
    if f2:
        B = A[j:]
    elif f1:
        B = A[i:] + A
    else:
        raise
else:
    B = A
ans = []
cnt = [0] * 10
for a in B:
    if cnt[a] > 0:
        while True:
            cnt[ans.pop()] -= 1
            if cnt[a] == 0:
                break
    else:
        ans += [a]
        cnt[a] += 1
print(' '.join(map(str, ans)))


### FIXED CODE ###

import bisect
N, K, *A = [int(_) for _ in open(0).read().split()]
K -= 1
L = [[] for _ in range(2 * 10**5 + 1)]
for i, a in enumerate(A * 2):
    L[a] += [i]
before_next = [L[a][bisect.bisect(L[a], i)] for i, a in enumerate(A)]
first_cycle = [None] * N
now = 0
idx = 0
cycle = 0
while True:
    if first_cycle[now] is not None:
        break
    first_cycle[now] = cycle
    now = before_next[now] + 1
    dcycle, now = divmod(now, N)
    cycle += dcycle
cycle2 = cycle
cycle1 = first_cycle[now]
#K cycle目=cycle1+(K-cycle1)%(cycle2-cycle1) cycle目
K2 = cycle1 + (K - cycle1) % (cycle2 - cycle1)
if K2:
    f1 = f2 = 0
    for i in range(N - 1, -1, -1):
        if first_cycle[i] == K2 - 1:
            f1 = 1
            break
    for j in range(N - 1, -1, -1):
        if first_cycle[j] == K2:
            f2 = 1
            break
    if f2:
        B = A[j:]
    elif f1:
        B = A[i:] + A
else:
    B = A
ans = []
cnt = [0] * (2 * 10**5 + 1)
for a in B:
    if cnt[a] > 0:
        while True:
            cnt[ans.pop()] -= 1
            if cnt[a] == 0:
                break
    else:
        ans += [a]
        cnt[a] += 1
print(' '.join(map(str, ans)))
# -*- coding: utf-8 -*-

def io_generator():
	return input()

#+++++++++++++++++++

def main(io):
	n,q=map(int, io().split())
	s=list(io())
	
	ss=[0 for _ in s[:-1]]
	for i, (c, cn) in enumerate(zip(s, s[1:])):
		if c=='A' and cn=='C':
			ss[i]=1
	
	ret=[]
	for i in range(q):
		r,l=map(int, io().split())
		rr=sum(ss[r-1:l])-ss[l-1]
		ret.append(str(rr))
		
	return "\n".join(ret)
	
	
#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	print (main(io))

### FIXED CODE ###

 # -*- coding: utf-8 -*-

def io_generator():
	return input()

#+++++++++++++++++++

def main(io):
	n,q=map(int, io().split())
	s=list(io())
	
	ss=[0 for _ in s]
	sss=ss.copy()
	for i, c in enumerate(s[1:],1):
		if s[i-1]=='A' and s[i]=='C':
			ss[i]=1
		sss[i] = ss[i] + sss[i-1]
	
	for i in range(q):
		r, l=map(int, io().split())
		#rr=sum(ss[r-1:l])-ss[l-1]
		rr=sss[l-1]-sss[r-1]
		#ret.append(str(rr))
		print(rr)
	
#++++++++++++++++++++

if __name__ == "__main__":
	io= lambda : io_generator()
	#print (main(io))
	main(io)