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

card_num, gate_num = map(int, input().split())

s, t = map(int, input().split())
all_set = set(range(s, t+1))
for _ in range(gate_num-1):
    s, t = map(int, input().split())
    all_set = all_set.intersection(set(range(s, t+1)))

print(len(all_set))


### FIXED CODE ###

card_num, gate_num = map(int, input().split())

ans_start, ans_end = map(int, input().split())
for _ in range(gate_num-1):
    s, e = map(int, input().split())
    if e < ans_start or ans_end < s:
        print(0)
        exit()
    elif s < ans_start and ans_start < e < ans_end:
        ans_end = e
    elif ans_start < s < ans_end and ans_end < e:
        ans_start = s
    elif ans_start == e:
        ans_end = e
    elif ans_end == s:
        ans_start = s

print(ans_end - ans_start + 1)
### BUGGY CODE ###

#!/usr/bin/env python3

N, W = list(map(int, input().split()))
item_list = []

for _ in range(N):
    w, v = list(map(int, input().split()))
    item_list.append((w, v))

max_v = (10 ** 3) * 100
dp_table = [[0] + [float("inf")] * (max_v + 1) for _ in range(N + 1)]
total_v = 0

for i in range(1, N + 1):
    w, v = item_list[i - 1]
    # 品物iまで考慮したときの価値の最大値
    total_v += v
    for j in range(total_v + 1):
        # 品物iを入れない場合
        dp_table[i][j] = dp_table[i - 1][j]
        before_min_weight = dp_table[i - 1][j]
        # dp_table[i][j] = before_min_weight
        # 品物iを入れる場合
        if j - v < 0:
            continue
        weight = dp_table[i - 1][j - v] + w
        min_weight = min(before_min_weight, weight)
        dp_table[i][j] = min_weight

        # if min_weight <= W:
        #     dp_table[i][j] = min_weight
        #     # max_value = j
max_value = 0
for i, w in enumerate(dp_table[-1]):
    if w <= W:
        max_value = i
ans = max_value
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3

N, W = list(map(int, input().split()))
item_list = []

for _ in range(N):
    w, v = list(map(int, input().split()))
    item_list.append((w, v))

max_v = (10 ** 3) * 100
dp_table = [[0] + [float("inf")] * (max_v + 1) for _ in range(N + 1)]
total_v = 0

for i in range(1, N + 1):  # 最大で10**2
    w, v = item_list[i - 1]
    # 品物iまで考慮したときの価値の最大値
    total_v += v
    for j in range(total_v + 1):  # 最大で10 ** 5
        # 品物iを入れない場合
        dp_table[i][j] = dp_table[i - 1][j]
        before_min_weight = dp_table[i - 1][j]
        # dp_table[i][j] = before_min_weight
        # 品物iを入れる場合
        if j - v < 0:
            continue
        weight = dp_table[i - 1][j - v] + w
        min_weight = min(before_min_weight, weight)
        dp_table[i][j] = min_weight
        if i == N:
            if min_weight <= W:
                max_value = j

ans = max_value
print(ans)
### BUGGY CODE ###

import functools


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

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

answers = []

prev_mul_scores_last_k = functools.reduce(lambda acc, score: acc * score, scores[:k])

prev_score = scores[0]

for i in range(k, n):
    mul_scores_last_k = (prev_mul_scores_last_k // prev_score) * scores[i]

    if prev_mul_scores_last_k < mul_scores_last_k:
        answers.append('Yes')
    else:
        answers.append('No')

    prev_mul_scores_last_k = mul_scores_last_k
    prev_score = scores[i - (k - 1)]

for answer in answers:
    print(answer)

### FIXED CODE ###

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

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

answers = []

prev_score = scores[0]

for i in range(k, n):
    if prev_score < scores[i]:
        answers.append('Yes')
    else:
        answers.append('No')

    prev_score = scores[i - (k - 1)]

for answer in answers:
    print(answer)
### BUGGY CODE ###

x=input().replace("ST","")
for _ in range(100000):
    if "ST" in x:
        x=x.replace("ST","")
print(len(x))

### FIXED CODE ###

x=list(input())
stack=[]
for i in range(len(x)):
    if x[i]=="S":
        stack.append(x[i])
    elif x[i]=="T" and len(stack)==0:
        stack.append(x[i])
    elif x[i]=="T" and stack[-1]=="T":
        stack.append(x[i])
    elif x[i]=="T" and stack[-1]=="S":
        stack.pop()
print(len(stack))
### BUGGY CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = Counter(a)
s = []
m = max(a) + 1
ans = 0
for i in a:
    if i in s:
        continue
    if c[i] == 1:
        ans += 1
    for i in range(i, m, i):
        s.append(i)
print(ans)

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
a.sort()
c = Counter(a)
m = max(a) + 1
dp = [False]*m
ans = 0
for ai in a:
    if dp[ai]:
        continue
    if c[ai] == 1:
        ans += 1
    for i in range(ai, m, ai):
        dp[i] = True
print(ans)
### BUGGY CODE ###

h,w,a,b=map(int,input().split())

m=[[0]]
for i in range(w-1):
  s=min(0,1,key=lambda x:m[0].count(x))
  x=m[0].count(s)
  m[0]+=[s if x<a else 1-s]
for i in range(h-1):
  n=list(zip(*m))
  s=min(0,1,key=lambda x:n[0].count(x))
  x=n[0].count(s)
  m+=[m[0]]
  if (x<b) ^ (s==0):
    m[-1]=[1-j for j in m[-1]]

for i in m:
  print(*i,sep="")

### FIXED CODE ###

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

arow = '1'*A + '0'*(W-A)
brow = '0'*A + '1'*(W-A)

for i in range(1,H+1):
    if (i <= B):
        print(brow)
    else:
        print(arow)
### BUGGY CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque

def check(max_length, left, right, r, index):
    if index == 1000:
        print(left)
    half = (left + right) / 2
    if 2 * half <= max_length * (r - half) / r:
        check(max_length, half, right, r, index + 1)
    else:
        check(max_length, left, half, r, index + 1)

def main():
    data = [list(map(int, input().split())) for i in range(3)]
    a = ((data[0][0] - data[1][0]) ** 2 + (data[0][1] - data[1][1]) ** 2) ** 0.5
    b = ((data[1][0] - data[2][0]) ** 2 + (data[1][1] - data[2][1]) ** 2) ** 0.5
    c = ((data[0][0] - data[2][0]) ** 2 + (data[0][1] - data[2][1]) ** 2) ** 0.5

    s = (a + b + c) / 2
    S = (s * (s - a) * (s - b) * (s - c)) ** 0.5
    r = 2 * S / (a + b + c)

    left, right = 0, max(a, b, c)

    check(max(a, b, c), left, right, r, 0)





if __name__ == '__main__':
    main()
    # test()



### FIXED CODE ###

from collections import Counter, defaultdict
import sys
sys.setrecursionlimit(10 ** 5 + 10)
# input = sys.stdin.readline
from math import factorial
import heapq, bisect
import math
import itertools


import queue
from collections import deque

def check(max_length, left, right, r, index):
    if index == 1000:
        print(left)
        sys.exit()
    half = (left + right) / 2
    if 2 * half <= max_length * (r - half) / r:
        check(max_length, half, right, r, index + 1)
    else:
        check(max_length, left, half, r, index + 1)

def main():
    data = [list(map(int, input().split())) for i in range(3)]
    a = ((data[0][0] - data[1][0]) ** 2 + (data[0][1] - data[1][1]) ** 2) ** 0.5
    b = ((data[1][0] - data[2][0]) ** 2 + (data[1][1] - data[2][1]) ** 2) ** 0.5
    c = ((data[0][0] - data[2][0]) ** 2 + (data[0][1] - data[2][1]) ** 2) ** 0.5

    s = (a + b + c) / 2
    S = (s * (s - a) * (s - b) * (s - c)) ** 0.5
    r = 2 * S / (a + b + c)

    left, right = 0, max(a, b, c)

    check(max(a, b, c), left, right, r, 0)





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

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

from collections import defaultdict
import heapq
n,m,s = inm()
aas = []
dst = [{} for i in range(n+1)]
for i in range(m):
    uu,vv,aa,bb = inm()
    dst[uu][vv] = (aa,bb)
    dst[vv][uu] = (aa,bb)
    aas.append(aa)
maxa = max(aas)
s = min(s,(maxa+1)*n-1)
c = [-1]
d = [-1]
for i in range(n):
    cc,dd = inm()
    c.append(cc)
    d.append(dd)

dst2 = defaultdict(dict)
for u in range(1,n+1):
    for v in dst[u]:
        m = dst[u][v][0]
        t = dst[u][v][1]
        for p in range((maxa+1)*n-c[u]):
            dst2[(u,p)][(u,p+c[u])] = d[u]
        for p in range((maxa+1)*n):
            if p>=m:
                dst2[(u,p)][(v,p-m)] = t

if DBG:
    print("dst2)")
    for z in dst2:
        printn(str(z)+':')
        ddprint(dst2[z])
cost = {}
for z in dst2:
    cost[z] = BIG
q = [(0,1,s)]
while len(q)>0:
    dd,u,p = heapq.heappop(q)
    if cost[(u,p)]<=dd:
        continue
    cost[(u,p)] = dd
    for v,r in dst2[(u,p)]:
        heapq.heappush(q,(dd+dst2[(u,p)][(v,r)], v,r))

if DBG:
    print("cost)")
    for z in cost:
        printn(str(z)+':')
        ddprint(cost[z])
ans = [BIG]*(n+1)
for u,p in cost:
    ans[u] = min(ans[u], cost[(u,p)])
for i in range(2,n+1):
    print(ans[i])


### FIXED CODE ###

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True  and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

#from collections import defaultdict
import heapq
n,m,s = inm()
ST = 51*(n+1)
dst = [{} for i in range(n+1)]
for i in range(m):
    uu,vv,aa,bb = inm()
    dst[uu][vv] = (aa,bb)
    dst[vv][uu] = (aa,bb)
s = min(s,ST-1)
c = [-1]
d = [-1]
for i in range(n):
    cc,dd = inm()
    c.append(cc)
    d.append(dd)

dst2 = [[] for i in range((n+1)*ST)]
for u in range(1,n+1):
    for p in range(ST-c[u]):
        dst2[u*ST+p].append((u*ST+p+c[u], d[u]))
    for v in dst[u]:
        m = dst[u][v][0]
        t = dst[u][v][1]
        for p in range(m,ST):
            dst2[u*ST+p].append((v*ST+p-m,t))

if DBG:
    print("dst2)")
    for u,p in [(1,50),(2,50),(1,3)]:
        #z,pp = dst2[u*ST+p]
        ddprint("u {u} p {p} d2 {dst2[u*ST+p]}")
        for z in dst2[u*ST+p]:
            ddprint("v {z[0]//ST} q {z[0]%ST} t {z[1]}")

cost = [BIG]*((n+1)*ST)
q = [(0,1*ST+s)]
while len(q)>0:
    dd,u = heapq.heappop(q)
    if cost[u]<=dd:
        continue
    cost[u] = dd
    for v,t in dst2[u]:
        heapq.heappush(q,(dd+t, v))

if DBG:
    print("cost) ST {ST} s {s}")
    for u,p in [(2,204),(3,154),(4,154)]:
        ddprint("u {u} p {p} suf {u*ST+p} cost {cost[u*ST+p]}")

ddprint(cost)
ans = [BIG]*(n+1)
for i in range(2,n+1):
    ans[i] = min(cost[i*ST:(i+1)*ST])
    #ddprint(f"i {i} i*ST {i*ST}")
    ddprint(cost[i*ST:(i+1)*ST])
for i in range(2,n+1):
    print(ans[i])
### BUGGY CODE ###

import math

line=input().split(" ")
n=int(line[3])
r=int(line[0])
g=int(line[1])
b=int(line[2])
nline=sorted([r,g,b])
x=int(nline[2])
y=int(nline[1])
z=int(nline[0])


answers=0
#print(x,y,z,n)


for i in range(math.ceil(n/x)+1):
    a=i
    for j in range(math.ceil(n/y)+1):
        b=j
        c=(n-a*x-b*y)/z
        if c>=0 and (n-a*x-b*y)%z==0:
            answers+=1
            #print(a,b,c)

print(answers)

### FIXED CODE ###

# coding: utf-8
# Your code here!
import math

line=input().split(" ")
n=int(line[3])
r=int(line[0])
g=int(line[1])
b=int(line[2])
nline=sorted([r,g,b])
x=int(nline[2])
y=int(nline[1])
z=int(nline[0])

answers=0
#print(x,y,z,n)


for i in range(math.ceil(n/x)+1):
    a=i
    if z!=1:
        for j in range(math.ceil((n-a*x)/y)+1):
            b=j
            c=(n-a*x-b*y)/z
            if c>=0 and (n-a*x-b*y)%z==0:
                answers+=1
                #print(a,b,c)
    else:
        if n-a*x>=0:
            if n-a*x==0:
                answers+=1
                #print('a', 1)
            elif (n-a*x)%y!=0:
                answers+=math.ceil((n-a*x)/y)
                #print('b', math.ceil((n-a*x)/y))
            else:
                answers+=(math.ceil((n-a*x)/y)+1)
                #print('c', math.ceil((n-a*x)/y)+1)
            

print(answers)
### BUGGY CODE ###

N=int(input())
S=input()

Lis=[[] for _ in range(3)]
RGB="RGB"

for i in range(N):
    idx=RGB.index(S[i])
    Lis[idx].append(i+1)

if len(Lis[0])==0 or len(Lis[1])==0 or len(Lis[2])==0:
    print(0)
    exit()

Ng=len(Lis[2])
ans=0
for r in Lis[0]:
    for g in Lis[1]:
        n1=2*r-g
        n2=2*g-r
        n3=(r+g)//2
        Su=Ng
        if N>=n1>0:
            if n1 in Lis[2]:
                Su-=1
        if N>=n2>0:
            if n2 in Lis[2]:
                Su-=1
        if (g-r)%2==0:
            if n3 in Lis[2]:
                Su-=1
        ans+=Su
print(ans)

### FIXED CODE ###

N=int(input())
S=input()

Lis=[[] for _ in range(3)]
RGB="RGB"

for i in range(N):
    idx=RGB.index(S[i])
    Lis[idx].append(i+1)

if len(Lis[0])==0 or len(Lis[1])==0 or len(Lis[2])==0:
    print(0)
    exit()

Ng=len(Lis[2])
ans=0
for r in Lis[0]:
    for g in Lis[1]:
        n1=2*r-g
        n2=2*g-r
        n3=(r+g)//2
        Su=Ng
        if N>=n1>0:
            if S[n1-1]=="B":
                Su-=1
        if N>=n2>0:
            if S[n2-1]=="B":
                Su-=1
        if (g-r)%2==0:
            if S[n3-1]=="B":
                Su-=1
        ans+=Su
print(ans)
### BUGGY CODE ###

H,W = list(map(int,input().split()))
A = [["*"]*(W+2)]
 
sum = 0
cnt = 0
 
for i in range(H):
    a = ["*"]
    a += input()
    a.append("*")
    sum += a.count("#")
    A.append(a)
A.append(["*"]*(W+2))
 
while True:
    if sum == H*W:
        break
    x = []
    for i in range(1,H+1):
        for j in range(1,W+1):
            if A[i][j] == ".":
                for k,l in [[-1,0],[0,-1],[0,1],[1,0]]:
                    if A[i+k][j+l] == "#":
                        x.append([i,j])
                        break
 
    for i,j in x:
        A[i][j] = "#"
        sum += 1
 
    cnt += 1
 
print(cnt)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
q = deque()
A = []
for h in range(H):
    r = input()
    for w in range(W):
        if r[w] == "#":
            q.append([h, w])
    A.append([0 if s=="#" else -1 for s in r])

d = [[-1, 0], [0, -1], [0, 1], [1, 0]]
p = 0

while q:
    h, w = q.popleft()
    p = A[h][w]+1
    for dh, dw in d:
        nh = h+dh
        nw = w+dw
        if not (0 <= nh < H):
            continue
        if not (0 <= nw < W):
            continue
        if A[nh][nw] == -1:
            A[nh][nw] = p
            q.append([nh, nw])

print(p-1)
### BUGGY CODE ###

N=int(input())
def make(x):
    x=bin(int(x))[2:]
    return "0"*(20-len(x))+x
A=list(map(make,input().split()))
data=[0]*N
r=-1
two=set()
from collections import defaultdict
cnt=defaultdict(int)
for k in range(N):
    while len(two)==0 and r<N:
        r+=1
        if r==N:
            break
        for i,x in enumerate(A[r]):
            cnt[i]+=int(x)
            if cnt[i]==2:
                two|={i}
    data[k]=r-1
    for i,x in enumerate(A[k]):
        cnt[i]-=int(x)
        if cnt[i]<2:
            two-={i}
print(sum([data[i]-i+1 for i in range(N)]))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
data=[0]*N
r=-1
S=0
T=0
for k in range(N):
    while S==T and r<N:
        r+=1
        if r==N:
            break
        S+=A[r]
        T^=A[r]
    data[k]=r-1
    S-=A[k]
    T^=A[k]
print(sum([data[i]-i+1 for i in range(N)]))
### BUGGY CODE ###

def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [[input().split()] for _ in range(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]

from copy import deepcopy
import itertools

h,w=n1()
s=s2(h)
s=["#"+x+"#" for x in s]
s=["#"*(w+2)]+s+["#"*(w+2)]
meiro_original=[[0]*(w+2) for _ in range(h+2)]
road=[]
for i in range(len(s)):
    for j in range(len(s[i])):
        if s[i][j]=="#":
            meiro_original[i][j]=2
        else:
            meiro_original[i][j]=0
            road.append([i,j])


def calc(start,goal):
    min_count=9999999999
    meiro=deepcopy(meiro_original)
    meiro[goal[0]][goal[1]]=1
    pos=[[start[0],start[1],0]]
    while len(pos)>0:
        x,y,count=pos.pop(0)

        if meiro[x][y]==1:
            min_count=min(count,min_count)
            break

        meiro[x][y]=2

        if meiro[x-1][y]<2:
            pos.append([x-1,y,count+1])    
        if meiro[x+1][y]<2:
            pos.append([x+1,y,count+1])    
        if meiro[x][y-1]<2:
            pos.append([x,y-1,count+1]) 
        if meiro[x][y+1]<2:
            pos.append([x,y+1,count+1])

    return min_count
ans=0
for x in itertools.combinations(road,2):
    ans=max(ans,calc(x[0],x[1]))
    
print(ans)

### FIXED CODE ###


def s0():return input()
def s1():return input().split()
def s2(n):return [input() for x in range(n)]
def s3(n):return [input().split() for _ in range(n)]
def s4(n):return [[x for x in s] for s in s2(n)]
def n0():return int(input())
def n1():return [int(x) for x in input().split()]
def n2(n):return [int(input()) for _ in range(n)]
def n3(n):return [[int(x) for x in input().split()] for _ in range(n)]
def t3(n):return [tuple(int(x) for x in input().split()) for _ in range(n)]
def p0(b,yes="Yes",no="No"): print(yes if b else no)
# from sys import setrecursionlimit
# setrecursionlimit(1000000)
from collections import Counter,deque,defaultdict
import itertools
# import math
# import networkx as nx
# from bisect import bisect_left,bisect_right
# from heapq import heapify,heappush,heappop

h,w=n1()
s=s4(h)
def make_around(s,h):
    sss=[[-1]*(w+2)]
    for line in s:
        sss.append([-1]+[-1 if i=="#" else 0 for i in line ]+[-1])
    sss.append([-1]*(w+2))
    return sss

s=make_around(s,h)
d=[]
for i in range(1,h+1):
    for j in range(1,w+1):
        if s[i][j]==0:
            d.append((i,j))

from copy import deepcopy
ans=0
for i in range(len(d)):
    ss=deepcopy(s)
    x,y=d[i]
    q=deque([(x,y)])
    ss[x][y]=1
    while len(q)>0:
        x,y=q.popleft()
        if ss[x+1][y]==0:
            ss[x+1][y]=ss[x][y]+1
            q.append((x+1,y))
        if ss[x-1][y]==0:
            ss[x-1][y]=ss[x][y]+1
            q.append((x-1,y))
        if ss[x][y+1]==0:
            ss[x][y+1]=ss[x][y]+1
            q.append((x,y+1))
        if ss[x][y-1]==0:
            ss[x][y-1]=ss[x][y]+1
            q.append((x,y-1))
    ans=max(ans,max(list(itertools.chain.from_iterable(ss))))
print(ans-1)
### BUGGY CODE ###

BASE =  1000000007

class Route(object):
    def __init__(self):
        self.counter = [1]

    def getCounter(self, idx):
        if idx == -1:
            return 0
        try:
            return self.counter[idx]
        except IndexError:
            return 0

    def getList(self):
        return self.counter

    def append(self, elem):
        self.counter.append(elem)

if __name__ == '__main__':
    N, M = [int(i) for i in input().split()]
    not_available = []
    for i in range(M):
        not_available.append(int(input()))
    route_counter = Route()
    for idx in range(1, N + 1):
        if idx in not_available:
            route_counter.append(0)
            continue
        route_counter.append(route_counter.getCounter(idx - 1) + route_counter.getCounter(idx - 2))
    print(route_counter.getCounter(N) % BASE)

### FIXED CODE ###

BASE =  1000000007

if __name__ == '__main__':
    N, M = [int(i) for i in input().split()]
    not_available = []
    for i in range(M):
        not_available.append(int(input()))
    x = 0
    y = 1
    predicted_next = 1
    is_available = [True] * N
    for idx in not_available:
        is_available[idx - 1] = False

    for flag in is_available:
        if flag:
            z = x + y
            x = y
            y = z
        else:
            x = y
            y = 0

    print(y % BASE)
### BUGGY CODE ###

s_list = list(input())
q = int(input())


for _ in range(q):
	query= input().split()
	if int(query[0]) == 1:
		s_list.reverse()
	elif int(query[0]) == 2:
		if int(query[1]) == 1:
			s_list.insert(0, query[2])
		elif int(query[1]) == 2:
			s_list.append(query[2])

for s in s_list:
  print(s, end ="")



### FIXED CODE ###

from collections import deque

s_list = list(input())
d = deque(s_list)
q = int(input())
reverse = False

for _ in range(q):
	query= input().split()
	if int(query[0]) == 1:
		if reverse: reverse = False
		else: reverse = True
	elif int(query[0]) == 2:
		if int(query[1]) == 1:
			if reverse:
				d.append(query[2])
			else:
				d.appendleft(query[2])
		elif int(query[1]) == 2:
			if reverse:
				d.appendleft(query[2])
			else:	
				d.append(query[2])


if reverse:
	d.reverse()
for s in d:
  print(s, end ="")
### BUGGY CODE ###

n = int(input())
lst1 = list(map(int, input().split()))
for i in range(1, n + 1):
  res = 0
  for j in range(n - 1):
    if lst1[j] == i:
      res += 1
  print(res)

### FIXED CODE ###

n = int(input())
lst1 = list(map(int, input().split()))
reslst = [0] * n
for i in range(n - 1):
  reslst[lst1[i] - 1] += 1
for i in range(n):
  print(reslst[i])
### BUGGY CODE ###

n, t = map(int, input().split())
dices = map(int, input().split())
avg = list(map(lambda x: sum(x)/len(x)+1, map(range, dices)))
s = prev = sum(avg[0:t])

for i in range(1, n-t+1):
  prev = prev - avg[i-1] + avg[i+t-1]
  s = max(s, prev)
print(s)


### FIXED CODE ###

n, t = map(int, input().split())
dices = map(int, input().split())
avg = list(map(lambda n: (n+1)/2, dices))
s = prev = sum(avg[0:t])

for i in range(1, n-t+1):
  prev = prev - avg[i-1] + avg[i+t-1]
  s = max(s, prev)
print(s)
### BUGGY CODE ###

from functools import lru_cache

N = int(input().strip())
A = [int(v) for v in input().strip().split()]
C = {}

@lru_cache(maxsize=None)
def calc(a):
    global C
    C[a] -= 1
    sum_ = sum([n * (n - 1) // 2 for n in C.values() if n > 1])
    C[a] += 1
    return sum_

for a in A:
    C.setdefault(a, 0)
    C[a] += 1

for i, a in enumerate(A):
    print(calc(a))


### FIXED CODE ###

from functools import lru_cache

N = int(input().strip())
A = [int(v) for v in input().strip().split()]
C = {}


@lru_cache(maxsize=None)
def pair(k):
    return k * (k - 1) // 2

@lru_cache(maxsize=None)
def calc(s, a):
    return s - pair(C[a]) + pair(C[a] - 1)

for a in A:
    C.setdefault(a, 0)
    C[a] += 1

S = sum([pair(v) for v in C.values()])

for a in A:
    print(calc(S, a))
### BUGGY CODE ###

#n = (int(i) for i in input().split())  
n=int(input())
prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101]
num=[1] * n
count = 0
for i in range(0,n):
    S = input()
    for s in S:
        num[i] = num[i] * prime[ord(s)-ord('a')]
    for j in range(0,i):
        if num[i] == num[j]:
            count = count + 1
print(count)    

### FIXED CODE ###

import collections
#n = (int(i) for i in input().split())  
n=int(input())
prime = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101]
num=[1] * n
count = 0
for i in range(0,n):
    S = input()
    for s in S:
        num[i] = num[i] * prime[ord(s)-97]
#    for j in range(0,i):
#        if num[i] == num[j]:
#            count = count + 1
c = collections.Counter(num)
for v in c.values():
    if v > 1:
        count = count + v*(v-1)/2
#print(c)
print(int(count))
### BUGGY CODE ###

N,Q=map(int, input().split())
S=list(input())
A = []
for i in range(Q):
  A.append(list(map(int, input().split())))
for i in range(Q):
  count=0
  ent=False
  L=S[A[i][0]-1:A[i][1]]
  for j in range(len(L)):
    if L[j]=="A":
      ent=True
    if L[j]=="C" and ent==True:
      count+=1
      ent=False
  print(count)

### FIXED CODE ###

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