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

def bisearch(li,target):
    l=0
    r=len(li)-1
    while(l<=r):        
        m=int((l+r)/2)
        if(m==len(li)-1):
            return target-li[m][0]+li[m][1]
        if(li[m][0]<target and target<li[m+1][0]):
            return min(target-li[m][0]+li[m][1],li[m+1][0]-target+li[m+1][1])
        if(m==0 and target<li[0][0]):
            return li[0][0]-target+li[0][1]
        if(target<li[m][0]):
            r = m-1
        else:
            l = m+1

inf = 10**15
A,B,Q = [int(x) for x in input().split()]
s = [0]*(A+1)
t = [0]*(B+1)
x = [0]*Q

for i in range(A):
    s[i] = int(input())
for i in range(B):
    t[i] = int(input())
for i in range(Q):
    x[i] = int(input())
s[-1] = inf
t[-1] = inf

li = []
a = b = 0
while(a<A or b<B):
    if(s[a]<t[b]):
        li.append([s[a],min(abs(t[b]-s[a]),abs(t[b-1]-s[a]))])
        a+=1
    else:
        li.append([t[b],min(abs(t[b]-s[a]),abs(t[b]-s[a-1]))])
        b+=1

for i in x:
    print(bisearch(li,i))


### FIXED CODE ###

def bisearch(li,target):
    l=0
    r=len(li)-1
    while(l<=r):        
        m=int((l+r)/2)
        if(m==len(li)-1):
            return target-li[m][0]+li[m][1]
        if(li[m][0]<target and target<li[m+1][0]):
            return min(target-li[m][0]+li[m][1],li[m+1][0]-target+li[m+1][1])
        if(m==0 and target<li[0][0]):
            return li[0][0]-target+li[0][1]
        if(target<li[m][0]):
            r = m-1
        else:
            l = m+1

inf = 10**15
A,B,Q = [int(x) for x in input().split()]
s = [0]*(A+1)
t = [0]*(B+1)
x = [0]*Q

for i in range(A):
    s[i] = int(input())
for i in range(B):
    t[i] = int(input())
for i in range(Q):
    x[i] = int(input())
s[-1] = inf
t[-1] = inf

li = []
a = b = 0
while(a<A or b<B):
    if(s[a]<t[b]):
        li.append([s[a],min(abs(t[b]-s[a]),abs(t[b-1]-s[a]))])
        a+=1
    else:
        li.append([t[b],min(abs(t[b]-s[a]),abs(t[b]-s[a-1]))])
        b+=1

for i in x:
    print(bisearch(li,i))
### BUGGY CODE ###

a, b, n= [int(i) for i in input().split()]

ans = 0

for i in range(min(n, b-1), 0, -1):
  ans = max(ans, int((a*i)/b))
  if int((a*i)/b) < ans:
    break
  
print(ans)

### FIXED CODE ###

a, b, n= [int(i) for i in input().split()]

if int(n/b) == 0:
  print(int((a*n)/b))
else:
  print(int((a*(b-1))/b))
### BUGGY CODE ###

N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
import time
time.sleep(1.5)
print(ans)


### FIXED CODE ###

N,M=map(int, input().split())
G=[list() for i in range(N)]
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    G[a].append(b)
    G[b].append(a)
ans=0
index=-1
for i in range(1,N):
    for p in G[i]:
        if index<p<i:
            ans+=1
            index=i-1
print(ans)
### BUGGY CODE ###

S = input()
MOD = 10 ** 9 + 7
N = len(S)

def check(n):
  for i in range(N):
    if S[i] != "?":
      d = 10 ** (N - i - 1)
      c = (n // d) % 10
      if c != int(S[i]):
        return False
  return True

num_max = 0
for i in range(N):
  num_max *= 10
  if S[i] != "?":
    num_max += int(S[i])
  else:
    num_max += 9

ans = 0
num = 5
while num <= num_max:
  if check(num):
    ans += 1
  num += 13
print(ans % MOD)

### FIXED CODE ###

S = input()
MOD = 10 ** 9 + 7
N = 13
dp = [0 for _ in range(N)]
dp[0] = 1

mul = 1
for i in range(len(S)):
  c = S[len(S) - i - 1]
  nextDP = [0 for _ in range(N)]

  if c == "?":
    for k in range(10):
      for j in range(N):
        nextDP[(k * mul + j) % N] += dp[j]
        nextDP[(k * mul + j) % N] %= MOD
  else:
    k = int(c)
    for j in range(N):
      nextDP[(k * mul + j) % N] += dp[j]
      nextDP[(k * mul + j) % N] %= MOD

  mul *= 10
  mul %= N
  dp = nextDP
print(dp[5])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
import copy
import collections
from bisect import bisect_left
from bisect import bisect_right
from collections import defaultdict
from heapq import heappop, heappush
import numpy as np
import statistics
from statistics import mean, median,variance,stdev
import math

def main():
	N, K = map(int, input().split(" "))
	A = input().split(" ")
	A = [int(s) for s in A]
	
	DP = [100000000000000000000000000000000 for _ in range(N)]
	DP[0] = 0
	
	for i, val in enumerate(A):
		if i == 0:
			continue
		tmp = 100000000000000000000000000000000
		
		for j in range(K):
			index = j+1
			if i >= index:
				tmp1 = DP[i-index] + abs(A[i-index] - val)
				tmp = min(tmp, tmp1)
			else:
				break
		DP[i] = min(DP[i], tmp)
		
	#print(DP)
	print(DP[N-1])
	
	
if __name__ == "__main__":
	main()


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

def main():
	N, K = map(int, input().split(" "))
	H = input().split(" ")
	H = [int(s) for s in H]
	
	DP = [-1 for _ in range(N)]
	DP[0] = 0
	
	for i in range(1, len(H)):
		paths = [DP[j] + abs(H[j] - H[i]) for j in range(max(0, i-K), i)]
		DP[i] = min(paths)
		
	print(DP[N-1])
		
if __name__ == "__main__":
	main()
### BUGGY CODE ###

a=int(input())
List = list(map(int, input().split()))
res =1
for i in range(a):
  res = res *List[i]
if res > 1000000000000000000:
  res = -1
print(res)

### FIXED CODE ###

a=int(input())
List = list(map(int, input().split()))
res =1
List.sort()
for i in range(a):
  res = res *List[i]
  if res > 1000000000000000000:
    res = -1
    break
  elif res == 0:
    break
  else:
    pass
print(res)
### BUGGY CODE ###

from functools import reduce
from math import gcd


k = int(input())
l = range(1, k+1)
s = 0

for a in l:
    for b in l:
        for c in l:
            t = [a, b, c]
            g = reduce(gcd, t)
            s += g
            
print(s)

### FIXED CODE ###

from math import gcd

k = int(input())
range(1, k+1)

l1 = range(1, k+1)
def loop(s):
    for a in l1:
        for b in l1:
            for c in l1:
                l2 = (a, b, c)
                g1 = gcd(a,b)
                g2 = gcd(g1, c)
                s += g2
    return s

print(loop(0))
### BUGGY CODE ###

def solve():
    import numpy as np
    import sys

    input = sys.stdin.readline

    h, w = map(int, input().split())
    d = [list(map(int, input().split())) for _ in range(h * 2)]
    for r in range(h):
        for c in range(w):
            d[r][c] = abs(d[r][c] - d[r + h][c])

    MaxBias = 80 * (h + w)

    dp = np.zeros(shape=(h, w, MaxBias + 1))
    dp[0, 0, d[0][0]] = 1

    for r in range(1, h):
        for bias in range(MaxBias + 1):
            if dp[r - 1, 0, bias]:
                for new_bias in abs(bias + d[r][0]), abs(bias - d[r][0]):
                    if 0 <= new_bias <= MaxBias:
                        dp[r, 0, new_bias] = 1

    for c in range(1, w):
        for bias in range(MaxBias + 1):
            if dp[0, c - 1, bias]:
                for new_bias in abs(bias + d[0][c]), abs(bias - d[0][c]):
                    if 0 <= new_bias <= MaxBias:
                        dp[0, c, new_bias] = 1

    for r in range(1, h):
        for c in range(1, w):
            for bias in range(MaxBias + 1):
                if dp[r - 1, c, bias] or dp[r, c - 1, bias]:
                    for new_bias in abs(bias + d[r][c]), abs(bias - d[r][c]):
                        if 0 <= new_bias <= MaxBias:
                            dp[r, c, new_bias] = 1

    for bias in range(MaxBias + 1):
        if dp[h - 1, w - 1, bias]:
            print(bias)
            return


if __name__ == '__main__':
    solve()


### FIXED CODE ###

# https://atcoder.jp/contests/abc147/submissions/8871745
# 写経
# bitset 高速化

def main():
    import numpy as np

    H, W = map(int, input().split())
    A = np.array([[int(x) for x in input().split()] for _ in range(H)])
    B = np.array([[int(x) for x in input().split()] for _ in range(H)])
    D = np.abs(A - B)

    MAX_BIAS_PER_CELL = 80
    UPPER_BOUND_TOTAL_BIAS = MAX_BIAS_PER_CELL * (H + W - 1) + 1

    dp = [[0] * W for _ in range(H)]
    dp[0][0] = 1 << UPPER_BOUND_TOTAL_BIAS
    # dp[r][c]:(r,c)で値の加減を行った後、
    # 達成可能なbiasに該当するbitを立てたbit表現
    # 2**UPPER_BOUND_TOTAL_BIASの位をbias=0とみなす

    # -UPPER_BOUND_TOTAL_BIAS, ..., 0, ...UPPER_BOUND_TOTAL_BIAS [意味するbias]
    # 0, ..., UPPER_BOUND_TOTAL_BIAS, ..., UPPER_BOUND_TOTAL_BIAS*2 [dpに代入されるbit表現の桁]

    # numpyのndarrayを使用しなかった理由
    # dtypeでuint64を採用しても、
    # 2**(UPPER_BOUND_TOTAL_BIAS*2)は収まらない
    # pythonのintなら収まる

    for r in range(H):
        for c in range(W):
            x = dp[r][c]
            if r > 0:
                x |= dp[r - 1][c]
            if c > 0:
                x |= dp[r][c - 1]
            # x:(r,c)到達可能なbiasのbit表現

            d = D[r][c]
            dp[r][c] = (x << d) | (x >> d)
            # (r,c)マスでのbias変化を加味したbit表現

    ret = min(
        abs(UPPER_BOUND_TOTAL_BIAS - shift)
        for shift in range(UPPER_BOUND_TOTAL_BIAS * 2)
        if (dp[H - 1][W - 1] & (1 << shift)) > 0)

    print(ret)


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

import itertools
n,k = map(int,input().split())
if k%2!=0:
  ans = len(list(itertools.product(range(1,n//k+1),repeat=3)))
  print(ans)
else:
  ans = len(list(itertools.product(range(1,n//k+1),repeat=3))) + len(list(itertools.product(range(1,(2*n)//k-n//k+1),repeat=3)))
  print(ans)

### FIXED CODE ###

import itertools
n,k = map(int,input().split())
if k%2!=0:
  ans = (n//k)**3
  print(ans)
else:
  ans = (n//k)**3 + ((2*n)//k - n//k)**3
  print(ans)
### BUGGY CODE ###

N, Q = map(int, input().split())
S = input()
lst = []
idx = 0
for x in range(len(S) - 1):
    if S[x] == 'A' and S[x + 1] == 'C':
        lst.append(1)
    else:
        lst.append(0)

for x in range(Q):
    a, b = map(int, input().split())
    print(sum(lst[a-1:b-1]))

### FIXED CODE ###

from itertools import accumulate

N, Q = map(int, input().split())
S = input()
lst = [0]
idx = 0
for x in range(len(S) - 1):
    if S[x] == 'A' and S[x + 1] == 'C':
        lst.append(1)
    else:
        lst.append(0)

lst2 = list(accumulate(lst))
for x in range(Q):
    a, b = map(int, input().split())
    print(lst2[b-1] - lst2[a-1])
### BUGGY CODE ###

import sys
from collections import defaultdict
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# S = input().strip

x = 0
y = N

p = [None] * N
print(x)
p[x] = input().strip()

for _ in range(20):
    m = (x + y) // 2
    print(m)

    s = input().strip()
    if s == "Vacant":
        exit()
    else:
        if p[x] == s:
            if (m - x) % 2 == 0:
                x = m
                p[x] = s
            else:
                y = m
                p[y] = s
        else:
            if (m - x) % 2 == 0:
                y = m
                p[y] = s
            else:
                x = m
                p[x] = s

### FIXED CODE ###

import sys
from collections import defaultdict
from heapq import *
sys.setrecursionlimit(200000)
input = sys.stdin.readline

# N, M, = map(int, input().split())
N = int(input())
# L = [int(v) for v in input().split()]
# L = [[int(v) for v in input().split()] for _ in range(N)]
# L = [int(input()) for _ in range(N)]
# S = input().strip

x = 0
y = N

p = [None] * N
print(x, flush = True)
p[x] = input().strip()

for _ in range(20):
    m = (x + y) // 2
    print(m, flush = True)

    s = input().strip()
    if s == "Vacant":
        exit()
    else:
        if p[x] == s:
            if (m - x) % 2 == 0:
                x = m
                p[x] = s
            else:
                y = m
                p[y] = s
        else:
            if (m - x) % 2 == 0:
                y = m
                p[y] = s
            else:
                x = m
                p[x] = s
### BUGGY CODE ###

#!/usr/bin/env python

l = []
n = int(input())
for i in range(n):
    s = input()
    l.append(s)

l_s = []
for i in range(n):
    l_s.append(sorted(l[i]))

c = 0
for i in range(len(l_s)):
    for j in range(i+1, len(l_s)):
        if l_s[i] == l_s[j]:
            c += 1
print(c)

### FIXED CODE ###

#!/usr/bin/env python
import math

l_s = set()
c = 0
n = int(input())
dup = {}

for i in range(n):
    st = sorted(input())
    s  = "".join(st)
    if s in l_s:
        if s in dup.keys():
            dup[s] += 1
        else:
            dup[s] = 1
        c += dup[s]
    l_s.add(s)

print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
S = []
s = list(input().rstrip())
K = int(input())
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        if s[i:j] not in S:
            S.append(s[i:j])
S.sort()
print("".join(S[K-1]))


### FIXED CODE ###

import sys
input = sys.stdin.readline
S = set()
s = list(input().rstrip())
K = int(input())
for i in range(len(s)):
    for j in range(i+1, i+K+1):
        if "".join(s[i:j]) not in S:
            S.add("".join(s[i:j]))
S = list(S)
S.sort()
print("".join(S[K-1]))
### BUGGY CODE ###

s = input()
cnt = 0
for i in range(1,len(s)):
    if s[i-1] == s[i]:
        new = (int(s[i])+1)%2
        s_li = list(s)
        s_li[i] = str(new)
        s = ''.join(s_li)
        cnt += 1
        
print(cnt)
    

### FIXED CODE ###

s = input()
cnt = 0
for i in range(1,len(s)):
    if s[i-1] == s[i]:
        new = (int(s[i])+1)%2
        """
        s_li = list(s)
        s_li[i] = str(new)
        s = ''.join(s_li)
        """
        s = s[:i] + str(new) + s[i+1:]
        cnt += 1
        
print(cnt)
### BUGGY CODE ###

import numpy as np
N,W = map(int,input().split())
wv = [map(int,input().split()) for _ in range(N)]
w,v = [list(i) for i in zip(*wv)]
max_v,max_w = 0,0
for i,j in zip(w,v):
    max_w += i
    max_v += j
dp = [[float("inf")]*(max_v+1) for _ in range(N+1)]
dp[0][0] = 0#初期値
for i in range(1,N+1):
    for j in range(max_v+1):
        if j - v[i-1] >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1])
        else:
            dp[i][j] = dp[i-1][j]
for i in range(1,max_v+2):
    if W >= dp[N][-i]:
        print(max_v+1-i)
        break

### FIXED CODE ###

N,W = map(int,input().split())
wv = [map(int,input().split()) for _ in range(N)]
w,v = [list(i) for i in zip(*wv)]
max_v,max_w = 0,0
for i,j in zip(w,v):
    max_w += i
    max_v += j
dp = [[float("inf")]*(max_v+1) for _ in range(N+1)]
dp[0][0] = 0#初期値
for i in range(1,N+1):
    for j in range(max_v+1):
        if j - v[i-1] >= 0:
            dp[i][j] = min(dp[i-1][j],dp[i-1][j-v[i-1]]+w[i-1])
        else:
            dp[i][j] = dp[i-1][j]
for i in range(1,max_v+2):
    if W >= dp[N][-i]:
        print(max_v+1-i)
        break
### BUGGY CODE ###

n,c = [int(i) for i in input().split()]
d = []
for i in range(c):
    d.append(list(map(int, input().split())))
color = []
for i in range(n):
    color.append(list(map(int, input().split())))
wrongfeeling = [[0 for i in range(3)] for j in range(c)]
for a in range(c):
    for l in range(n):
        for row in range(n):
            wrongfeeling[a][(l+row)%3] += d[color[row][l]-1][a]
D = wrongfeeling[0][0]+wrongfeeling[1][1]+wrongfeeling[2][2]
for c0 in range (c):
    for c1 in range (c):
        if c1 == c0:
            continue
        for c2 in range (c):
            if c2 == c1 or c2 == c0:
                continue
            D = min(D,wrongfeeling[c0][0]+wrongfeeling[c1][1]+wrongfeeling[c2][2])
print(D)

### FIXED CODE ###

n,c = [int(i) for i in input().split()]
d = [[int(i) for i in input().split()]for i in range(c)]
#d[A][B] はAからBになるときの違和感
color = [[int(i) for i in input().split()]for i in range(n)]

devcol = [[0 for i in range(3)] for j in range(c)]
for l in range(n):
        for row in range(n):
            devcol[color[l][row]-1][(l+row)%3] += 1
Dsum = [[0 for i in range(3)] for j in range(c)]
for i in range(c):
    for j in range(c):
        for k in range(3):
            Dsum[i][k] += d[j][i]*devcol[j][k] 
D = Dsum[0][0]+Dsum[1][1]+Dsum[2][2]
for c0 in range (c):
    for c1 in range (c):
        if c1 == c0:
            continue
        for c2 in range (c):
            if c2 == c1 or c2 == c0:
                continue
            D = min(D,Dsum[c0][0]+Dsum[c1][1]+Dsum[c2][2])
#O(c^3)のつもり
print(D)
### BUGGY CODE ###

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

n = int(input())
l = sorted(list(map(int, input().split(' '))), reverse = True)

ans = 0
for ai in range(len(l)-2):
    a = l[ai]
    for bj in range(ai+1, len(l)-1):
        b = l[bj]
        for ck in range(bj+1, len(l)):
            c = l[ck]
            if a < b+c:
                ans += 1
            else:
                break

print(ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
from bisect import bisect_left

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):
        t = l[i]+l[j]
        idx = bisect_left(l, t)
        ans += max(0, idx-j-1)

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

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

X = []
for i in range(A,B+1):
    X.append(bin(i)[2:].zfill(40))

ans = ''
for i in range(40):
    tmp = 0
    for x in X:
        tmp += int(x[i])
    if tmp%2 == 0:
        ans += '0'
    else:
        ans += '1'

print(int(ans,2))

### FIXED CODE ###

def count(X,n):
    l = []
    for i in range(n):
        l.append((X+1)//(2**(i+1))*2**i + max(0,(X+1)%(2**(i+1))-2**i))
    return l

A,B = map(int,input().split())
n = len(bin(B)[2:])
la = count(A-1,n)
lb = count(B,n)

xor = ''
for a,b in zip(la[::-1],lb[::-1]):
    if (b-a)%2 == 0:
        xor += '0'
    else:
        xor += '1'

print(int(xor,2))
### BUGGY CODE ###

def solve(Card):
  if len(Card)==1: return 0
  X = []
  for i in range(len(Card)-1):
    A = Card[:]
    tmp = A[i]+A[i+1]
    cost = reduce(lambda a,b: a*b, tmp)
    tmp[1:3] = []
    A[i:i+2] = [tmp]
    X.append(cost+solve(A))
  return min(X)
    
n = int(raw_input())
Card = [map(int,raw_input().split()) for _ in [0]*n]
print solve(Card)

### FIXED CODE ###

n = int(raw_input())
C = [[] for _ in [0]*n]
W = {}
for i in range(n):
  C[i] = map(int, raw_input().split())
  W[(i, i)] = 0
for i in range(1, n):
  for j in range(0, n-i):
    a = j+i
    W[(j, a)] = min([C[j][0] * C[k][1] * C[k+1][0] * C[a][1] + W[(j, k)] + W[(k+1, a)] for k in range(j, a)])
print W[0, n-1]
### BUGGY CODE ###

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

l = list(itertools.combinations(a,2))
ans = 0
for i in l:
    ans += i[0]*i[1]
print(ans%(10**9 + 7))

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
ans = 0
total = 0
for i in range(N):
    if i != 0:
        total += a[i-1]
        ans += a[i]*total
print(ans%(10**9 + 7))
### BUGGY CODE ###

def solve(ls) -> int:
  n = len(ls)
  assert(3 <= n <= 2 * 10**3)

  ret = 0

  ia, ib, ic = (0, 1, 2)
  need_adjust = False
  while True:
    if need_adjust or ic == n:
      ib, ic = (ib + 1, ib + 2)
      if ic == n:
        ia, ib, ic = (ia + 1, ia + 2, ia + 3)
      # index check
      if ic == n:
        break
      need_adjust = False

    a, b, c = (ls[ia], ls[ib], ls[ic])
    if a < b + c and b < c + a and c < a + b:
      ret += 1
    elif c >= a + b:
      need_adjust = True

    ic = ic + 1

  return ret


n = int(input().strip())
ls = [int(l) for l in input().split()]

print(solve(sorted(ls)))


### FIXED CODE ###

import bisect


def solve(ls) -> int:
  n = len(ls)
  assert(3 <= n <= 2 * 10**3)

  def n_possible_cs(a: int, b: int, first_ic: int) -> int:
    # def bin_search_le_rightmost(s: int, e: int, target: int):
    #   if s == e:
    #     if ls[s] > target:
    #       return None
    #     else:
    #       return s
    #
    #   mid = s + (e - s) // 2
    #
    #   if ls[mid] <= target and (mid + 1 < n and ls[mid + 1] > target):
    #     return mid
    #   elif ls[mid] <= target:
    #     return bin_search_le_rightmost(mid + 1, e, target)
    #   else:
    #     return bin_search_le_rightmost(s, mid, target)

    idx = bisect.bisect_left(ls, a + b, first_ic)
    return 0 if idx == first_ic else idx - first_ic

  ret = 0
  for ia in range(0, n - 2):
    for ib in range(ia + 1, n - 1):
      a, b = (ls[ia], ls[ib])
      x = n_possible_cs(a, b, ib + 1)
      ret += x
  return ret


n = int(input().strip())
ls = [int(l) for l in input().split()]

print(solve(sorted(ls)))
### BUGGY CODE ###

import bisect

N = int(input())
parts = [[] for i in range(3)]
con = [0] * N

ans = 0

for i in range(3):
  t = sorted(list(map(int,input().split())))
  parts[i] = t

under =parts[2]
middle = parts[1]
upper = parts[0]

for i in range(N):
  p = middle[i]
  q = bisect.bisect_left(upper,p)
  con[i] += q

for i in range(N):
  p = under[i]
  q = bisect.bisect_left(middle,p)
  for j in range(0,q):
    ans += con[j]
    
print(ans)

### FIXED CODE ###

import bisect

N = int(input())
parts = [[] for i in range(3)]
con = [0] * N

ans = 0

for i in range(3):
  t = sorted(list(map(int,input().split())))
  parts[i] = t

under =parts[2]
middle = parts[1]
upper = parts[0]

for i in range(N):
  p = middle[i]
  ans += bisect.bisect_left(upper,p) * (N - bisect.bisect_right(under,p))
    
print(ans)
### BUGGY CODE ###

n=int(input())
if n==1:
    print("0")
    exit()
l=[list(map(int,input().split())) for _ in range(n-1)]
for i in range(n):
    t=0
    k=i
    while k<n-1:
        if l[k][1]>t:
            t=l[k][0]+l[k][1]
            k+=1
            continue
        elif t%l[k][2]==0:
            t+=l[k][0]
            k+=1
            continue
        else:t+=1
    print(t)

### FIXED CODE ###

n=int(input())
if n==1:
    print("0")
    exit()
l=[list(map(int,input().split())) for _ in range(n-1)]
for i in range(n):
    t=0
    k=i
    while k<n-1:
        if l[k][1]>t:
            t=l[k][0]+l[k][1]
            k+=1
            continue
        elif t%l[k][2]==0:
            t+=l[k][0]
            k+=1
            continue
        else:t+=l[k][2]-t%l[k][2]
    print(t)
### BUGGY CODE ###

def main():
    n, c = map(int, input().split())
    d = [list(map(int, input().split())) for i in range(c)]
    grid = [list(map(int, input().split())) for i in range(n)]

    group = [[0 for i in range(c)], [0 for i in range(c)], [0 for i in range(c)]]
    for i in range(n):
        for j in range(n):
            for color in range(c):
                group[(i+j) % 3][color] += d[grid[i][j]-1][color]

    min_cost = 1 << 30
    for i in range(c):
        for j in range(c):
            if i != j:
                for k in range(c):
                    if j != k and k != i:
                        min_cost = min(group[0][i]+group[1][j]+group[2][k], min_cost)

    print(min_cost)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, c = map(int, input().split())
    d = [list(map(int, input().split())) for i in range(c)]
    grid = [list(map(int, input().split())) for i in range(n)]

    group = [[0 for i in range(c)], [0 for i in range(c)], [0 for i in range(c)]]
    for i in range(n):
        for j in range(n):
            group[(i+j) % 3][grid[i][j]-1] += 1

    min_cost = 1 << 30
    for i in range(c):
        for j in range(c):
            if i != j:
                for k in range(c):
                    if j != k and k != i:
                        cost = 0
                        for color in range(c):
                            cost += group[0][color] * d[color][i]
                            cost += group[1][color] * d[color][j]
                            cost += group[2][color] * d[color][k]

                        min_cost = min(cost, min_cost)

    print(min_cost)


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

def count_AC(s):
  ans=0
  for i in range(len(s)):
    if s[i:i+2]=="AC":ans+=1
  return ans
n,q=map(int,input().split())
s=input()
for i in range(q):
  a,b=map(int,input().split())
  print(count_AC(s[a-1:b]))

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
count=[0]
for i in range(n-1):count.append(count[i]+(s[i:i+2]=="AC"))
for i in range(q):
  a,b=map(int,input().split())
  print(count[b-1]-count[a-1])