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

import sys
sys.setrecursionlimit(10**6)

n=int(input())
g=[set() for _ in range(n*(n-1)//2+1)]
visit=[0]*(n*(n-1)//2+1)
d=[0]*(n*(n-1)//2+1)

for i in range(1,n+1):
    last=0
    for j in list(map(int,input().split())):
        mi,ma=(min(i-1,j-1),max(i-1,j-1))
        current=ma*(ma-1)//2+mi+1
        g[last].add(current)
        last=current

def dfs(u):
    if visit[u]==2:
        return d[u]
    
    ans=0
    visit[u]=1
    for v in g[u]:
        if visit[v]==1:
            print(-1)
            exit(0)
        
        d[u]=max(d[u],1+dfs(v))
    
    visit[u]=2
    return d[u]

print(dfs(0))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n=int(input())
g=[set() for _ in range(n*(n-1)//2+1)]
visit=[0]*(n*(n-1)//2+1)
d=[0]*(n*(n-1)//2+1)

for i in range(1,n+1):
    last=0
    for j in list(map(int,input().split())):
        mi,ma=(min(i-1,j-1),max(i-1,j-1))
        current=ma*(ma-1)//2+mi+1
        g[last].add(current)
        last=current

def dfs(u):
    if visit[u]==2:
        return d[u]
    
    ans=0
    visit[u]=1
    for v in g[u]:
        if visit[v]==1:
            print(-1)
            exit(0)
        
        d[u]=max(d[u],1+dfs(v))
    
    visit[u]=2
    return d[u]

print(dfs(0))
### BUGGY CODE ###

class Combination:
    '''MOD上の
    計算量：階乗・逆元テーブルの作成O(N)
    nCkを求めるO(1)'''

    def __init__(self, n, MOD):
        self.fact = [1] * (n + 1)
        for i in range(1, n + 1):
            self.fact[i] = self.fact[i-1] * i % MOD
        self.inv_fact = [pow(self.fact[i], MOD - 2, MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


h, w, n = map(int, input().split())
info = [(1, 1)] + [tuple(map(int, input().split())) for i in range(n)] + [(h, w)]
n += 2
MOD = 10**9 + 7
comb = Combination(w+h+1, MOD)

dp = {}
dp[0] = (0, 1)
def solve(ind):
    if ind in dp:
        return dp[ind]
    i, j = info[ind]
    dp0 = 0
    dp1 = 0
    for ind2 in range(n):
        if ind2 == ind:
            continue
        pi, pj = info[ind2]
        if pi <= i and pj <= j:
            dp0 += comb.combination((i+j)-(pi+pj), i-pi) * solve(ind2)[1]
            dp1 += comb.combination((i+j)-(pi+pj), i-pi) * solve(ind2)[0]
            dp0 %= MOD
            dp1 %= MOD
    dp[ind] = (dp0, dp1)
    return dp[ind]

for i in range(n):
    solve(i)
print((dp[n-1][0] - dp[n-1][1]) % MOD)


### FIXED CODE ###

class Combination:
    def __init__(self, n, MOD):
        self.fact = [1] * (n + 1)
        for i in range(1, n + 1):
            self.fact[i] = self.fact[i-1] * i % MOD
        self.inv_fact = [pow(self.fact[i], MOD - 2, MOD) for i in range(n + 1)]
        self.MOD = MOD

    def factorial(self, k):
        """k!を求める O(1)"""
        return self.fact[k]

    def inverse_factorial(self, k):
        """k!の逆元を求める O(1)"""
        return self.inv_fact[k]

    def permutation(self, k, r):
        """kPrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[r]) % self.MOD

    def combination(self, k, r):
        """kCrを求める O(1)"""
        if k < r:
            return 0
        return (self.fact[k] * self.inv_fact[k - r] * self.inv_fact[r]) % self.MOD


h, w, n = map(int, input().split())
info = [(1, 1)] + [tuple(map(int, input().split())) for i in range(n)] + [(h, w)]
info = sorted(info)
n += 2
MOD = 10**9 + 7
comb = Combination(w+h+1, MOD)

dp = {}
dp[0] = (0, 1)
def solve(ind):
    if ind in dp:
        return dp[ind]
    i, j = info[ind]
    dp0 = 0
    dp1 = 0
    for ind2 in range(n):
        if ind2 == ind:
            continue
        pi, pj = info[ind2]
        if pi <= i and pj <= j:
            tmp = comb.combination((i+j)-(pi+pj), i-pi)
            dp0 += tmp * solve(ind2)[1] % MOD
            dp1 += tmp * solve(ind2)[0] % MOD
    dp[ind] = (dp0, dp1)
    return dp[ind]

for i in range(n):
    solve(i)
print((dp[n-1][0] - dp[n-1][1]) % MOD)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
A_list = list(set(A))
count = 0

for c in A_list:
    C = A.count(c)
    if C >= c:
        count += C - c
    else:
        count += C

print(count)

### FIXED CODE ###

import collections

N = int(input())
a = list(map(int, input().split()))
a_s = collections.Counter(a) 
A = a_s.most_common()
count = 0

for i in range(len(A)):
    if int(A[i][1]) >= int(A[i][0]):
        count += int(A[i][1]) - int(A[i][0])
    else:
        count += int(A[i][1])

print(count)
### BUGGY CODE ###

import collections


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


tmp = collections.Counter(ss).most_common()

target = collections.Counter(ss).most_common()[0][1]
ans = ''
for i in tmp:
    if i[1] == target:
        ans += i[0] + ' '
    else:
        break
ans = sorted(ans.split(), key=str.lower)
print(*ans)


### FIXED CODE ###

import bisect

n = int(input())
sl = ['']*n
for i in range(n):
    sl[i] = input()
sl = sorted(sl, key=str.lower)
# print(sl)
c = 0
anss = []
max_n = 0
for i, t in enumerate(sl):
    if i == 0:
        c += 1
        target = t
        continue

    if t == target:
        c += 1
    else:
        if max_n < c:
            anss = []
            anss.append(target)
            max_n = c
        elif max_n == c:
            anss.append(target)
            max_n = c
        target = t
        c = 1

if max_n < c:
    anss = []
    anss.append(t)
elif max_n == c:
    anss.append(t)


print(*anss)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n = int(input())

Li = [None]*n
for i in range(n):
    s = input()
    if s in Li:
        pass
    else:
        Li[i] = s

Li = [e for e in Li if e is not None]
print(len(Li))


### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())

Li = [input() for _ in range(n)]
Li.sort()
s= Li[0]
c =1
for l in Li[1:]:
    if l == s:
        pass
    else:
        c+=1
        s = l
print(c)
### BUGGY CODE ###

from heapq import heappop, heappush
from collections import deque


def solve():
    N, M = map(int, input().split())
    loadmap = [[] for _ in range(N + 1)]
    for _ in range(M):
        A, B = map(int, input().split())
        loadmap[A].append(B)
        loadmap[B].append(A)

    dbmap = [[float('inf'), -1] for _ in range(N + 1)]  # 部屋の深度, しるべ

    # rooms = [[0, 1, 0]]  # [移動前の部屋, 移動後(現在)の部屋, 深度]
    rooms = deque()
    rooms.append([0, 1, 0])
    while rooms:
        # br, r, d = heappop(rooms)
        br, r, d = rooms.popleft()
        if d <= dbmap[r][0]:
            # update room data
            dbmap[r][0] = d
            dbmap[r][1] = br
            # add new room data
            for l in loadmap[r]:
                # heappush(rooms, [r, l, d + 1])
                rooms.append([r, l, d + 1])

    if min([db[1] for db in dbmap[1:]]) <= -1:
        print('No')
    else:
        print('Yes')
        for db in dbmap[2:]:
            print(db[1])


if __name__ == '__main__':
    solve()


### FIXED CODE ###

from heapq import heappop, heappush
from collections import deque


def solve():
    N, M = map(int, input().split())
    loadmap = [[] for _ in range(N + 1)]
    for _ in range(M):
        A, B = map(int, input().split())
        loadmap[A].append(B)
        loadmap[B].append(A)

    dbrmap = [[float('inf'), -1, 0] for _ in range(N + 1)]  # 部屋の深度, しるべ, 予約状態

    # rooms = [[0, 1, 0]]  # [移動前の部屋, 移動後(現在)の部屋, 深度]
    rooms = deque()
    rooms.append([0, 1, 0])
    dbrmap[1][2] = 1
    while rooms:
        # br, r, d = heappop(rooms)
        br, r, d = rooms.popleft()
        if d <= dbrmap[r][0]:
            # update room data
            dbrmap[r][0] = d
            dbrmap[r][1] = br
            # add new room data
            for load in loadmap[r]:
                # heappush(rooms, [r, l, d + 1])
                if dbrmap[load][2] == 0:
                    rooms.append([r, load, d + 1])
                    dbrmap[load][2] = 1

    if min([db[1] for db in dbrmap[1:]]) <= -1:
        print('No')
    else:
        print('Yes')
        for db in dbrmap[2:]:
            print(db[1])


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

def main():
    H, W, K = map(int, input().split())
    s = []
    for _ in range(H):
        *row, = map(int, input())
        s.append(row)

    ret = H * W
    for bits in range(1 << (H - 1)):
        # 水平カットで生成される2枚目以降の開始行
        # 0行目は確定で, 残りのカットを調べる
        # 次の変換が必要
        # [0,H) -> [1,H]

        group = [0] * H
        for j in range(H - 1):
            group[j + 1] = group[j] + (1 if (bits >> j) & 1 else 0)
        # group = [0,0,1,1,1,2,...]

        ctr = [0] * H
        add_v = [0] * H
        c, pc = 0, -1
        cut = bin(bits).count('1')
        while c < W:
            need_cut = False
            for r in range(H):
                g = group[r]
                add_v[g] += s[r][c]
                if ctr[g] + add_v[g] > K:
                    need_cut = True
                    break

            if need_cut:
                if pc == c:
                    cut = H * W
                    break
                ctr = [0] * H
                add_v = [0] * H
                cut += 1
                pc = c
                if cut >= ret:
                    break
                continue

            for g, _add_v in enumerate(add_v):
                ctr[g] += _add_v
            add_v = [0] * H
            pc = c
            c += 1

        ret = min(ret, cut)

    print(ret)


if __name__ == '__main__':
    main()


### FIXED CODE ###

H, W, K = map(int, input().split())
s = []
for _ in range(H):
    *row, = map(int, input())
    s.append(row)

ret = H * W
for bits in range(1 << (H - 1)):
    # 水平カットで生成される2枚目以降の開始行
    # 0行目は確定で, 残りのカットを調べる
    # 次の変換が必要
    # [0,H) -> [1,H]

    group = [0] * H
    for j in range(H - 1):
        group[j + 1] = group[j] + (1 if (bits >> j) & 1 else 0)
    # group = [0,0,1,1,1,2,...]

    ctr = [0] * H
    add_v = [0] * H
    c, pc = 0, -1
    cut = bin(bits).count('1')
    while c < W:
        need_cut = False
        for r in range(H):
            g = group[r]
            add_v[g] += s[r][c]
            if ctr[g] + add_v[g] > K:
                need_cut = True
                break

        if need_cut:
            if pc == c:
                cut = H * W
                break
            ctr = [0] * H
            add_v = [0] * H
            cut += 1
            pc = c
            if cut >= ret:
                break
            continue

        for g, _add_v in enumerate(add_v):
            ctr[g] += _add_v
        add_v = [0] * H
        pc = c
        c += 1

    ret = min(ret, cut)

print(ret)
### BUGGY CODE ###

import numpy as np
import scipy.sparse
N,X,Y = (int(x) for x in input().split())
lil = scipy.sparse.lil_matrix((N, N))
for i in range(N-1):
    lil[i, i+1] = 1
    lil[i+1, i] = 1
lil[X-1, Y-1] = 1
lil[Y-1, X-1] = 1
lil2 = scipy.sparse.csgraph.dijkstra(lil)
k = [((np.count_nonzero(lil2 == i)) // 2) for i in range(1,N)]
for j in range(N-1):
    print(k[j])

### FIXED CODE ###

import numpy as np
import scipy.sparse
N,X,Y = (int(x) for x in input().split())
lil = scipy.sparse.lil_matrix((N, N), dtype = int)
for i in range(N-1):
    lil[i, i+1] = 1
    lil[i+1, i] = 1
lil[X-1, Y-1] = 1
lil[Y-1, X-1] = 1
lil2 = scipy.sparse.csgraph.dijkstra(lil, directed = False).astype(int)
ans = np.bincount(lil2.ravel(), minlength = N) // 2
for i in range(1,N):
    print(ans[i])
### BUGGY CODE ###

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

lis = []
p=0
while True:
  p = S.find("AC", p)

  if p < 0:
    break

  lis += [p]

  p+=2

for _ in range(Q):
  L = tuple(map(int, input().split()))

  c = 0
  for l in lis:
    if L[0] - 1 <= l < L[1] - 1:
      c+=1
      
  
  print(c)


### FIXED CODE ###

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

lis = [0] * len(S)
for i in range(len(S)):

  if i>0:
    lis[i] += lis[i-1]
  if i < len(S)-1 and S[i] == 'A' and S[i+1] == 'C':
    lis[i+1] += 1


for _ in range(Q):
  L = tuple(map(int, input().split()))

  c = 0
  print(lis[L[1]-1]-lis[L[0]-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = [0]*N
for i in range(N):
    ans[i] = A.index(i+1) +1
print(*ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = {}
for i in range(N):
    ans[i+1] = A[i]
ans = sorted(ans.items(), key=lambda x:x[1])
ans2 = []
for i in ans:
    ans2.append(i[0])
print(*ans2)
### BUGGY CODE ###

X = int(input())
max_n = 1
for i in range(2,X+1):
  for j in range(2,X+1):
    tmp = i**j
    if X >= tmp and max_n < tmp:
      max_n = tmp
print(max_n)

### FIXED CODE ###

X = int(input())
max_n = 1
for i in range(2,32):
  for j in range(2,10):
    tmp = i**j
    if X >= tmp and max_n < tmp:
      max_n = tmp
print(max_n)
### BUGGY CODE ###

N = int( input() )
t_list = list( map( int, input().split() ) )
counter = 0
a = 0
b = 1
for i in t_list:
  a += 1
  b = a
  for j in t_list[a:]:
    b += 1
    for k in t_list[b:]:
      if i < j + k:
        if j < i + k:
          if k < i + j:
            counter += 1
            
print(counter)
          
  


### FIXED CODE ###

from bisect import bisect_left
N = int ( input() )
t_list = list ( map ( int, input().split() ) )
t_list.sort()
ans = 0

for i in range ( N - 2 ):
  a = t_list[i]
  for j in range ( i + 1, N - 1 ):
    b = t_list[j]
    c = bisect_left ( t_list , a + b)
    ans += c - j - 1
    
print(ans)
### BUGGY CODE ###

def main():
    class rolling_hash():
        def __init__(self, sequence, char_list=None):
            self.sequence = sequence  # 文字列
            self.seq_size = len(self.sequence)  # 文字列の長さ
            self.mod = 2**61-1  # mod
            if char_list is None:  # 使われている文字のリスト
                self.char_list = "abcdefghijklmnopqrstuvwxyz"
            else:
                self.char_list = char_list
            self.base = len(self.char_list)+1  # 文字の種類数
            self.char_dict = {j: i+1 for i,
                              j in enumerate(self.char_list)}  # 文字と数値の対応表
            self.Hash_0start = [0]*(self.seq_size+1)  # 先頭からi-1文字目までのハッシュ値
            for i in range(self.seq_size):
                self.Hash_0start[i+1] = self.Hash_0start[i] + \
                    self.char_dict[self.sequence[i]] * \
                    pow(self.base, i, self.mod)

        def calc_hash(self, l, r):  # l文字目からr-1文字目までのハッシュ値
            return ((self.Hash_0start[r] - self.Hash_0start[l])
                    * pow(self.base, l*(self.mod-2), self.mod)) % self.mod

    n = int(input())
    s = input()
    h_s = rolling_hash(s)

    def value(num):
        h_dict = {}
        for i in range(len(s)-num+1):
            j = h_s.calc_hash(i, i+num)
            if j not in h_dict.keys():
                h_dict[j] = i
            else:
                if i-h_dict[j] >= num:
                    return True
        return False

    def b_search(a, b, value):
        while a+1 < b:
            med = (a+b)//2
            if value(med):
                a = med
            else:
                b = med-1
        if a == b:
            return a
        elif a+1 == b:
            if value(b):
                return b
            else:
                return a

    print(b_search(0, len(s), value))


main()


### FIXED CODE ###

def main():
    n=int(input())
    s=input()
    m=0
    for i in range(1,n):
        cnt_m=0
        cnt=0
        for j in range(i,n):
            if s[j-i]==s[j]:
                cnt=min(cnt+1,i)
            else:
                cnt_m=max(cnt,cnt_m)
                cnt=0
        m=max(cnt,cnt_m,m)
    print(m)

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

N = int(input())

CSFs = [list(map(int, input().split(' '))) for i in range(N - 1)]

for i in range(0, N - 1):
    initial_move_time = CSFs[i][0] + CSFs[i][1]

    for j in range(i + 1, N - 1):
        if initial_move_time <= CSFs[j][1]:
            initial_move_time = CSFs[j][1]

        elif initial_move_time % CSFs[j][2] == 0:
            initial_move_time = initial_move_time

        else:
            k = 1
            while True:
                tmp = CSFs[j][1] + CSFs[j][2] * k
                if initial_move_time <= tmp:
                    initial_move_time = tmp
                    break
                k += 1
        initial_move_time += CSFs[j][0]

    print(initial_move_time)
    
print(0)

### FIXED CODE ###

N = int(input())

CSFs = [list(map(int, input().split(' '))) for i in range(N - 1)]

for i in range(0, N - 1):
    initial_move_time = CSFs[i][0] + CSFs[i][1]
    for j in range(i + 1, N - 1):
        if initial_move_time <= CSFs[j][1]:
            initial_move_time = CSFs[j][1]
        elif initial_move_time % CSFs[j][2] == 0:
            initial_move_time = initial_move_time
        else:
            initial_move_time = initial_move_time + CSFs[j][2] - initial_move_time % CSFs[j][2]
        initial_move_time += CSFs[j][0]
    print(initial_move_time)
print(0)
### BUGGY CODE ###

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

s = 1
for i in range(k):
    s *= li[i]

for i in range(k, n):
    t = 1
    for j in range(k):
        t *= li[i+j-k+1]

    if s < t:
        print('Yes')
    else:
        print('No')
        
    s = t


### FIXED CODE ###

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

for i in range(k, n):

    if li[i-k] < li[i]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

N,M = map(int,input().split(' '))
sections_a = []
sections_b = []

for _ in range(M):
    a,b = map(int,input().split(' '))
    sections_a.append(a)
    sections_b.append(b)

tmp_a = [sections_a[0]]
tmp_b = [sections_b[0]]
for i in range(1,len(sections_a)):
    for j in range(i):
        if sections_a[i] < tmp_a[j]:
            tmp_a.insert(j,sections_a[i])
            tmp_b.insert(j,sections_b[i])
            break
        if j == i -1:
            tmp_a.append(sections_a[i])
            tmp_b.append(sections_b[i])
min_end = 10000000000000000
sorted_list_a = tmp_a
sorted_list_b = tmp_b
cnt = 0
for i in range(len(sorted_list_a)):
    if min_end <= sorted_list_a[i]:
        cnt += 1
        min_end = 10000000000000000
    min_end = min(min_end,sorted_list_b[i])
cnt += 1
print(cnt)

### FIXED CODE ###

N,M = map(int,input().split(' '))
sections = [list(map(int,input().split(' '))) for _ in range(M) ]

'''
tmp_list = [sections[0]]
for i in range(1,len(sections)):
    for j in range(i):
        if sections[i] < tmp_list[j]:
            tmp_list.insert(j,sections[i])
            break
        if j == i -1:
            tmp_list.append(sections[i])
'''
min_end = 10000000000000000
sorted_list = sorted(sections)
cnt = 0
for section in sorted_list:
    if min_end <= section[0]:
        cnt += 1
        min_end = min_end = 10000000000000000
    min_end = min(min_end,section[1])
cnt += 1
print(cnt)
### BUGGY CODE ###

from collections import deque
import sys
input=sys.stdin.readline


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    candidate = [(i, j, 0) for i in range(H) for j, s in enumerate(input()) if s=="#"]
    q = deque(candidate)
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]

    while q:
        y, x, cost = q.popleft()
        m[y][x] = cost

        for i in range(4):
            x1, y1 = x + dx[i], y + dy[i]
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1, cost+1))

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()


### FIXED CODE ###

from collections import deque


def solve():
    H, W = map(int, input().split())
    m = [[-1]*W for _ in range(H)]
    l = [list(input()) for _ in range(H)]
    dx = [-1, 1, 0, 0]
    dy = [0, 0, -1, 1]
    q = deque([])

    for i in range(H):
        for j in range(W):
            if l[i][j]=="#":
                q.append((i, j))
                m[i][j] = 0
    
    while q:
        y, x = q.popleft()

        for px, py in zip(dx, dy):
            x1, y1 = x + px, y + py
            if not (0<=x1<W and 0<=y1<H):
                continue
            if m[y1][x1] == -1:
                q.append((y1, x1))
                m[y1][x1] = m[y][x] + 1

    print(max(map(max, m)))


if __name__ == "__main__":
    solve()
### BUGGY CODE ###

import math

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

for i in range(N):
  for j in range(i,N):
    if A[i]+A[j]==abs(j-i):
      c+=1
print(c)

### FIXED CODE ###

n=int(input())
A=list(map(int, input().split()))
d={}
c=0

for i,a in enumerate(A):
  if i+a not in d:
    d[i+a]=1
  else:
    d[i+a]+=1
  if i-a in d:
    c+=d[i-a]

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

N, M=map(int,input().split())
H=list(map(int,input().split()))
A=[0]*M
B=[0]*M
for i in range(M):
  A[i], B[i]=map(int,input().split())
answer=0
for i in range(N):
  X=[H[i]]
  for j in range(M):
    if (i+1)== A[j]:
      X.append(H[B[j]-1])
    elif (i+1)==B[j]:
      X.append(H[A[j]-1])

  if H[i]==max(X) and X.count(max(X))==1:
    answer+=1
print(answer)

### FIXED CODE ###

N, M=map(int,input().split())
H=list(map(int,input().split()))
ans=[1]*N
for i in range(M):
  A, B=map(int,input().split())
  x=H[A-1]
  y=H[B-1]
  if x>y:
    ans[B-1]=0
  elif x==y:
    ans[B-1]=0
    ans[A-1]=0
  elif y>x:
    ans[A-1]=0   
print(sum(ans))
### BUGGY CODE ###

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, q = read_line(int, int)
s, = read_line(str)

p = []
i = 0
while i < len(s) - 1:
    if s[i:i+2] == 'AC':
        p.append(i)
        i += 2
    else:
        i += 1

for i in range(q):
    l, r = read_line(int, int)
    l, r = l - 1, r - 1

    if len(p) == 0:
        print(0)
        continue

    c = 0
    for j in range(len(p)):
        pp = p[j]
        if l <= pp:
            break
        c += 1

    for jj in reversed(range(j, len(p))):
        pp = p[jj]
        if pp + 1 <= r:
            break
        c += 1

    print(len(p) - c)


### FIXED CODE ###

def read_line(*types): return [f(a) for a, f in zip(input().split(), types)]

n, q = read_line(int, int)
s, = read_line(str)

m = [0 for _ in range(len(s) + 1)]

c = 0
for i in range(len(s)):
    if s[i:i+2] == 'AC':
        c += 1
    m[i + 1] = c

for i in range(q):
    l, r = read_line(int, int)

    if c == 0:
        print(0)
        continue
    print(m[r - 1] - m[l - 1])
### BUGGY CODE ###

s = str(input())
n = len(s)
count = 0
for i in range(1,n-2):
    for k in range(3,n+1):
        j = i+k
        if (j<=n):
            st = int(s[i-1:j])
            if int(st)%2019==0:
                count +=1
print(count)

### FIXED CODE ###

s = input()[::-1] # 入力文字列を逆順でsに格納

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

print(ans) # 答えの出力
### BUGGY CODE ###

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

cakes = []
for _ in range(N):
    cakes.append(list(map(int, input().split())))

memo = dict()

def pick_cake(picked):
    key = ','.join([str(p) for p in sorted(picked)])
    if key in memo:
        return memo[key]

    if len(picked) == M:
        memo[key] = sum([abs(sum([cakes[i][j] for i in picked])) for j in range(3)])
        return memo[key]

    answer = 0
    for i in range(N):
        if i in picked:
            continue
        answer = max(answer, pick_cake(picked + [i]))

    memo[key] = answer
    return answer

print(pick_cake([]))

### FIXED CODE ###

from itertools import product

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

cakes = []
for _ in range(N):
    cakes.append(list(map(int, input().split())))

def _eval1(op):
    def _eval2(x):
        return eval(''.join(['{}{}'.format(op[i], x[i]) for i in range(3)]))

    return _eval2

answer = 0
for op in product('+-', repeat=3):
    answer = max(answer, sum([abs(sum([cake[j] for cake in sorted(cakes, key=_eval1(op))[:M]])) for j in range(3)]))

print(answer)