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

import bisect


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

for _ in range(m):
    b, c = map(int, input().split())
    i = bisect.bisect_left(A, c)
    if i >= b:
        A[:b] = [c] * b
    else:
        A[:i] = [c] * i
    A.sort()

answer = sum(A)
print(answer)


### FIXED CODE ###

from heapq import *


n, m = map(int, input().split())
PAIRS = [[-a, -1] for a in map(int, input().split())]
heapify(PAIRS)

for _ in range(m):
    b, c = map(int, input().split())
    heappush(PAIRS, [-c, -b])

answer = 0
for _ in range(n):
    pair = heappop(PAIRS)
    answer += -pair[0]
    pair[1] += 1
    if pair[1] != 0:
        heappush(PAIRS, pair)

print(answer)
### BUGGY CODE ###

n= int(input())
#dp = [0]*10**7+1

def fac(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr
ans = 1

for i in range(2, n+1):
    li = fac(i)
    #print(li)
    temp=1
    for j in li:
        temp*=j[-1]+1
    
    ans+=temp*i
print(ans)

### FIXED CODE ###

n= int(input())
dp=[1]*n

for i in range(2, n+1):
    k=1
    while i*k<=n:
        dp[i*k-1]+=1
        k+=1
ans = 0
for i in range(1, n+1):
    ans+=i*dp[i-1]
print(ans)
### BUGGY CODE ###

N,K = map(int, input().split())
P=input().split()
P = [(int(p)+1)/2 for p in P]
maxv=0

for i in range(N-K+1):
    expv=0
    for j in range(K):
        expv+=P[i+j]
    maxv=max(maxv,expv)
    
        
print(maxv)

### FIXED CODE ###

N,K = map(int, input().split())
P=input().split()
P = [int(p) for p in P]
maxv=0
expv=0

for i in range(K):
    expv+=P[i]

maxv=expv

for i in range(N-K):
    expv=expv-P[i]+P[i+K]
    maxv=max(maxv,expv)
    
        
print("{:.20f}".format((maxv+K)/2))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n, k = MI()
p = list(MI())
c = list(MI())

p.insert(0, 0)
c.insert(0, 0)

idx = np.array(range(n + 1))
loop = list()
ans = -(10 ** 9)
for i in range(1, n + 1):
    # passed = np.full(n + 1, -1)
    # passed[i] = 0
    score = 0
    next = i
    for j in range(1, k + 1):
        next = p[next]
        # if passed[next] >= 0:
        #     loop.append(set(idx[passed > passed[next]]))
        #     break
        # else:
        #     passed[next] = j
        score += c[next]
        ans = max(ans, score)

print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys

input = sys.stdin.readline


def S():
    return input().rstrip()


def I():
    return int(input())


def MI():
    return map(int, input().split())


n, k = MI()
p = list(MI())
c = list(MI())

p.insert(0, 0)
c.insert(0, 0)

ans = -float("INF")
for i in range(1, n + 1):
    next = p[i]
    score = 0
    MAX = -float("INF")

    for j in range(1, k + 1):
        score += c[next]
        MAX = max(MAX, score)
        if next == i:
            loop_score = score
            loop_size = j
            if loop_score > 0:
                q, r = divmod(k, loop_size)
                # 周れるだけ周る-1+余りの回数で最大となるマス動く
                score1 = loop_score * (q - 1) + MAX
                # 周れるだけ周る+余りの回数で最大となるマス動くとき
                score2 = loop_score * q
                MAX = score2
                next = p[i]
                for _ in range(1, r + 1):
                    score2 += c[next]
                    MAX = max(MAX, score2)
                    next = p[next]
                score = max(score1, MAX)
                break
            else:
                # 一周未満
                score = MAX
                break
        else:
            next = p[next]
    else:
        score = MAX

    ans = max(ans, score)


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

from collections import Counter
n = int(input())
a = list(map(int,input().split()))
a.sort()
t = Counter(a)
b = []
for i, j in t.most_common():
	if j == 1:
		b.append(i)
bset = set(a)

def makediv(n):
	lower_divisors , upper_divisors = [], []
	i = 1
	while i*i <= n:
		if n % i == 0:
			lower_divisors.append(i)
			if i != n // i:
				upper_divisors.append(n//i)
		i += 1
	return lower_divisors + upper_divisors[::-1]

ans = 0
for i in b:
	k = makediv(i)
	k.remove(i)
	mode = 1
	for l in k:
		if l in bset:
			mode = 0
			break
	if mode:
		ans += 1
print(ans)

### FIXED CODE ###

import itertools
from collections import Counter
h = int(input())
if h == 1:
	print(1)
	exit()
a = list(map(int,input().split()))
t = Counter(a)
b = []
for i, j in t.most_common():
	if j == 1:
		b.append(i)
bset = set(a)

def sieve(n):
	ret = []
	divlis = [-1]*(n+1)  # 何で割ったかのリスト(初期値は-1)
	flag = [True]*(n+1)
	flag[0] = False
	flag[1] = False
	ind = 2
	while ind <= n:
		if flag[ind]:
			ret.append(ind)
			ind2 = ind**2
			while ind2 <= n:
				flag[ind2] = False
				divlis[ind2] = ind
				ind2 += ind
		ind += 1
	#何で割ったかのリストを取得したいとき, divlisも出力する
	return ret

k = sieve(1000)

def pfact(m):
	pf = {}
	cnt = 0
	i = k[cnt]
	st = len(k)
	while m > 1 and cnt < st:
		i = k[cnt]
		while m%i == 0:
			pf[i] = pf.get(i,0) + 1
			m //= i
		cnt += 1
	if m>1 : pf[m]=1
	return pf

def makediv(n):
	s = pfact(n)
	k = [range(i+1) for i in s.values()]
	ansl = []
	for i in itertools.product(*k):
		ans = 1
		for n, j in enumerate(s.keys()):
			ans *= (j**i[n])
		ansl.append(ans)
	ansl.sort()
	return ansl

ans = 0
for i in b:
	t=makediv(i)
	t.remove(i)
	mode = 1
	for l in t:
		if l in bset:
			mode = 0
			break
	if mode:
		ans += 1
print(ans)
### BUGGY CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
import numpy as np
n, k = map(int, input().split())
s_list = []
a_list = np.zeros(n + 1, dtype=int)
a_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    for j in range(l, r + 1):
        s_list.append(j)
s_list.sort()
for i in range(1, n):
    for s in s_list:
        if i + s > n:
            break
        a_list[i + s] += a_list[i]
print(a_list[n] % 998244353)



### FIXED CODE ###

#!/usr/bin/python3
# -*- coding: utf-8 -*-
n, k = map(int, input().split())
s_list = []
a_list = [0] * (n + 1)
b_list = [0] * (n + 1)
a_list[1] = 1
b_list[1] = 1
for i in range(k):
    l, r = map(int, input().split())
    s_list.append([l, r + 1])

for i in range(2, n + 1):
    for l, r in s_list:
        t2 = max(0, i - l)
        t1 = max(0, i - r)
        a_list[i] += b_list[t2] - b_list[t1]
    b_list[i] = (b_list[i - 1] + a_list[i]) % 998244353

print(a_list[n] % 998244353)
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readints():return list(map(int,readline().split()))

from collections import deque

h,w = readints()

ys,xs = (x-1 for x in readints())
yg,xg = (x-1 for x in readints())

maze = [readstr() for i in range(h)]

dist = [[10**10]*w for i in range(h)]

dq = deque()
dq.append([ys,xs])
dist[ys][xs] = 0

while dq:
    y,x = dq.popleft()
    for dy in range(-2,3):
        for dx in range(-2,3):
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.' and dist[y+dy][x+dx]>dist[y][x]:
                if abs(dy)+abs(dx)==1:
                    dq.appendleft((y+dy,x+dx))
                    dist[y+dy][x+dx] = dist[y][x]
                else:
                    dq.append((y+dy,x+dx))
                    dist[y+dy][x+dx] = dist[y][x] + 1

print(-1 if dist[yg][xg]==10**10 else dist[yg][xg])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))

import heapq
def dijkstra(s,path):
    # 距離をinfで初期化
    d = [float('inf')]*len(path)
    d[s] = 0

    # sへの距離は0
    q = [(0,s)]
    heapq.heapify(q)

    # 距離が最小の頂点から更新していけば良い
    while q:
        c,p = heapq.heappop(q)

        # 頂点pまでの距離がheap内のpまでの距離より小さい場合、continue
        if d[p]<c:
            continue

        # 頂点pから伸びる、全ての辺の距離を確認
        for to,cost in path[p]:
            # 頂点pから行ける頂点の距離がpまでの距離とpからの距離の和より小さい場合 -> 距離を更新し、heapに追加
            if d[to] > d[p] + cost:
                d[to] = d[p] + cost
                heapq.heappush(q,(d[to], to))
    return d

h,w = readints()

start = readints()
start = (start[0]-1)*w + start[1]-1

goal = readints()
goal = (goal[0]-1)*w + goal[1]-1

maze = [readstr() for i in range(h)]

path = [[] for i in range(h*w)]
for i in range(h*w):
    y = i//w
    x = i%w
    if maze[y][x]=='#':
        continue
    for dy in range(-2,3):
        for dx in range(-2,3):
            if dy==dx==0:
                continue
            if 0<=y+dy<h and 0<=x+dx<w and maze[y+dy][x+dx]=='.':
                j = (y+dy)*w + x+dx
                if (dy==0 and abs(dx)==1) or (abs(dy)==1 and dx==0):
                    path[i].append((j,0))
                else:
                    path[i].append((j,1))

d = dijkstra(start,path)
print(-1 if d[goal]==float('inf') else d[goal])
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
count = 0

for i in range(Q):
  l, r = map(int,input().split())
  Si = S[l-1:r]
  
  len_Si = len(Si)
  for i in range(len_Si-1):
    if Si[i] == 'A':
      if Si[i+1] == 'C':
        count += 1
  print(count)
  count = 0

### FIXED CODE ###

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

import numpy as np

x, move, d = map(int, input().split())

for k in range(move):

    if np.sign(x) == 1:
        x = x-d
    else:
        x = x+d

    if abs(x) <= d and (move-(k+1))%2==0:
        break


print(abs(x))


### FIXED CODE ###

import numpy as np

x, move, d = map(int, input().split())

num = int(abs(x)/d)
ans = 0

if move <= num:
    if np.sign(x) == 1:
        ans = x-d*move
    else:
        ans = x+d*move

elif (move-num)%2==0:
    if np.sign(x) == 1:
        ans = x-d*num
    else:
        ans = x+d*num

elif (move-num)%2!=0:
    if np.sign(x) == 1:
        ans = x-d*(num+1)
    else:
        ans = x+d*(num+1)


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

#C問題
import heapq
N = int(input())
A = list(map(int,input().split()))

a = []
for i in range(N):
    heapq.heappush(a,A[i])
B = []
for i in range(3*N):
    B.append(-A[3*N-1-i])
b = []
for i in range(N):
    heapq.heappush(b,B[i])

Red = [sum(a) for i in range(N+1)]
Blue = [sum(b) for i in range(N+1)]
inf = float("inf")
MAX = -inf
for i in range(N):
    k = N+i
    l = heapq.heappushpop(a,A[k])
    Red[i+1] = Red[i]+(A[k]-l)
for i in range(N):
    k = N+i
    #print(k)
    m = heapq.heappushpop(b,B[k])
    Blue[i+1] = Blue[i]+(B[k]-m)
    
for i in range(N+1):
    #print(Red[i],Blue[N-i])
    MAX = max(MAX,Red[i]+Blue[N-i])

#print(A,B)
print(MAX)


### FIXED CODE ###

#C問題
import heapq
N = int(input())
A = list(map(int,input().split()))

a = []
for i in range(N):
    heapq.heappush(a,A[i])
B = []
for i in range(3*N):
    B.append(-A[3*N-1-i])
b = []
for i in range(N):
    heapq.heappush(b,B[i])

Red = [sum(a)]
Blue = [sum(b)]
inf = float("inf")
MAX = -inf
AR = []
BB = []
for i in range(N):
    AR.append(A[N+i])
    BB.append(B[N+i])
for i,(ar,r) in enumerate(zip(AR,Red)):
    l = heapq.heappushpop(a,ar)
    Red.append(r+(ar-l))
for i,(bb,bl) in enumerate(zip(BB,Blue)):
    m = heapq.heappushpop(b,bb)
    Blue.append(bl+(bb-m))
    
for i in range(N+1):
    #print(Red[i],Blue[N-i])
    MAX = max(MAX,Red[i]+Blue[N-i])

#print(A,B)
print(MAX)
### BUGGY CODE ###

def main():
    n, q = map(int, input().split())
    s = input()
    lr =  [list(map(int, input().split())) for _ in range(q)]
    
    for l, r in lr:
        print(s[l-1:r].count('AC'))
    
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, q = map(int, input().split())
    s = input()
    
    t = [0] * n
    pre = s[0]
    t_sum = 0
    for i in range(1, n):
        if pre == 'A' and s[i] == 'C':
            t[i] = t_sum + 1
            t_sum +=  1
        else: 
            t[i] = t_sum
        pre = s[i]
    for _ in range(q):
        l, r = map(int, input().split())
        print(t[r - 1] - t[l - 1])
        
    
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
a = [int(input()) for _ in range(n)]

for i in range(n):
  t = a.pop(i)
  print(max(a))
  a.insert(i,t)

### FIXED CODE ###

n = int(input())
a = [0]*n
for i in range(n):
  a[i] = int(input())

x = sorted(set(a), reverse = True)
t = [0]*2
if len(x) > 1:
  t[0],t[1] = x[0],x[1]
else:
  t[0],t[1] = x[0],x[0]
  
max = t[0]
count= a.count(max)
for i in range(n):
  if a[i] == max:
    if count > 1:
      print(max)
    else:
      print(t[1])
  else:
    print(max)
### BUGGY CODE ###

S=list(input())
Q=int(input())
ls=[list(input().split()) for _ in range(Q)]
a=1
for i in range(Q):
  if ls[i][0]=="1":
    a*=(-1)
  else:
    if (ls[i][1]=="1" and a==1) or (ls[i][1]=="2" and a==-1):
      S.insert(0,ls[i][2])
    else:
      S.append(ls[i][2])
print("".join(S) if a==1 else "".join(reversed(S)))

### FIXED CODE ###

from collections import deque
S=list(input())
Q=int(input())
ls=[list(input().split()) for _ in range(Q)]
D=deque()
for i in range(len(S)):
  D.append(S[i])  
a=1
for i in range(Q):
  if ls[i][0]=="1":
    a*=(-1)
  else:
    if (ls[i][1]=="1" and a==1) or (ls[i][1]=="2" and a==-1):
      D.appendleft(ls[i][2])
    else:
      D.append(ls[i][2])
if a==1:
  while D:
    print(D.popleft(), end="")
else:    
  while D:
    print(D.pop(), end="")
### BUGGY CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10 ** 9)
input = sys.stdin.readline

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

sushi = [0,0,0]
for a in A:
  sushi[a-1] += 1
#print(sushi)

# dp[i][j][k]:寿司3個のお皿がi枚、2個のがj枚、1個がk枚のときの期待値
# dp[i][j][k] = i/N * dp[i-1][j+1][k]
#             + j/N * dp[i][j-1][k+1]
#             + k/N * dp[i][j][k-1]
#             + (N-i-j-k)/N * dp[i][j][k]
#             + 1
# dp[i][j][k]を移項すると、
# dp[i][j][k] = 1/(i+j+k) * (i * dp[i-1][j+1][k]
#                          + j * dp[i][j-1][k+1]
#                          + k * dp[i][j][k-1]
#                          + N)
dp = [[[-1.0 for _ in range(N+1)] for _ in range(sushi[2]+sushi[1]+1)] for _ in range(sushi[2]+1)] # 型推論で時間がかからないように-1ではなく-1.0とする。

def rec(i,j,k):
  if i == 0 and j == 0 and k == 0:
    return 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 0.0 # 型推論で時間がかからないように0ではなく0.0とする。
  if i != 0:
    res += i * rec(i-1,j+1,k)
  if j != 0:
    res += j * rec(i,j-1,k+1)
  if k != 0:
    res += k * rec(i,j,k-1)
  res = (res+N)/(i+j+k)
  dp[i][j][k] = res
  return res

print(rec(sushi[2],sushi[1],sushi[0]))

### FIXED CODE ###

# 再帰関数を使うとTLEになるので、3重ループにしてみる。
from collections import defaultdict

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

sushi = [0,0,0]
for a in A:
  sushi[a-1] += 1

# dp[i][j][k]:寿司3個のお皿がi枚、2個のがj枚、1個がk枚のときの期待値
# dp[i][j][k] = i/N * dp[i-1][j+1][k]
#             + j/N * dp[i][j-1][k+1]
#             + k/N * dp[i][j][k-1]
#             + (N-i-j-k)/N * dp[i][j][k]
#             + 1
# dp[i][j][k]を移項すると、
# dp[i][j][k] = 1/(i+j+k) * (i * dp[i-1][j+1][k]
#                          + j * dp[i][j-1][k+1]
#                          + k * dp[i][j][k-1]
#                          + N)
dp = [[[0.0 for _ in range(N+1)] for _ in range(N+1)] for _ in range(N+1)] # 型推論で時間がかからないように0ではなく0.0とする。

for i in range(N+1):
  for j in range(N+1):
    for k in range(N+1):
      if i+j+k > N or i+j+k == 0:
        continue
      if i>0:
        dp[i][j][k] += i * dp[i-1][j+1][k]
      if j>0:
        dp[i][j][k] += j * dp[i][j-1][k+1]
      if k>0:
        dp[i][j][k] += k * dp[i][j][k-1]
      dp[i][j][k] += N
      dp[i][j][k] /= (i+j+k)

print(dp[sushi[2]][sushi[1]][sushi[0]])
### BUGGY CODE ###

import itertools

n = int(input())

l = list(map(int, input().split()))

zzz = list(itertools.combinations(l,3))

cnt = 0

for z in zzz:
    
    a = z[0]
    b = z[1]
    c = z[2]

    if a >= b + c:
        continue

    if b >= c + a:
        continue

    if c >= a + b:
        continue

    cnt += 1

print(cnt)


### FIXED CODE ###

import bisect

n = int(input())

l = list(map(int, input().split()))

l.sort()

cnt = 0

for i in range(n):
    for j in range(i):
        cnt += bisect.bisect_left(l,l[i]+l[j]) - (i + 1)

print(cnt)
### BUGGY CODE ###

n = int(input())
b = list(map(int, input().split()))
ans = []
def dfs(x):
    if x == []:
        return True
    ret = False
    for i, a in enumerate(x):
        if i + 1 == a:
            ret = dfs(x[:i] + x[i+1:])
            if ret:
                ans.append(a)
                break
    return ret
if dfs(b):
    for a in ans:
        print(a)
else:
    print(-1)

### FIXED CODE ###

n = int(input())
b = list(map(int, input().split()))
ans = []
for k in range(n):
    for i in reversed(range(n - k)):
        a = b[i]
        if i + 1 == a:
            ans.append(b.pop(i))
            break
if b != []:
    print(-1)
else:
    for a in reversed(ans):
        print(a)
### BUGGY CODE ###

N = int(input())
T, A = [0]*N, [0]*N

for i in range(N):
    T[i], A[i] = map(int, input().split())
ans = T[0]+A[0]

for i in range(N-1):
    for j in range(10**8):
        if (ans+j)%(T[i+1]+A[i+1])==0:
            if (ans+j)*T[i+1]/(T[i+1]+A[i+1])>=ans*T[i]/(T[i]+A[i]) and (ans+j)*A[i+1]/(T[i+1]+A[i+1])>=ans*A[i]/(T[i]+A[i]):
                ans += j
                break

print(ans)


### FIXED CODE ###

N = int(input())
T, A = [0]*N, [0]*N

for i in range(N):
    T[i], A[i] = map(int, input().split())
t = a = 1
for i in range(N):
    n = max(-(-t//T[i]), -(-a//A[i]))
    t = n*T[i]
    a = n*A[i]
print(t+a)
### BUGGY CODE ###

n=int(input())
l=list(map(int,input().split()))
l.sort()
ans=0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if l[i]+l[j]>l[k]:
                ans+=1
print(ans)

### FIXED CODE ###

import bisect
n = int(input())
l = sorted(list(map(int,input().split())))

ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        ans += bisect.bisect_left(l,l[i] + l[j]) - (j + 1)


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

n=int(input())
s=[list(map(int,input().split(" "))) for k in range(n)]
ex=[]
for i in range(1,n):
  j=i
  while s[j][0]+s[j][1]>s[j-1][0]+s[j-1][1]:
    ex=s[j]
    s[j]=s[j-1]
    s[j-1]=ex
    j-=1
    if j==0:
      break
c=0
for l in range(n):
  if l%2==0:
    c+=s[l][0]
  else:
    c-=s[l][1]
print(c)    

### FIXED CODE ###

n=int(input())
s=[list(map(int,input().split(" "))) for k in range(n)]
aa=sorted(s,key=lambda x:x[0]+x[1],reverse=True)
c=0
for l in range(n):
  if l%2==0:
    c+=aa[l][0]
  else:
    c-=aa[l][1]
print(c)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
b = [0]*n

for i in range(1, n+1):
  b[i-1] = a.index(i)+1
  
  
print(" ".join(map(str, b)))

### FIXED CODE ###

n=int(input())
l=list(map(int,input().split()))
d=[0]*n
for i,val in enumerate(l):
  d[val-1]=i+1
print(*d)
### BUGGY CODE ###

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

n,q = map(int,input().split())
s = input()
lr = []
for i in range(0,q):
    lr.append(input().split())
map(int,lr)

s = s.replace("AC","QP")

lrCut = []
for i in range(0,q):
    lrCut.append(s[int(lr[i][0]) - 1:int(lr[i][1])])

for i in range(0,q):
    sum = 0
    for index, j in enumerate(lrCut[i]):
        if index == len(lrCut[i]) - 1:
            break
        if lrCut[i][index] == "Q" and lrCut[i][index + 1] == "P":
            sum += 1
    print(sum)


### FIXED CODE ###

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

n, q = map(int,input().split())
s = list(input())
l = [0] * q
r = [0] * q
for i in range(q):
    l[i],r[i] = map(int,input().split())

aclist = []

cnt = 0
for i in range(n):
    if s[i-1] == "A" and s[i] == "C":
        cnt += 1
        aclist.append(cnt)
    else:
        aclist.append(cnt)

for i in range(q):
    print(aclist[r[i]-1] - aclist[l[i]-1])
### BUGGY CODE ###

"""
ABC076_D AtCoderExpress
まず区間に注目してEditorialみたいなグラフを思い描くことがきつかった。
そのうえで、区間Limitをバグなく実装するのが結構ポイント。
あとはVVあたりがバグってないかをPrintしながら見ていく形。
"""
N = int(input())
T = list(map(int,input().split()))
V = list(map(int,input().split()))
TMAX = sum(T)

TS = [0] * (N+1)
for i in range(N):
  TS[i+1] = TS[i] + T[i]
T_Left = TS[:N]
T_Right = TS[1:]
#print(T_Left,T_Right,V)

## これで下記がちゃんとつくれた。
# Tleft[i] <= t <= Tright[i] の間、 V[i]以下でなければいけない

# VV[tt] tt/2秒時の速度。両端がゼロ、という条件から初期値を生成する。
VV = [min(i*0.5, (TMAX*2-i) * 0.5) for i in range(TMAX*2+1)]
#print(VV)

# 区間iについて
for i in range(N):
  for tt in range(TMAX*2+1):
    VV[tt] = min(VV[tt], V[i] + max(0, (T_Left[i]*2 - tt) * 0.5, (tt-T_Right[i]*2) * 0.5))
#print(VV)
# 面積は両端がゼロであることから、速度合計を２で割る（0.5秒ごとだから）で出る。
# v-tグラフの面積を台形の面積で考えればよい。
print(sum(VV)/2)

### FIXED CODE ###

"""
ABC076_D AtCoderExpress
まず区間に注目してEditorialみたいなグラフを思い描くことがきつかった。
そのうえで、区間Limitをバグなく実装するのが結構ポイント。
あとはVVあたりがバグってないかをPrintしながら見ていく形。
"""
N = int(input())
T = list(map(int,input().split()))
V = list(map(int,input().split()))
TMAX = sum(T)

TS = [0] * (N+1)
for i in range(N):
  TS[i+1] = TS[i] + T[i]
T_Left = TS[:N]
T_Right = TS[1:]
#print(T_Left,T_Right,V)

## これで下記がちゃんとつくれた。
# Tleft[i] <= t <= Tright[i] の間、 V[i]以下でなければいけない

# VV[tt] tt/2秒時の速度。両端がゼロ、という条件から初期値を生成する。
VV = [min(i*0.5, (TMAX*2-i) * 0.5) for i in range(TMAX*2+1)]
#print(VV)

# 区間iについて
for i in range(N):
  for tt in range(TMAX*2+1):
    VV[tt] = min(VV[tt], V[i] + max(0, (T_Left[i]*2 - tt) * 0.5, (tt-T_Right[i]*2) * 0.5))
#print(VV)
# 面積は両端がゼロであることから、速度合計を２で割る（0.5秒ごとだから）で出る。
# v-tグラフの面積を台形の面積で考えればよい。
print(sum(VV)/2)
### BUGGY CODE ###

from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
start = time.time()
# N = list(map(int, input()))[::-1]
# N = int(input())
N, M, Q = map(int, input().split())
big = 0
s = 2**N
l = []

moto = list(range(1, Q+1))

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

A = []
for i in range(N):
    AA = []
    if A:
        for k in A:
            for j in range(1, M+1):
                if int(k[-1]) <= j:
                    AA.append(k+str(j))
        A = AA
    else:
        for j in range(1, M+1):
            A.append(str(j))

for i in A:
    wa = 0
    for j in l:
        if (int(i[j[1]-1])-int(i[j[0]-1])) == j[2]:
            wa += j[3]

    if big < wa:
        big = wa
print(big)


### FIXED CODE ###

from collections import defaultdict
from math import gcd
import time
import sys
from collections import Counter
import itertools
import math
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
start = time.time()
# N = list(map(int, input()))[::-1]
# N = int(input())
N, M, Q = map(int, input().split())
big = 0
s = 2**N
l = []

moto = list(range(1, Q+1))

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

A = []
for i in range(N):
    AA = []
    if A:
        for k in A:
            for j in range(1, M+1):
                if k[-1] <= j:
                    AA.append(k+[j])
        A = AA
    else:
        for j in range(1, M+1):
            A.append([j])

for i in A:
    wa = 0
    for j in l:
        if (i[j[1]-1]-i[j[0]-1]) == j[2]:
            wa += j[3]

    if big < wa:
        big = wa
print(big)