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

mod = pow(10, 9) + 7

N = pow(10, 6)

fact = [0]*N
inv = [0]*N

fact[0] = inv[0] = 1
inv[1] = fact[1] = 1
for i in range(2, N):
	fact[i] = (i*fact[i-1])%mod
	inv[i] = pow(fact[i], mod-2, mod)

def ncr(n, r):
	return (fact[n]*inv[r]*inv[n-r])%mod

X, Y = map(int, input().split())

if (X + Y)%3 != 0:
	print(0)
else:
	m = (2*Y - X)//3
	n = (X - m)//2
	if n < 0 or m < 0:
		print(0)
	else:
		ans = ncr(n+m, n)
		print(ans)

### FIXED CODE ###

mod = pow(10, 9) + 7

N = pow(10, 6)

fact = [0]*N
inv = [0]*N

fact[0] = inv[0] = 1
inv[1] = fact[1] = 1
for i in range(2, N):
	fact[i] = (i*fact[i-1])%mod
	inv[i] = pow(fact[i], mod-2, mod)

def ncr(n, r):
	return (fact[n]*inv[r]*inv[n-r])%mod

X, Y = map(int, input().split())

if (X + Y)%3 != 0:
	print(0)
else:
	m = (2*Y - X)//3
	n = (X - m)//2
	if n < 0 or m < 0:
		print(0)
	else:
		ans = ncr(n+m, n)
		print(ans)
### BUGGY CODE ###

import itertools

N, K = map(int, input().split())
candidate = list(range(N+1))
comb = list(itertools.product(candidate, repeat=3))
l = [c for c in comb if sum(c) == K]

print(len(l))

### FIXED CODE ###

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

cnt = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z and z <= k:
            cnt += 1

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

s = input()
t = input()

lens = len(s)
lent = len(t)

dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

dp = [[(0, 0)] * (lent + 1) for _ in range(lens + 1)]
# dp = [[(0, 0) for _ in range(lent + 1)] for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            length, pattern = dp[aindex + 1][bindex + 1]
            r = (length + 1, pattern | (2 << aindex))
        else:
            if dp[aindex + 1][bindex][0] > dp[aindex][bindex + 1][0]:
                r = dp[aindex + 1][bindex]
            else:
                r = dp[aindex][bindex + 1]
        dp[aindex][bindex] = r
for aindex in range(lens):
    if (2 << aindex) & dp[0][0][1]:
        print(s[aindex], end="")
print()


### FIXED CODE ###

s = input()
t = input()

lens = len(s)
lent = len(t)

# dp = [[None] * lent for _ in range(lens)]
# def dfs(aindex=0, bindex=0):
#     if aindex >= lens:
#         return 0
#     if bindex >= lent:
#         return 0
#
#     if dp[aindex][bindex] is not None:
#         return dp[aindex][bindex]
#
#     if s[aindex] == t[bindex]:
#         r = dfs(aindex + 1, bindex + 1) + 1
#     else:
#         r = max(dfs(aindex + 1, bindex), dfs(aindex, bindex + 1))
#     dp[aindex][bindex] = r
#     return r
#
# print(dfs())

shift = [1 << x for x in range(3000 + 1)]

dp = [[0] * (lent + 1) for _ in range(lens + 1)]
for aindex in range(lens - 1, -1, -1):
    for bindex in range(lent - 1, -1, -1):
        if s[aindex] == t[bindex]:
            r = dp[aindex + 1][bindex + 1] + 1
        else:
            r = max(dp[aindex + 1][bindex], dp[aindex][bindex + 1])
        dp[aindex][bindex] = r

ans = ""
ls = len(s)
lt = len(t)
ls = 0
lt = 0
while ls < lens and lt < lent:
    if dp[ls][lt] == dp[ls + 1][lt]:
        ls += 1
    elif dp[ls][lt] == dp[ls][lt + 1]:
        lt += 1
    else:
        ans += t[lt]
        ls += 1
        lt += 1
print(ans)
### BUGGY CODE ###

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

  q.append((0,0,0))

  ind=0
  while len(q)>0:
    ind+=1
    if ind>10**8:
      break

    y,x,cnt=q.pop()
    counter[y][x]=cnt

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]>cnt:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]+1

  if step_cnt==inf+1:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())


### FIXED CODE ###

import math,itertools,fractions,heapq,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()

def main():
  h,w=LI()
  q=[]

  field=[S() for _ in range(h)]
  counter=[[inf]*w for _ in range(h)]

  sharp_cnt=0
  for x in field:
    sharp_cnt+=x.count('#')

  q.append((0,0,1))

  while len(q)>0:
    y,x,cnt=q.pop()
    if counter[y][x]<cnt:
      continue
    counter[y][x]=cnt

    for dy,dx in dd:
      ny=y+dy
      nx=x+dx

      if 0<=ny and 0<=nx and ny<h and nx<w:
        if field[ny][nx]!='#':

          if counter[ny][nx]>cnt+1:
            q.append((ny,nx,cnt+1))

  step_cnt=counter[h-1][w-1]

  if step_cnt==inf:
    return -1

  return h*w-sharp_cnt-step_cnt

# main()
print(main())
### BUGGY CODE ###

N = int(input())
S = [input() for i in range(N) ]
counter = 0
for i in range(N):
    for j in range(i+1,N):
        if sorted(S[i]) == sorted(S[j]):
            counter += 1
print(counter)

### FIXED CODE ###

import math
def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

N = int(input())
dic_s = {}
for i in range(N):
    s = "".join(sorted(input()))
    if s in dic_s:
        dic_s[s] += 1
    else:
        dic_s[s] = 1
counter = 0
for key,value in dic_s.items():
    if value >1:
        counter += combinations_count(value,2)
print(counter)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

# resort list X O(len(X))
def sorting(X, l):
    eX = []
    oX = []
    for x in X:
        if x&(1<<l):
            oX.append(x)
        else:
            eX.append(x)
    return eX + oX

ans = 0
for shift in range(30):
    A = sorting(A, shift)
    B = sorting(B, shift)
    div = (1<<(shift+1))
    count = 0
    l1 = N
    r1 = N
    l2 = N
    r2 = N
    for a in A:
        while a%div + B[l1-1]%div >= div//2 and l1 > 0:
            l1 -= 1
        while a%div + B[r1-1]%div >= div and r1 > 0:
            r1 -= 1
        while a%div + B[l2-1]%div >= div//2*3 and l2 > 0:
            l2 -= 1
        while a%div + B[r2-1]%div >= 2*div and r2 > 0:
            r2 -= 1
        count += (r1-l1) + (r2-l2)
    if count%2 == 1:
        ans += (1<<shift)

print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

# resort list X O(len(X))
def sorting(X, l):
    eX = []
    oX = []
    for x in X:
        if x&(1<<l):
            oX.append(x)
        else:
            eX.append(x)
    return eX + oX

ans = 0
for shift in range(30):
    A = sorting(A, shift)
    B = sorting(B, shift)
    div = (1<<(shift+1))
    count = 0
    l1 = N
    r1 = N
    l2 = N
    r2 = N
    for a in A:
        while a%div + B[l1-1]%div >= div//2 and l1 > 0:
            l1 -= 1
        while a%div + B[r1-1]%div >= div and r1 > 0:
            r1 -= 1
        while a%div + B[l2-1]%div >= div//2*3 and l2 > 0:
            l2 -= 1
        while a%div + B[r2-1]%div >= 2*div and r2 > 0:
            r2 -= 1
        count += (r1-l1) + (r2-l2)
    if count%2 == 1:
        ans += (1<<shift)

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

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

for i in range(K+1, N+1):
  s = x[i-1]
  for j in range(1, K//2):
    s *= x[i-1-j]*x[i-1-(j+1)]
  if K%2==0:
    s=s
  else:
    s=s*(x[i-K])

  u = s/(x[i-1])*(x[i-K-1])
  u=int(u)

  if u<s:
    print("Yes")
  else:
    print("No")

### FIXED CODE ###

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


for i in range(K+1, N+1):
  

  if x[i-K-1]<x[i-1]:
    print("Yes")
  else:
    print("No")
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
for k in range(N):
  ans = ans*A[k]
if ans > 1000000000000000000:
  print("-1")
else:
  print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
ans=1
if A.count(0) >= 1:
  print(0)
else:
  B=[i for i in A if i != 1]
  if len(B) >= 100:
    print("-1")
  else:
    for k in range(len(B)):
      ans=ans*B[k]
    if ans > 1000000000000000000:
      print("-1")
    else:
      print(ans)
### BUGGY CODE ###

n = int(input())
r = [int(input()) for x in range(n)]

cur_max_diff = min(r) - max(r)
cur_min_idx = -1

for i in range(n) :
    
    if i == 0 :
        for j in range(1, n) :
            if r[j] - r[i] > cur_max_diff :
                cur_max_diff = r[j] - r[i]
                cur_min_idx = j
                
    elif i >= cur_min_idx :
        for j in range(i + 1, n) :
            if r[j] - r[i] > cur_max_diff :
                cur_max_diff = r[j] - r[i]
                cur_min_idx = j
    else :
        cur_max_diff = max(cur_max_diff, r[cur_min_idx] - r[i])
        
print(cur_max_diff)
        


### FIXED CODE ###

n = int(input())

# initial observation
cur_min = int(input())
max_diff = -1 * (10**9) - 1

for i in range(n - 1) :
    num = int(input())
    
    max_diff = max(max_diff, num - cur_min)
    
    if num < cur_min :
        cur_min = num
    
print(max_diff)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np
import itertools

H,W = map(int,readline().split())
S = (np.frombuffer(read(),dtype='S1')==b'#').reshape(H,-1)[:,:W].astype(np.int64)

# pad_width
p = min(H,W)+1

def F(S,H,W):
    # L,Uに頂点があって、RDに第3の頂点がある場合。
    # Rは数えずDだけ数えておく
    cnt = 0
    diag = np.zeros((H+p,W+p),np.int64)
    diag[:H,:W] += S
    for n in range(1,H+p):
        diag[n,:W] += diag[n-1,1:W+1]
    for h,w in itertools.product(range(H),range(W)):
        n = h if h<w else w
        L = S[h,w-1::-1][:n]
        U = S[h-1::-1,w][:n]
        RD = diag[h+1:h+n+1,w] - diag[h,w+1:w+n+1]
        cnt += (L*U*RD).sum()
    return cnt

x = []
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))
S = S.T[::-1,:] # 90度回転
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))

answer = sum(x)
print(answer)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np
import itertools

H,W = map(int,readline().split())
S = (np.frombuffer(read(),dtype='S1')==b'#').reshape(H,-1)[:,:W].astype(np.int64)

# pad_width
p = min(H,W)+1

S = np.pad(S,(p,p),'constant')

def F(S,H,W):
    # L,Uに頂点があって、RDに第3の頂点がある場合。
    # Rは数えずDだけ数えておく
    cnt = 0
    diag = np.zeros((H+p,W+p),np.int64)
    diag[:H,:W] += S[p:-p,p:-p]
    for n in range(1,H+p):
        diag[n,:W] += diag[n-1,1:W+1]
    for n in range(1,p):
        cnt += (S[1+p:H+1+p,1-n+p:W+1-n+p] * S[1-n+p:H+1-n+p,1+p:W+1+p] * (diag[1+n:H+1+n,1:W+1]-diag[1:H+1,1+n:W+1+n])).sum()
    return cnt

x = []
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))
S = S.T[::-1,:] # 90度回転
x.append(F(S,H,W))
S = S.T[::-1,:] # 90度回転
x.append(F(S,W,H))

answer = sum(x)
print(answer)
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split(' ')]
cnt = 0
first = 0
xsum_old = 0
r_old = 0
for l in range(0, N):
    xsum = xsum_old
    first = A[l]
    cnt += r_old - l
    for r in range(r_old, N):
        if xsum & A[r] > 0:
            xsum_old = xsum - first
            r_old = r
            break
        xsum += A[r]
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
A_raw = input()
A = [int(i) for i in A_raw.split(' ')]
cnt = 0
first = 0
xsum_old = 0
r_old = 0
for l in range(0, N):
    xsum = xsum_old
    first = A[l]
    cnt += r_old - l
    isBreak = False
    for r in range(r_old, N):
        if xsum & A[r] > 0:
            xsum_old = xsum - first
            r_old = r
            isBreak = True
            break
        xsum += A[r]
        cnt += 1
    if isBreak == False:
        r_old = r
print(cnt)
### BUGGY CODE ###

from math import factorial
#a = factorial(n) / factorial(r) / factorial(n - r)
n,m = map(int,input().split())
l = list(map(int,input().split()))
def modinv(a, mod=10**9+7):
    return pow(a, mod-2, mod)
def combination(n, r, mod=10**9+7):
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * modinv(i+1, mod) % mod
    return res
l.sort()
ans = 0
mod = 10**9+7
for i in range(n-m+1):
    for j in range(i+m-1,n):
        a = combination(j-i-1,m-2)
        
        ans += a*(l[j]-l[i])
      
        ans %= mod
print(ans%mod)


### FIXED CODE ###

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

mod = 10**9+7

fact = [1]
for i in range(n):
    fact.append(fact[-1]*(i+1)%mod)

finv = [1]*(n+1)
finv[n] = pow(fact[-1],mod-2,mod)
for i in range(n-1,0,-1):
    finv[i] = ((i+1)*finv[i+1])%mod

def combi(n,k,mod):
    return (fact[n]*finv[k]*finv[n-k])%mod

l.sort()

ans = 0
for i in range(n-k+1):
    tmp = combi(n-i-1,k-1,mod)
    ans += tmp*(l[-i-1]-l[i])
    ans %= mod

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

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    diff = 10 ** 10
    for i in range(N):
        partA = sum(A[:i])
        partB = sum(A[i:])
        diff = min(diff, abs(partA-partB))
    
    print(diff)
    return
resolve()

### FIXED CODE ###

def resolve():
    N = int(input())
    A = list(map(int, input().split()))
    diff = 10 ** 10

    partA = 0
    partB = sum(A)

    for i in range(N):
        diff = min(diff, abs(partA-partB))
        partA += A[i]
        partB -= A[i]
    print(diff)
    return
resolve()
### BUGGY CODE ###

n = int(input())
lista = [int(e) for e in input().split()]
ans = 1
for i in lista:
    ans = ans *i

if ans > 10**18:
    ans=-1

print(ans)

### FIXED CODE ###

n = int(input())
lista = [int(e) for e in input().split()]

if 0 in lista:
    ans = 0
else:
    ans = 1
    for i in lista:
        ans *= i
        if ans>10**18:
            ans = -1
            break

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

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


N = int(input())
L = list(map(int, input().split()))
L.sort()
bit = BIT(L[-1]*2+1)
bit.add(L[0]+L[1], 1)
total = 1
ans = 0
for k in range(2, N):
  ans += total - bit.sum(L[k])
  for j in range(k):
    bit.add(L[j]+L[k], 1)
    total += 1

print(ans)  


### FIXED CODE ###

# Binary Indexed Tree (Fenwick Tree)
class BIT:
    def __init__(self, n):
        self.n = n
        self.data = [0]*(n+1)
        self.el = [0]*(n+1)
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.data[i]
            i -= i & -i
        return s
    def add(self, i, x):
        # assert i > 0
        self.el[i] += x
        while i <= self.n:
            self.data[i] += x
            i += i & -i
    def get(self, i, j=None):
        if j is None:
            return self.el[i]
        return self.sum(j) - self.sum(i)


N = int(input())
L = list(map(int, input().split()))
L.sort()
bit = BIT(L[-1]*2+1)
bit.add(L[0]+L[1], 1)
total = 1
ans = 0
for k in range(2, N):
  ans += total - bit.sum(L[k])
  for j in range(k):
    bit.add(L[j]+L[k], 1)
    total += 1

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

def main():
    from collections import deque
    n, q = map(int, input().split())
    g = [[] for i in range(n+1)]
    point = [0 for i in range(n+1)]
    for i in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
    for i in range(q):
        p, x = map(int, input().split())
        point[p] += x

    q = deque([[1,0]])
    for j in range(n):
        now = q.pop()
        point[now[0]] += point[now[1]]
        for i in g[now[0]]:
            if i==now[1]:
                continue
            q.append([i,now[0]])
    for i in range(1, n+1):
        print(point[i], end='')
        if i!=n:
            print(' ', end='')

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    from collections import deque
    n, q = map(int, input().split())
    g = [[] for i in range(n+1)]
    point = [0 for i in range(n+1)]
    for i in range(n-1):
        a, b = map(int, input().split())
        g[a].append(b)
        g[b].append(a)
    for i in range(q):
        p, x = map(int, input().split())
        point[p] += x

    q = deque([[1,0]])
    for j in range(n):
        now = q.pop()
        point[now[0]] += point[now[1]]
        for i in g[now[0]]:
            if i==now[1]:
                continue
            q.append([i,now[0]])
    for i in range(1, n+1):
        print(point[i], end='')
        if i!=n:
            print(' ', end='')

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

sieve=[0]*1000009
n=int(input())
s=sorted(map(int,input().split()))
for i in s:
    for j in range(i,1000009,i):sieve[j]+=1
print(sum(sieve[i]==1for i in s))

### FIXED CODE ###

sieve=[0]*1000009
n=int(input())
s=sorted(map(int,input().split()))
for i in s:
    if sieve[i]<2:
        for j in range(i,1000009,i):sieve[j]+=1
print(sum(sieve[i]==1for i in s))
### BUGGY CODE ###

K = int(input())
res = '-1'
a = 0
for n in range(K):
  a += 7*(10**n)
  if a%K==0:
    res = n+1
    break
print(res)


### FIXED CODE ###

K = int(input())
ans = '-1'
mod = 7%K
path = [mod]
for i in range(1,K+1):
  if mod == 0:
    ans = i
    break
  mod = (mod*10 + 7)%K
  path.append(mod)
  if mod == path[0]:
    ans = '-1'
    break
print(ans)
### BUGGY CODE ###

# My Answer -> TLE
N = int(input())
A = list(map(int, input().split()))

a = [(i, ai) for i, ai in enumerate(A)]
a = sorted(a, key=lambda x: x[1], reverse=True)

# import numpy as np
# dp = np.zeros((N+1, N+1), np.int8)

dp = [[0] * (N + 1) for _ in range(N + 1)]

dp[0][0] = 0
for i, ai in enumerate(a):
    for l in range(i+1):
        r = i - l
        dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
        dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

print(max(dp[N]))

### FIXED CODE ###

def solve(N, A):
    a = [(i, ai) for i, ai in enumerate(A)]
    a.sort(key=lambda x: x[1], reverse=True)

    # import numpy as np
    # dp = np.zeros((N+1, N+1), np.int8)

    dp = [[0] * (N + 1) for _ in range(N + 1)]

    dp[0][0] = 0
    for i, ai in enumerate(a):
        for l in range(i+1):
            r = i - l
            dp[i+1][l] = max(dp[i+1][l], dp[i][l] + ai[1] * ((N-1-r) - ai[0]))
            dp[i+1][l+1] = max(dp[i+1][l+1], dp[i][l] + ai[1] * (ai[0] - l))

    print(max(dp[N]))

N = int(input())
A = list(map(int, input().split()))
solve(N,A)
### BUGGY CODE ###

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

import io
import sys
import math

def solve(s,l,r):
    # implement process
    str = s[l-1:r]
    return str.count("AC")

def main():
    # input
    n,q = map(int, input().split())
    s = input()
    
    # process
    ans = ""
    for _ in range(q):
        l,r = map(int, input().split())
        ans += str( solve(s,l,r) ) + "\n"
         
    # output    
    print(ans)
    return ans
        
### DEBUG I/O ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
8 3
ACACTACG
3 7
2 3
1 8
"""
_EXPECTED = """\
2
0
3

"""

def logd(str):
    """usage:
    if _DEB: logd(f"{str}")
    """
    if _DEB: print(f"[deb] {str}")

### MAIN ###
if __name__ == "__main__":
    if _DEB:
        sys.stdin = io.StringIO(_INPUT)
        print("!! Debug Mode !!")

    ans = main()

    if _DEB:
        print()
        if _EXPECTED.strip() == ans.strip(): print("!! Success !!")
        else: print(f"!! Failed... !!\nANSWER:   {ans}\nExpected: {_EXPECTED}")

### FIXED CODE ###

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

import io
import sys
import math

def solve(ac_lst,l,r):
    # implement process
    #l=2,r=3
    if l == 1:
        return ac_lst[r-2]
    return ac_lst[r-2] - ac_lst[l-2]
    

def make_ac_lst(s):
    ac_lst = [0] * len(s)
    for i in range(len(s)-1):
        if i != 0:
            ac_lst[i] += ac_lst[i-1]
        if s[i] == "A" and s[i+1] == "C":
            ac_lst[i] += 1
    ac_lst[-1] = ac_lst[-2]

    if _DEB: logd(f"{ac_lst}")
    return ac_lst

def main():
    # input
    n,q = map(int, input().split())
    s = input()
    
    # process
    ans = ""
    ac_lst = make_ac_lst(s)

    for _ in range(q):
        l,r = map(int, input().split())
        ans += str( solve(ac_lst,l,r) ) + "\n"
         
    # output    
    print(ans)
    return ans
        
### DEBUG I/O ###
_DEB = 0   # 1:ON / 0:OFF

_INPUT = """\
8 3
ACACTAAC
7 8
2 3
1 8
"""
_EXPECTED = """\
2
0
3

"""

def logd(str):
    """usage:
    if _DEB: logd(f"{str}")
    """
    if _DEB: print(f"[deb] {str}")

### MAIN ###
if __name__ == "__main__":
    if _DEB:
        sys.stdin = io.StringIO(_INPUT)
        print("!! Debug Mode !!")

    ans = main()

    if _DEB:
        print()
        if _EXPECTED.strip() == ans.strip(): print("!! Success !!")
        else: print(f"!! Failed... !!\nANSWER:   {ans}\nExpected: {_EXPECTED}")
### BUGGY CODE ###

N=int(input())
A,B=[],[]
for i in range(N):
  a,b=map(int,input().split())
  A.append((a,b,i))
  B.append((b,a,i))
A.sort()
B.sort()
ans=0
inf=float("inf")
eaten=[False]*N
for i in range(N):
  if i%2==0:
    while eaten[A[-1][2]]:
      A.pop()
    while eaten[B[-1][2]]:
      B.pop()
    a1=A[-1][0]
    a2,b1=B[-1][1],B[-1][0]
    if A[-1][2]==B[-1][2]:
      ans+=a1
      eaten[A[-1][2]]=True
    else:
      b2=inf
      if i<N-1:
        while b2>10000000000:
          k=2
          if not eaten[B[-k][2]]:
            b2=B[-k][0]
          else:
            k+=1
      if a1-b1>=a2-b2:
        ans+=a1
        eaten[A[-1][2]]=True
      else:
        ans+=a2
        eaten[B[-1][2]]=True
  else:
    while eaten[A[-1][2]]:
      A.pop()
    while eaten[B[-1][2]]:
      B.pop()
    b1=B[-1][0]
    b2,a1=A[-1][1],A[-1][0]
    if A[-1][2]==B[-1][2]:
      ans-=b1
      eaten[B[-1][2]]=True
    else:
      a2=inf
      if i<N-1:
        while a2>10000000000:
          k=2
          if not eaten[A[-k][2]]:
            a2=A[-k][0]
          else:
            k+=1
      if b1-a1>=b2-a2:
        ans+=b1
        eaten[B[-1][2]]=True
      else:
        ans+=b2
        eaten[A[-1][2]]=True
print(ans)        
        
      
        
        
      

### FIXED CODE ###

N=int(input())
Dinner=[[int(i) for i in input().split()] for i in range(N)]
C=[Dinner[i][0]+Dinner[i][1] for i in range(N)]
C.sort(reverse=True)
ans=0
for i in range(N):
  if i%2==0:
    ans+=C[i]
  ans-=Dinner[i][1]
print(ans)