Harryxun/stf_run huggingface dataset:
inf=100000000

while(1):
    n,m,c,s,g=map(int,input().split())
    if(n==m==0): break
    for i in range(m):
        x,y,d,c0=map(int,input().split())

    unchin=list(map(int,input().split()))
    unchin.insert(0,0)
    uth=[]
    uth.append([])
    for i in range(1,c+1):
        ddis=list(map(int,input().split()))
        ddis.insert(0,0)
        dcost=list(map(int,input().split()))
        uth.append([ddis,dcost])
	
	print(-1)

### FIXED CODE ###

inf=100000000

def calc(uth,dis,c):
    fare=0
    if dis>=inf:
        return inf
    if unchin[c]==1:
        return uth[c][1][0]*dis
    ddis=uth[c][0]
    dcost=uth[c][1]
    i=1
    while(i<unchin[c] and dis>ddis[i]):
        fare+=(ddis[i]-ddis[i-1])*dcost[i-1]
        i+=1
    fare+=(dis-ddis[i-1])*dcost[i-1]
    return fare

def floyd(bigmap,n):
    res=bigmap
    for k in range(1,n+1):
        for i in range(1,n+1):
            for j in range(1,n+1):
                if res[i][j]>res[i][k]+res[k][j]:
                    res[i][j]=res[i][k]+res[k][j]
    return res

def init2d(bigmap,n):
    for i in range(n+1):
        bigmap.append([])
    for map1 in bigmap:
        for j in range(n+1):
            map1.append(inf)
    for i in range(1,n+1):
        bigmap[i][i]=0
    return bigmap

while(1):
    n,m,c,s,g=map(int,raw_input().split())
    if(n==m==0): break
    rosen=[]
    for i in range(c+1):
        map0=[]
        rosen.append(init2d(map0,n))

    for i in range(m):
        x,y,d,c0=map(int,raw_input().split())
        rosen[c0][x][y]=min(rosen[c0][x][y],d)
        rosen[c0][y][x]=min(rosen[c0][x][y],d)

    unchin=list(map(int,raw_input().split()))
    unchin.insert(0,0)
    uth=[]
    uth.append([])
    for i in range(1,c+1):
        ddis=list(map(int,raw_input().split()))
        ddis.insert(0,0)
        dcost=list(map(int,raw_input().split()))
        uth.append([ddis,dcost])

    bigmap=[]
    bigmap=init2d(bigmap,n)


    for c0,cmap in enumerate(rosen[1:]):
        tmp=floyd(cmap,n)
        for i in range(1,n+1):
            for j in range(1,n+1):
                bigmap[i][j]=min(bigmap[i][j],calc(uth,tmp[i][j],c0+1))

    bigmap=floyd(bigmap,n)

    ans=bigmap[s][g]
    if ans < inf:
        print(ans)
    else:
        print(-1)
a,b,k = map(int,input().split())
x=0
y=[0]
c=min(a,b)

if a==1 or b==1:
    print(1)
    exit()
    
for d in range(1,c):
    if a%d==0 and b%d==0:
            y.append(d)

print(y[k])
print(y)


### FIXED CODE ###

a,b,k = map(int,input().split())
x=0
y=[0]
c=min(a,b)

if a==1 or b==1:
    print(1)
    exit()
    
for d in range(1,c+1):
    if a%d==0 and b%d==0:
            y.append(d)

print(y[-k])
N, C = map(int, input().split())
timeTable = [tuple(map(int, input().split())) for i in range(N)]
sutyoku =  [{0} for i in range(20003)]

for s,t,c in timeTable:
    if s == 0:
        for i in range(2*t):
            sutyoku[i].add(c)
    else:
        for i in range(2*s-1,2*t):
            sutyoku[i].add(c)

ans = 0
for s in sutyoku:
    ans = max(ans, len(s)-1)

print(ans)



### FIXED CODE ###

import numpy

N, C = map(int, input().split())
STC = [list(map(int, input().split())) for i in range(N)]
Channel = numpy.array([[0]*(2*10**5+1) for i in range(C+1)])

for s, t, c in STC:
    Channel[c][2*s-1] += 1
    Channel[c][2*t] -= 1
    
for i in range(len(Channel)):
    Channel[i] = numpy.cumsum(Channel[i])
bool_Channel = Channel.astype(numpy.bool_)

needs = numpy.sum(bool_Channel, axis=0)
print(needs.max())
import math
from functools import reduce
def lcm_base(x, y):
    return (x * y) // math.gcd(x, y)

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)
N, M = map(int, input().split())
a = list(map(int, input().split()))
b = lcm(a)//2
ans = (M - b)//lcm(a) + 1
print(ans)

### FIXED CODE ###

import math
import fractions
n, m = map(int, input().split())
a = list(map(int, input().split()))
num = 1
cnt = []
for x in a:
    c = 0
    for i in range(int(math.log(x,2))):
        if x>>c&1:
            break
        else:
            c+=1
    cnt.append(c)
if max(cnt) != min(cnt):
    print(0)
else:
    for x in a:
        num = num * (x//2) // fractions.gcd(num, x//2)
    print(m//num-(m//num)//2)
n = int(input())
s = list(input())

r = [i for i, x in enumerate(l_dup) if x == 'R']
g = [i for i, x in enumerate(l_dup) if x == 'G']
b = [i for i, x in enumerate(l_dup) if x == 'B']

c = 0

for k in r:
    for j in g:
        for i in b:
            a = list(k, j, i)
            a.sort
            if a[0] - a[1] != a[1] - a[2]:
                c += 1

print(c)

### FIXED CODE ###

n = int(input())
s = list(input())

r = s.count('R')
g = s.count('G')
b = s.count('B')

# 1つ目の条件を満たす組の数
ans = r * g * b

# 2つ目の条件を満たす組の数
c = 0
for i in range(n):
    for j in range(i+1,n):
        k = 2 * j -i
        if k > n-1:
            break
        if s[i] != s[j] and s[j] != s[k] and s[k] != s[i]:
            c += 1

print(ans - c)
import math
a=input().split("¥n")
K=int(a[1])
S_len=len(a[0])

print("K="+str(K) +" S_len="+str(S_len))

for i in range(S_len):
    # print("i="+str(i) +" n="+a[0][i])
    n=int(a[0][i])
    # print("i="+str(i) +" n="+str(n))

    # if(n==1):
    #     K-=1
    #     if(K<=0):
    #         print("1")
    #         break
    # else:

    L=int(K*math.log10(n))
    # print("K="+str(K) +" L="+str(L))
    K-=L+1
    if(K<=0):
        print(n)
        break


### FIXED CODE ###

a=input().split();print((int(a[0])-1)*(int(a[1])-1));
n=int(input())
a=[]*n
a=list(map(int,input().split()))
num=1
bre=0
no=True
def search(pos,s):
    spos=pos
    global num,bre,no
    end=True
    while end:
        if spos >= n:
            break
        if a[spos]==s:
            no=False
            bre+=spos-pos
            num+=1
            search(spos+1,num)
            end=False
        else:spos+=1
search(0, num)
if no:
    bre=-1
print(bre)

### FIXED CODE ###

import sys
sys.setrecursionlimit(2000000)

n=int(input())
a=[]*n
a=list(map(int,input().split()))
num=1
bre=0
no=True
def search(pos):
    spos=pos
    global num,bre,no
    end=True
    while end:
        if spos >= n:
            break
        if a[spos]==num:
            no=False
            num+=1
            search(spos+1)
            end=False
        else:
            spos+=1
            bre+=1

search(0)
if no:
    bre=-1
print(bre)
S = input()
K = int(input())

if len(S) <= K:
    print(S)
else
    print(S[0:K]　+ '...')

### FIXED CODE ###

N = int(input())
N = N % 10
if N in [2, 4, 5, 7, 9]:
    print('hon')

elif N in [0, 1, 6, 8]:
    print('pon')

else:
    print('bon')
N = int(input())
H = list(map(int,input().split()))
ans = []
count = 0
for i in range(N-1):
  if i == N-2:
    if H[i] >= H[i+1]:
      ans.append(count+1)
    else:
      ans.append(count)
    break
  if H[i] < H[i+1]:
    ans.append(count)
    count = 0
  else:
    count += 1
print(max(ans))

### FIXED CODE ###

N = int(input())
H = list(map(int,input().split()))
ans = [0]
count = 0
for i in range(N-1):
  if i == N-2:
    if H[i] >= H[i+1]:
      count += 1
    ans.append(count)
    break
  if H[i] < H[i+1]:
    ans.append(count)
    count = 0
  else:
    count += 1
print(max(ans))
n,l = map(int,input().split())
ss =[]
for i in range(n):
  s = input()
  ss.append(s)
ss.sort()
print(''.join(ss)

### FIXED CODE ###

n,l = map(int,input().split())
s = list(input() for i in range(n))

c = sorted(s)
ans =''.join(c)
print(ans)
from collections import *
mod=10**6+3
fac=[0 for i in range(mod-1)]
fac[0]=1
for i in range(0,len(fac)-1):
    fac[i+1]=(fac[i]*(i+1))%mod
Q=int(input())
for q in range(Q):
    x,d,n=map(int,input().split())
    D=pow(d,mod-2,mod)
    a,b=x*D%mod,(x+(n-1)*d)*D%mod
    if a>0 and a<b and b-1<mod:
        value=fac[b]*pow(fac[a-1],mod-2,mod)*pow(d,n,mod)
        print(value%mod)
    else:
        print(0)


### FIXED CODE ###

from collections import *
mod=10**6+3
fac=[0 for i in range(mod)]
fac[0]=1
for i in range(0,len(fac)-1):
    fac[i+1]=(fac[i]*(i+1))%mod
fac[0]=0
Q=int(input())
for q in range(Q):
    x,d,n=map(int,input().split())
    if d>0:
        D=pow(d,mod-2,mod)
        a=(x-d%mod)*D%mod
        b=(a+n)%mod
        if a<b and a+n<mod:
            if a>0:
                value=fac[b]*pow(fac[a],mod-2,mod)*pow(d,n,mod)
            else:
                value=fac[b]*pow(d,n,mod)
            print(value%mod)
        else:
            print(0)
    else:
        print(pow(x,n,mod))
def srch(i, l, Lng, Dst):
    if Lng[i] > l:
        Lng[i] = l
        
    if Dst[i] is not None and len(Dst[i]) > 0:
        for c in Dst[i]:
            srch(c,l+1, Lng, Dst)

def main():
    num = int(input())
    Dst = [None for i in range(num + 1)]
    Lng = [999] * (num + 1)

    for n in range(1, num+1):
        a = list(map(int,input().split()))
        u = a[0]
        if a[1] > 0:
            Dst[u] = a[2:]

    srch(1, 0, Lng, Dst)

    for n in range(1, num+1):
        l = Lng[n]
        if l > num:
            l = -1
        print("{} {}".format(n,l))

if __name__ == '__main__':
    main()

### FIXED CODE ###

def srch(i, l, Lng, Dst):
    if Lng[i] != -1 and Lng[i] < l:
        return
    Lng[i] = l
    if Dst[i] is not None and len(Dst[i]) > 0:
        for c in Dst[i]:
            srch(c,l+1, Lng, Dst)

def main():
    num = int(input())
    Dst = [None for i in range(num + 1)]
    Lng = [-1] * (num + 1)
    
    for n in range(1, num+1):
        a = list(map(int,input().split()))
        u = a[0]
        if a[1] > 0:
            Dst[u] = a[2:]

    srch(1, 0, Lng, Dst)

    for n in range(1, num+1):
        l = Lng[n]
        if l > num:
            l = -1
        print("{} {}".format(n,l))

if __name__ == '__main__':
    main()
N, M = map(int, input().split())
memo = [0]*(N+1)
memo[1] = 1
memo[2] = 2
mod = 10**9+7

for _ in range(M):
    ai = int(input())
    memo[ai] = None

if memo[1] == None:
    memo[2] = 1

for i in range(3, N+1):
    tmp = 0
    if memo[i] == None:
        continue
    if memo[i-1] != None:
        tmp += memo[i-1]
    if memo[i-2] != None:
        tmp += memo[i-2]
    memo[i] = tmp

print(memo[N]%mod)


### FIXED CODE ###

#ABC-129-C
N, M = map(int, input().split())
# N, M = map(int, input().split())
a = [int(input()) for i in range(M)]

dp = [0] * (N+1)
#どうやってもスタート地点から始まるから、0に行く方法は1通りのみ
dp[0] = 1

#1が壊れていなければ1に行く方法は0->1の1通りのみ
if 1 not in a:
    dp[1] = 1
    not_broken_stairs = set(range(2, N+1)) - set(a)
else:
    not_broken_stairs = set(range(1, N+1)) - set(a)    

#i=2or3から始まる。
#１が壊れていなければ2に行く方法は(0->2の1通り)+(1->2の1通り)で2通り。
for i in not_broken_stairs:
    dp[i] = dp[i-2] + dp[i-1]
    
print(dp[-1] % (10 ** 9 + 7))
#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

H, W = map(int,input().split())
sth, stw = 0, 0
glh, glw = H-1, W-1

INF = -1
Gmap = [list(input()) for _ in range(H)]
Dist = [[INF]*W for _ in range(H)]
direc = {(1,0), (-1,0), (0,1), (0,-1)}
next_q = deque([])

def dfs_settings():
    #複数
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                next_q.append([h,w])
                Dist[h][w]=0

def dfs():
    ret = 0
    while len(next_q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = next_q.popleft()
        hs, ws = h + 0 , w + 1
        if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF and ws<W:
            next_q.append([hs,ws])
            Dist[hs][ws] = Dist[h][w] + 1
            ret = max(ret, Dist[hs][ws])
        hs, ws = h + 1 , w + 0
        if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF and hs<H:
            next_q.append([hs,ws])
            Dist[hs][ws] = Dist[h][w] + 1
            ret = max(ret, Dist[hs][ws])
        hs, ws = h +0 , w - 1
        if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF and ws>=0:
            next_q.append([hs,ws])
            Dist[hs][ws] = Dist[h][w] + 1
            ret = max(ret, Dist[hs][ws])
        hs, ws = h - 1 , w + 0
        if Gmap[hs][ws]=='.' and Dist[hs][ws]==INF and hs>=0:
            next_q.append([hs,ws])
            Dist[hs][ws] = Dist[h][w] + 1
            ret = max(ret, Dist[hs][ws])
    return ret

def main():
    dfs_settings()
    ret = dfs()
    print(ret)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

from collections import deque

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

INF = -1
Gmap = [list(input()) for _ in range(H)]
next_q = deque([])

def dfs_settings():
    #複数
    for h in range(H):
        for w in range(W):
            if Gmap[h][w]=='#':
                next_q.append([h,w])
                Gmap[h][w]=0

def dfs():
    ret = 0
    while len(next_q)!=0:
        #スタック取り出し(先頭)幅優先
        h,w = next_q.popleft()
        lv=Gmap[h][w]+1
        hs, ws = h + 0 , w + 1
        if ws<W and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 1 , w + 0
        if hs<H and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h + 0 , w - 1
        if ws>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
        hs, ws = h - 1 , w + 0
        if hs>=0 and Gmap[hs][ws]=='.':
            next_q.append([hs,ws])
            Gmap[hs][ws] = lv
            ret = max(ret, Gmap[hs][ws])
    return ret

def main():
    dfs_settings()
    ret = dfs()
    print(ret)

if __name__ == '__main__':
    main()
import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    W,H,x,y=map(int,input().split())
    S=W*H/2
    b=1 if x==W//2 and y==H//2 else 0
    print(f'{S} {b}')

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)
def input():
    return sys.stdin.readline().rstrip()

def main():
    W,H,x,y=map(int,input().split())
    S=W*H/2
    b=1 if x==W/2 and y==H/2 else 0
    print(str(S)+' '+str(b))

if __name__ == '__main__':
    main()
h,w=map(int,input().split())
pic=[["#" for i in range(w+2)]]
for i in range(h):
  s=list(input())
  s="#"+s+"#"
  pic.append(s)
pic.append(["#" for i in range(w+2)])

for i in pic:
  print("".join(i))

### FIXED CODE ###

h,w=map(int,input().split())
pic=[["#" for i in range(w+2)]]
for i in range(h):
  s=list(input())
  s=["#"]+s+["#"]
  pic.append(s)
pic.append(["#" for i in range(w+2)])

for i in pic:
  print("".join(i))
import math
import functools

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

def gcd(numbers):
    return functools.reduce(math.gcd, numbers)
  
print(gcd(a))

### FIXED CODE ###

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

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

def gcd_list(a):
  for i in range(n - 1):
    a[i + 1] = gcd(a[i], a[i + 1])
  return a[n - 1]
  
print(gcd_list(a))
N,Q = map(int,input().split())
def dfs(x, score):
    for y in Tree[x]:
        if Parent[x] != y:
            Parent[y] = x
            score[y] += score[x]
            dfs(y, score)
Tree = [[] for i in range(N+1)]
Parent = [0]*(N+1)
for i in range(N-1):
    a,b = map(int,input().split())
    Tree[a].append(b)
    Tree[b].append(a)
score = [0]*(N+1)
for j in range(Q):
    p,x = map(int,input().split())
    score[p] += x
dfs(1,score)
for i in score[1:]:
    print(i)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1<<30)
N,Q = map(int,input().split())
def dfs(x, score):
    for y in Tree[x]:
        if Parent[x] != y:
            Parent[y] = x
            score[y] += score[x]
            dfs(y, score)
Tree = [[] for i in range(N+1)]
Parent = [0]*(N+1)
for i in range(N-1):
    a,b = map(int,input().split())
    Tree[a].append(b)
    Tree[b].append(a)
score = [0]*(N+1)
for j in range(Q):
    p,x = map(int,input().split())
    score[p] += x
dfs(1,score)
print(*score[1:],end="\t")
n,k = [int(_) for _ in input().split()]
s = input()

c0 = 0
c1 = 0
a = [0]
b = []
v = 0
while s[v] == '0':
    c0 += 1
    s = s[1:]
b.append(c0)
c0 = 0
for i in range(len(s)):
    if s[i] == '1':
        c1 += 1
        if c0 != 0:
            b.append(c0)
        c0 = 0
    else:
        c0 += 1
        if c1 != 0:
            a.append(c1)
        c1 = 0
if c0 != 0:
    b.append(c0)
else:
    a.append(c1)
    b.append(0)
a.append(0)
# print(a)
# print(b)

s_a = [0]
s_b = [0]
for i in range(len(a)):
    s_a.append(s_a[i]+a[i])
for i in range(len(b)):
    s_b.append(s_b[i]+b[i])
# print(s_a)
# print(s_b)

ans = 0
if len(b) <= k:
    ans = n
else:
    for i in range(len(a)-k):
        # print(s_a[i+k+1] - s_a[i] + s_b[i+k] - s_b[i])
        ans = max(ans, s_a[i+k+1] - s_a[i] + s_b[i+k] - s_b[i])  
print(ans)


### FIXED CODE ###

import sys


n,k = [int(_) for _ in input().split()]
s = input()

all_0 = True
for i in range(len(s)):
    if s[i] == '1':
        all_0 = False
        break
if all_0:
    if k == 0:
        print(0)
    else:
        print(n)
    sys.exit()

c0 = 0
c1 = 0
a = [0]
b = []
v = 0
while s[v] == '0':
    c0 += 1
    s = s[1:]
b.append(c0)
c0 = 0
for i in range(len(s)):
    if s[i] == '1':
        c1 += 1
        if c0 != 0:
            b.append(c0)
        c0 = 0
    else:
        c0 += 1
        if c1 != 0:
            a.append(c1)
        c1 = 0
if c0 != 0:
    b.append(c0)
else:
    a.append(c1)
    b.append(0)
a.append(0)
# print(a)
# print(b)

s_a = [0]
s_b = [0]
for i in range(len(a)):
    s_a.append(s_a[i]+a[i])
for i in range(len(b)):
    s_b.append(s_b[i]+b[i])
# print(s_a)
# print(s_b)

ans = 0
if len(b) <= k:
    ans = n
else:
    for i in range(len(a)-k):
        # print(s_a[i+k+1] - s_a[i] + s_b[i+k] - s_b[i])
        ans = max(ans, s_a[i+k+1] - s_a[i] + s_b[i+k] - s_b[i])  
print(ans)
N,M,s=map(int,input().split())
S=sum(s)
if sorted(s)[-1:-m]<S/(4*M):
    print('No')
else:
    print('Yes')


### FIXED CODE ###

x,y = map(int,input().split())
A=list(map(int,input().split()))
T=sum(A)
a=0
for i in range(x):
  if A[i]>=T/(4*y):
    a+=1
if a>=y:
    print('Yes')
else:
    print('No')
N=int(input())


lista=[chr(i) for i in range(97, 97+26)]
alphlist=[1]
anslist=[]
for i in range(1,12):
    if i==1:
        a=alphlist[i-1]+26**i-1
    else:
        a=alphlist[i-1]+26**i
    alphlist.append(a)

for i in range(12):
    if N<=alphlist[i]:
        keta=i
        break
a=keta
Ni=N
for i in range(a):
    Ni=Ni-sum(alphlist[0:a-i-1])+1
    at=Ni//alphlist[a-i-1]-2
    Ni=Ni-(at+1)*alphlist[a-i-1]
    print(Ni,at)
    anslist.append(lista[at])
print(''.join(anslist))

### FIXED CODE ###


N = int(input())

ans = ""
while N > 0:
    N-=1                        #-1 means "a"
    ans += chr(ord('a') + N%26) #chr: Unicode to character, ord:character to Unicode
    N//=26                      #next power of 26

print(ans[::-1])                #sort reverse
#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))
  
n=int(input())
a=input_array()
q=int(input())
BC=[input_array() for _ in range(q)]
SUM=sum(a)

A=[0]*10**5
for i in a:
	A[i]+=1

for bc in BC:
	diff= bc[1]-bc[0]
	SUM+=diff*A[bc[0]]
	A[bc[1]]+=A[bc[0]]
	A[bc[0]]-=A[bc[0]]
	print(SUM)

### FIXED CODE ###

#入力:[n1,n2,...nk](int:整数配列)
def input_array():
	return list(map(int,input().split()))

n=int(input())
a=input_array()
q=int(input())
BC=[input_array() for _ in range(q)]
SUM=sum(a)

A=[0]*(10**5+1)
for i in a:
	A[i]+=1

for bc in BC:
	diff= bc[1]-bc[0]
	SUM+=diff*A[bc[0]]
	A[bc[1]]+=A[bc[0]]
	A[bc[0]]-=A[bc[0]]
	print(SUM)
a = input()
b = 0
C = -1
d = 0

for i in range(len(a)):
	if a[b] != a[c]:
      d = d + 1
    b = b + 1
    C = c - 1

print(d/2)

### FIXED CODE ###

a = input()
b = 0
c = -1
d = 0
 
for i in range(len(a)):
    if a[b] != a[c]:
      d = d + 1
    b = b + 1
    c = c - 1

print(d//2)
s = input()
s = sorted(s)
if s = ['a','b','c']:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

s = input()
c = ''.join(sorted(s))
print('Yes') if c == 'abc' else print('No')
import itertools

N,Q = map(int, input().split())
S = input()
a = list(itertools.accumulate([i for i in S]))

for i in range(Q):
    l,r = map(int, input().split())
    b = a[r-1][l-1:]
    print(b.count('AC'))

### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
count = [0]*N
for i in range(1,N):
    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])
A, B, C, K = map(int, input().spliit())
if K <= A :
    print(K)

elif K <= A + B:
    print(A)

else:
    print(A - (K - (A + B)))


### FIXED CODE ###

A, B, C, K = map(int, input().split())
if K <= A :
    print(K)

elif K <= A + B:
    print(A)

else:
    print(A - (K - (A + B)))
n, m = map(int, input().split())
S, C = []
for _ in range(m):
  s, c = map(int, input().split())
  S.append(s)
  C.append(c)
  
for num in range(10 ** (max(S) - 1), 10 ** n):
  num = str(num)
  f = 1
  for s, c in zip(S, C):
    s = s - 1
    if int(num[s]) != c:
      f = 0
      break
      
  if f:
    ans = num
    break
    
print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
 
num = [-1] * n
ans = -1
f = 1
 
for _ in range(m):
  s, c = map(int, input().split())
  if s == 1 and c == 0:
    if n == 1:
      ans = 0
    f = 0
    break
    
  i = num[s - 1]
  if i == -1:
    num[s-1] = c
  elif i == c:
    continue
  else:
    f = 0
    break
  
if num[0] == -1:
  if n == 1:
    num[0] = 0
  else:
    num[0] = 1
  
if f:
  num = [0 if n == -1 else n for n in num]
  ans = ''.join(map(str, num))
  
print(ans)
n, h = map(int, input().split())
a = []
b = []
for i in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
a = sorted(a, reverse=True)
b = sorted(b, reverse=True)

count = 0
while True:
    if h <= 0:
        break
    elif b[0] <= a[0]:
        count += -(- h // a[0])
        break
    else:
        h -= b.pop(0)
        count += 1

print(count)

### FIXED CODE ###

n, h = map(int, input().split())
a = []
b = []
for i in range(n):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
b.append(0)
a2 = sorted(a, reverse=True)
b2 = sorted(b, reverse=True)

count = 0
while True:
    if h <= 0:
        break
    elif b2[0] <= a2[0]:
        count += -(- h // a2[0])
        break
    else:
        h -= b2.pop(0)
        count += 1

print(count)
def main():
    a, b, c = map(int, input().split())
    if sum(a, b, c) == 17:
        print('YES')
    else:
        print('NO')


if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    a, b, c = map(int, input().split())
    if a + b + c == 17:
        print('YES')
    else:
        print('NO')


if __name__ == "__main__":
    main()
n, m, x = map(int, input().split())
P = list(map(int,input().split())
a, b = 0, 0

for i in range(m):
    if P[i]  > x:
        a += 1
    else:
        b += 1
print(min(a, b))

### FIXED CODE ###

n, m, x = map(int, input().split())
P = list(map(int,input().split()))
a, b = 0, 0

for i in range(m):
    if P[i]  > x:
        a += 1
    else:
        b += 1
print(min(a, b))
import math

def calc_comb(n):
    k = 2
    if n <= 1 :
        return 0
    elif n ==2 :
        return 1
    return math.factorial(n)/(math.factorial(n-k) * math.factorial(k))

n = int(raw_input(""))

smap = {}
tmp = ""
for i in range(0, n):
    tmp = ''.join(sorted(raw_input("")))
    if smap.get(tmp, None) == None:
        smap[tmp] = 1
    else:
        smap[tmp] += 1
count = 0
for s, num in smap.items():
    #print num
    count += calc_comb(num)
print(count)


### FIXED CODE ###

import math

def calc_comb(n):
    k = 2
    if n <= 1 :
        return 0
    elif n ==2 :
        return 1
    return math.factorial(n)/(math.factorial(n-k) * math.factorial(k))

n = int(raw_input(""))

smap = {}
tmp = ""
for i in range(0, n):
    tmp = ''.join(sorted(raw_input("")))
    if smap.get(tmp, None) == None:
        smap[tmp] = 1
    else:
        smap[tmp] += 1
count = 0
for s, num in smap.items():
    #print num
    count += calc_comb(num)
print count