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

def extract_max(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:  # ???????????????
        v = A[i]
        rv = 0
        lv = 0
        r = (i + 1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x

def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


heap = []
while True:
    cmd = input().split()
    if cmd[0] == "end":
        break
    elif cmd[0] == "extract":
        print(extract_max(heap))
    elif cmd[0] == "insert":
        insert(heap, int(cmd[1]))


### FIXED CODE ###

import sys


def extract_max(A):
    x = A[0]
    A[0] = A[-1]
    A.pop()
    H = len(A)
    i = 0
    while i < H:
        v = A[i]
        rv = 0
        lv = 0
        r = (i + 1) * 2
        l = r - 1
        if l < H:
            lv = A[l]
            if r < H:
                rv = A[r]

        if v < lv and lv > rv:
            A[l] = v
            A[i] = lv
            i = l
        elif v < rv:
            A[r] = v
            A[i] = rv
            i = r
        else:
            break
    return x


def insert(a, n):
    i = len(a)
    a.append(n)
    while i > 0:
        p = int((i + 1) / 2) - 1
        v = a[i]
        pv = a[p]
        if pv < v:
            a[p] = v
            a[i] = pv
            i = p
        else:
            break


def main():
    istr = sys.stdin.read()
    cmds = list(istr.splitlines())
    S = []
    for cmd in cmds:  # input()
        if cmd[0] == "i":
            insert(S, int(cmd[7:]))

        elif cmd == "extract":
            a = extract_max(S)
            print(a)

        elif cmd == "end":
            break


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

# coding: utf-8
# hello worldと表示する
#float型を許すな
#numpyはpythonで
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
from collections import Counter, deque
from collections import defaultdict
from itertools import combinations, permutations, accumulate, groupby, product
from bisect import bisect_left,bisect_right
from heapq import heapify, heappop, heappush
from math import floor, ceil,pi,factorial
from operator import itemgetter
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI2(): return [int(input()) for i in range(n)]
def MXI(): return [[LI()]for i in range(n)]
def SI(): return input().rstrip()
def printns(x): print('\n'.join(x))
def printni(x): print('\n'.join(list(map(str,x))))
inf = 10**17
mod = 10**9 + 7
#0-indexに注意
n,m=MI()
al=[0]*n
lis=[[] for i in range(n)]
for i in range(m):
    a,b=MI()
    a-=1
    b-=1
    al[b]=-1
    lis[a].append(b)
starts=[]
for i in range(n):
    if al[i]==0:
        starts.append(i)
#print(starts)
#print(lis)
dp=[0 for i in range(n)]
def dfsdp(x):
    for y in lis[x]:
        dp[y]=max(dp[y],dp[x]+1)
        dfsdp(y)
for x in starts:
    dfsdp(x)
print(max(dp))



### FIXED CODE ###

from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
from bisect import bisect_right, bisect_left
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, gamma, log
from operator import mul
from functools import reduce
from copy import deepcopy

sys.setrecursionlimit(2147483647)
INF = 10 ** 20
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): pass
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7


n, m = LI()
G = [[] for _ in range(n)]
for _ in range(m):
    a, b = LI()
    G[a-1]+=[b-1]



dp = [-1] * n

def f(x):
    if dp[x] != -1:
        return dp[x]
    ret = 0
    for y in G[x]:
        ret = max(f(y) + 1, ret)
    dp[x] = ret
    return ret

for i in range(n):
    f(i)

print(max(dp))
### BUGGY CODE ###

h, w, m = map(int, input().split())
bord_x, bord_y = [0 for i in range(h)], [0 for i in range(w)]
bord = [[0 for _i in range(w)] for _j in range(h)]

for _i in range(m):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    bord[s][t] += 1
    bord_x[s] += 1
    bord_y[t] += 1

x_max, y_max = max(bord_x), max(bord_y)
a = [x for x, p in enumerate(bord_x) if x_max==p]
b = [y for y, p in enumerate(bord_y) if y_max==p]

r = x_max + y_max - 1
for i in a:
    for j in b:
        if bord[i][j] == 0:
            r += 1
            import sys
            print(r)
            sys.exit()
print(r)

### FIXED CODE ###

h, w, m = map(int, input().split())
bord_x, bord_y = [0]*h, [0]*w
 
hw = []
for _i in range(m):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    bord_x[s] += 1
    bord_y[t] += 1
    hw.append([s, t])
 
x_max, y_max = max(bord_x), max(bord_y)
 
cnt = 0
for i, j in hw:
    if bord_x[i] == x_max and bord_y[j] == y_max:
        cnt += 1
 
if cnt == bord_x.count(x_max)*bord_y.count(y_max):
    x_max -= 1
 
print(x_max+y_max)
### BUGGY CODE ###

X,K,D = map(int,input().split())
ans=X
min_abs = 10**15
for i in range(K):
  ans = min(abs(ans+D),abs(ans-D))
  
print(ans)

### FIXED CODE ###

X,K,D = map(int,input().split())

def sgn(x):
  if x > 0:return 1
  if x < 0:return -1
  return 0

if X > 0:
  x_greedy = X - K*D
else:
  x_greedy = X + K*D
  
if sgn(X) == sgn(x_greedy):
  print(abs(x_greedy))
  exit()
x_r = X%D
x_l = x_r - D

r_parity = (abs(X-x_r)//D)%2

if K%2 == r_parity:
  print(abs(x_r))
else:
  print(abs(x_l))
### BUGGY CODE ###

INF = float("inf")

N, *S = map(int, open(0).read().split())

S.sort(reverse=True)

T = [S[0]]
for _ in range(N):
    T.sort()

    Q = T[:]
    while Q:
        q = Q.pop()

        for i, s in enumerate(S):
            if s < q:
                T.append(s)
                S[i] = INF
                break
        else:
            print("No")
            quit()

print("Yes")


### FIXED CODE ###

INF = float("inf")

N, *S = map(int, open(0).read().split())
M = len(S)

S.sort(reverse=True)

Q = [S[0]]
S[0] = INF
for _ in range(N):
    Q.sort()
    T = Q[:]

    cur = 1
    while Q:
        p = Q.pop()
        while S[cur] >= p:
            cur += 1
            if cur == M:
                print("No")
                exit()
        T.append(S[cur])
        S[cur] = INF

    Q = T

print("Yes")
### BUGGY CODE ###

#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

def comb(n,r):
    if n - r < 0:
        return 0
    return math.factorial(n)*pow(math.factorial(r),mod-2,mod)*pow(math.factorial(n-r),mod-2,mod) % mod
n = I()
a = LI()
c = list(Counter(a).items())
c.sort(key = itemgetter(1),reverse = True)
x = c[0][0]
lst = []
for i in range(n+1):
    if a[i] == x:
        lst.append(i+1)
a,b = lst[0],lst[1]
for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)
    

### FIXED CODE ###

#!/usr/bin/env python3
#ABC66 D

import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(1000000)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def f(a, b):
    if b == 0: 
        return 1
    if b % 2 == 0:
        d = f(a, b // 2)
        return d * d % mod
    if b % 2 == 1:
        return (a * f(a, b - 1)) % mod


def comb(n,r):
    if n - r < 0:
        return 0
    return fact[n] * invfact[r] * invfact[n-r] % mod

n = I()
a = LI()
cnt = [0]*(n+1)
for i in range(n+1):
    if cnt[a[i]]:
        a = cnt[a[i]]
        b = i+1
        break
    else:
        cnt[a[i]] = i+1

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

for i in range(n+1):
    res = 0
    res = (res + comb(n+1,i+1)) % mod
    res = (res - comb((a-1)+(n+1-b),i)) % mod
    print(res)
### BUGGY CODE ###

R,G,B,N=map(int,input().split())

RL=(N+R-1)//R
if RL*R>N:
    RL=RL-1

cnt=0
for r in range(RL+1):
    GL=(N-r*R+G-1)//G
    for g in range(GL+1):
        if (r*R+g*G)>N:continue
        if (N-r*R-g*G)%B==0:
            cnt+=1

print(cnt)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for i in range(int(N / R) + 1):
    for j in range(int((N - i * R) / G) + 1):
        if ((N - (i * R + j * G)) % B == 0):
            ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())
x = [0] + [int(input()) for i in range(n)]
cnt = 1
idx = min(x[1:])
while True:
    if x[idx] == 2:
        ans = cnt
        break
    elif x[idx] == x.index(x[idx]):
        ans = -1
        break
    elif x.index(x[idx]) == x.index(min(x[1:])):
        ans = -1
        break
    idx = x[idx]
    cnt += 1
print(ans)

### FIXED CODE ###

def train(n):
    x =[0] + [int(input()) for i in range(n)]
    idx = 1
    for i in range(n+1):
        if x[idx] == 2:
            return i + 1
        idx = x[idx]
    return -1
n = int(input())
print(train(n))
### BUGGY CODE ###

n = int(input())
num_list = map(int, input().split())

a = 1
for x in num_list:
  a = a * x
if a > 1000000000000000000:
  print("-1")
else:
	print(a)

### FIXED CODE ###

n = int(input())
num_list = list(map(int, input().split()))
     
a = 1
if 0 in num_list:
    print(0)
else:
    for x in num_list:
        a = a * x
        if (a > 1000000000000000000):
            print("-1")
            break
    if (a <= 1000000000000000000):
      print(a)
### BUGGY CODE ###

s = list(input())
q = int(input())

me = 1#1:sei  -1:gyaku
for i in range(q):
    t = input().split()
    if t[0] == '1':
        me *= -1
            
    else:# 0=2
        if t[1]=='1':#1=1
            if me == 1:
                s.insert(0,t[2])
            else:
                s.append(t[2])
        else:#1=2
            if me == 1:
                s.append(t[2])
            else:
                s.insert(0,t[2])

if me != 1:
    s = s[::-1]
print(''.join(s))

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
 
me = 1#1:sei  -1:gyaku
for i in range(q):
    t = input().split()
    if t[0] == '1':
        me *= -1
            
    else:# 0=2
        if t[1]=='1':#1=1
            s.appendleft(t[2]) if me == 1 else s.append(t[2])
        else:#1=2
            s.append(t[2]) if me == 1 else s.appendleft(t[2])
s= list(s) 
if me != 1:
    s = s[::-1]
print(''.join(s))
### BUGGY CODE ###

h,w = map(int,input().split())
s = []
for i in range(h):
    s1 = list(input())
    s.append(s1)
p = []
q = []
r = []
t = []
l = []
for i in range(h):
    count1 = 0
    count2 = 0
    p1 = []
    q1 = []
    for j in range(w):
        if s[i][j] == ".":
            count1 = count1 + 1
            p1.append(count1)
        elif s[i][j] == "#":
            count1 = 0
            p1.append(count1)
        if s[i][w-j-1] == ".":
            count2 = count2 + 1
            q1.append(count2)
        elif s[i][w-j-1] == "#":
            count2 = 0
            q1.append(count2)
    q1.reverse()
    p.append(p1)
    q.append(q1)
for i in range(w):
    count1 = 0
    count2 = 0
    r1 = []
    t1 = []
    for j in range(h):
        if s[j][i] == ".":
            count1 = count1 + 1
            r1.append(count1)
        elif s[j][i] == "#":
            count1 = 0
            r1.append(count1)
        if s[h-j-1][i] == ".":
            count2 = count2 + 1
            t1.append(count2)
        elif s[h-j-1][i] == "#":
            count2 = 0
            t1.append(count2)
    t1.reverse()
    r.append(r1)
    t.append(t1)
for i in range(h):
    for j in range(w):
        l.append(p[i][j]+q[i][j]+r[j][i]+t[j][i])
print(max(l)-3)

### FIXED CODE ###

h,w = map(int,input().split())
s = []
for i in range(h):
    s1 = list(input())
    s.append(s1)
p = []
q = []
r = []
t = []
l = 0
for i in range(h):
    count1 = 0
    count2 = 0
    p1 = []
    q1 = []
    for j in range(w):
        if s[i][j] == ".":
            count1 = count1 + 1
            p1.append(count1)
        elif s[i][j] == "#":
            count1 = 0
            p1.append(count1)
        if s[i][w-j-1] == ".":
            count2 = count2 + 1
            q1.append(count2)
        elif s[i][w-j-1] == "#":
            count2 = 0
            q1.append(count2)
    p.append(p1)
    q.append(q1)
for i in range(w):
    count1 = 0
    count2 = 0
    r1 = []
    t1 = []
    for j in range(h):
        if s[j][i] == ".":
            count1 = count1 + 1
            r1.append(count1)
        elif s[j][i] == "#":
            count1 = 0
            r1.append(count1)
        if s[h-j-1][i] == ".":
            count2 = count2 + 1
            t1.append(count2)
        elif s[h-j-1][i] == "#":
            count2 = 0
            t1.append(count2)
    r.append(r1)
    t.append(t1)
for i in range(h):
    for j in range(w):
        l1 = p[i][j]+q[i][w-j-1]+r[j][i]+t[j][h-i-1]
        if l < l1:
            l = l1
print(l-3)
### BUGGY CODE ###

def main():
    from collections import Counter
    import sys

    sys.setrecursionlimit(10 ** 7)
    input = sys.stdin.readline

    def f(c1, c2, c3):
        ind = c1 * x1 + c2 * x2 + c3
        if dp[ind] != -1.0:
            return dp[ind]

        res = n
        if c1 > 0:
            res += f(c1 - 1, c2, c3) * c1
        if c2 > 0:
            res += f(c1 + 1, c2 - 1, c3) * c2
        if c3 > 0:
            res += f(c1, c2 + 1, c3 - 1) * c3
        res /= c1 + c2 + c3

        dp[ind] = res
        return res

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [-1.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    print(f(c1, c2, c3))


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けた


### FIXED CODE ###

def main():
    from collections import Counter

    n = int(input())
    a = tuple(int(x) for x in input().split())

    c = Counter(a)
    c1 = c[1]
    c2 = c[2]
    c3 = c[3]

    x1 = 310 ** 2
    x2 = 310

    dp = [0.0] * (310 ** 3)
    dp[0] = 0.0
    # dp[x * x1 + y * x2 + z]:=1,2,3個の皿がx,y,z残っているときの期待値

    for r3 in range(c3 + 1):
        d3 = c3 - r3
        for r2 in range(c2 + d3 + 1):
            for r1 in range(c1 + d3 + c2 - r2 + 1):
                ind = r1 * x1 + r2 * x2 + r3
                if ind != 0:
                    dp[ind] = (n \
                               + (dp[ind - x1] * r1 if r1 > 0 else 0) \
                               + (dp[ind + x1 - x2] * r2 if r2 > 0 else 0) \
                               + (dp[ind + x2 - 1] * r3 if r3 > 0 else 0)) \
                              / (r1 + r2 + r3)

    print(dp[c1 * x1 + c2 * x2 + c3])


if __name__ == '__main__':
    main()

# dp[now] =
# 1
# + dp[1個の皿を食べた] * p
# + dp[2個の皿を食べた] * p
# + dp[3個の皿を食べた] * p
# + dp[0個の皿を食べた==now] * p

# if mainの追加
# 初期値None->-1.0にした
# checked配列を辞めた
# チェック済みかどうかの判定を-1.0と一致するかの比較にした

# カウントはCounterを使う方が速い
# 1次元にした
# resの加算を複数回に分けると
# 三項演算子より遅くなる
# 再帰関数を辞めた
### BUGGY CODE ###

n,m = map(int,input().split())
ans = {}
for _ in range(m):
    l,r = map(int,input().split())
    gate = []
    if ans:
        for i in range(max(l,min(ans)),min(r+1,max(ans))+1):
            gate.append(i)
        ans &= set(gate)
    else:
        for i in range(l,r+1):
            gate.append(i)
        ans = set(gate)
print(len(ans))

### FIXED CODE ###

n,m = map(int,input().split())
ans = []
for _ in range(m):
    l,r = map(int,input().split())
    if ans:
        ans = [max(ans[0],l),min(ans[1],r)]
    else:
        ans = [l,r]
print(ans[1]-ans[0]+1 if ans[1]-ans[0]+1>0 else 0)
### BUGGY CODE ###

n, k = map(int, input().split()) 
p_list = list(map(int, input().split()))
pe_list = [(p + 1) / 2 for p in p_list]

ans = -1
for i in range(n):
    if i + k > n: break
    ans = max(ans, sum(pe_list[i:i+k]))
print(ans)

### FIXED CODE ###

n, k = map(int, input().split()) 
p_list = list(map(int, input().split()))
e_list = [(p + 1) / 2 for p in p_list]

s = sum(e_list[:k])
ans = s
for i, e in enumerate(e_list[k:]):
    s = s - e_list[i] + e
    ans = max(ans, s)
print(ans)
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
    inp = input()
    o = int(inp.split()[0])
    if o == 1: 
        s = s[::-1]
    else:
        dmy, f, c = inp.split()
        f = int(f)
        if f == 1:
            s = c + s
        else:
            s = s + c

print(s)


### FIXED CODE ###

s = input()
q = int(input())

reverse = 0
sento = ''
matsubi = ''

for i in range(q):
    inp = input()
    if len(inp) <= 1:
        reverse += 1
    else:
        dmy, f, c = inp.split()
        f = int(f)
        if reverse & 1:
            if f == 1:
                matsubi = matsubi + c
            else:
                sento = c + sento
        else:
            if f == 1:
                sento = c + sento
            else:
                matsubi = matsubi + c

s = sento + s + matsubi

if reverse & 1:
    print(s[::-1])
else:
    print(s)
### BUGGY CODE ###

I=lambda:map(int,input().split())
n,m=I()
r=range(n)
y=[[] for i in r]
z=[None for i in r]

for _ in [0]*m:
  i,j,k=I()
  y[i-1]+=[[j-1, k]]
  y[j-1]+=[[i-1,-k]]

for i in r:
  if z[i]==None:
    z[i]=0 
  q=[i]
  while q:
    p=q.pop()
    for j,k in y[p]:
      if z[j]==None:
        q+=[j]
        z[j]=z[p]+k
      elif z[j]!=z[p]+k:
        print("No")
        exit()
print("Yes")

### FIXED CODE ###

I=lambda:map(int,input().split())
n,m=I()
r=range(n)
y=[[] for i in r]
z=[None for i in r]

for _ in [0]*m:
  i,j,k=I()
  y[i-1]+=[[j-1, k]]
  y[j-1]+=[[i-1,-k]]

for i in r:
  if z[i]==None:
    z[i]=0 
  q=[i]
  while q:
    p=q.pop()
    for j,k in y[p]:
      if z[j]==None:
        q+=[j]
        z[j]=z[p]+k
      elif z[j]!=z[p]+k:
        print("No")
        exit()
print("Yes")
### BUGGY CODE ###

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

print(ans)

### FIXED CODE ###

import bisect as bi
n = int(input())
l = list(map(int,input().split()))
l.sort()
#print(l)
ans = 0
for i in range(n-2):
  for j in range(i+1,n-1):
    ans += (bi.bisect_left(l,l[i]+l[j]))-j-1
    #print(i,j,bi.bisect_right(l,l[i]+l[j])-j-1)
    #print(ans)
print(ans)
### BUGGY CODE ###

def mdiv(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

n=int(input())
ans=chk=0
for i in range(1,n+1):
    ans+=i*len(mdiv(i))
print(ans)


### FIXED CODE ###

n=int(input())
ans=0
for i in range(1,n+1):
    m=n//i*i
    k=n//i
    ans+=(k*(i+m)//2)
print(ans)
### BUGGY CODE ###

from itertools import accumulate

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

A = list(range(2,max(r)+1))
sqrt_n = (max(r)+1)**(1/2)
idx = 0

while True:
    p = A[idx]
    if p > sqrt_n:
        break
    q = 2*p
    while q <= max(r):
        if q in A:
            A.remove(q)
        q += p
    idx += 1

ans = [0] * (max(r)+1)
for a in A:
    if (a+1)//2 in A:
        ans[a] += 1
ans = list(accumulate(ans))

for i,j in zip(l,r):
    print(ans[j]-ans[i-1])


### FIXED CODE ###

import math

def isPrime(n):
    m = (n + 1) // 2
    n_sqrt = int(math.sqrt(n))
    for i in range(2, n_sqrt + 1):
        if n % i == 0 or m % i == 0:
            return 0
    return 1

Q = int(input())
MAX = 10 ** 5 + 1
prime = [0] * MAX
for i in range(3, MAX):
    prime[i] = prime[i-1] + isPrime(i)
ans = []
for _ in range(Q):
    l, r = map(int, input().split())
    ans.append(prime[r] - prime[l-1])
for a in ans:
    print(a)
### BUGGY CODE ###

N, M = [int(x) for x in input().split(" ")]
S = input()
T = input()

N = len(S)
M = len(T)


def gcd(a, b):
    if (a < b):
        return gcd(b, a)
    if a % b == 0:
        return b
    else:
        return gcd(b, a % b)


def maxkobai(a, b):
    return a * b // gcd(a, b)


#print(gcd(N, M))
#print(maxkobai(N, M))


L = maxkobai(N, M)
ret = L
x = ['-' for i in range(L+1)]
#x = ['-'] * (L+1)

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]

# print(x)

for m in range(0, M):
    idx = m * (L // M) + 1
    x_idx = x[idx]
    if x_idx != '-' and x_idx != T[m]:
        ret = -1
        break

print(ret)

### FIXED CODE ###

N, M = [int(x) for x in input().split(" ")]
S = input()
T = input()

N = len(S)
M = len(T)


S = [ord(c) for c in S]
T = [ord(c) for c in T]


def gcd(a, b):
    if a < b:
        a, b = b, a
    while b:
        a, b = b, a % b
    return a


def maxkobai(a, b):
    return a * b // gcd(a, b)


L = maxkobai(N, M)
ret = L
x = dict()

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]


for m in range(0, M):
    idx = m * (L // M) + 1
    tmp = x.get(idx, 0)

    if tmp != T[m] and tmp != 0:
        ret = -1
        break

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

import sys
import time
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N, Q = MAP()
S = input().rstrip()
LR = [MAP() for _ in range(Q)]

loc = [0]*N
#start = time.time()
for i in range(N-1):
	if S[i]+S[i+1] == 'AC': loc[i] += 1
#print(loc)
#elapsed_time = time.time() - start
#print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

#start = time.time()
for l, r in LR:
	print(sum(loc[l-1:r-1]))
	#tmp = (loc[r-1]-loc[l-1])
#elapsed_time = time.time() - start
#print("elapsed_time:{0}".format(elapsed_time) + "[sec]")

### FIXED CODE ###

import sys
import time
sys.setrecursionlimit(10**6)
if sys.platform in (['ios','darwin','win32']):
	sys.stdin=open('Untitled.txt')
input = sys.stdin.readline
def INT(): return int(input())
def MAP(): return [int(s) for s in input().split()]

N, Q = MAP()
S = input().rstrip()
LR = [MAP() for _ in range(Q)]

loc = [0]*N
for i in range(N-1):
	if S[i]+S[i+1] == 'AC':
		loc[i+1] += loc[i]+1
	else:
		loc[i+1] = loc[i]
#print(loc)

for l, r in LR:
	print(loc[r-1]-loc[l-1])
### BUGGY CODE ###

N = int(input())
s = ['']*N
ans = 0
for i in range(N):
    s[i] = sorted(input())
    if i != 0:
        for j in range(i):
#            print(i, j)
            if s[i] == s[j]:
                ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
s = [''.join(sorted(input())) for i in range(N)]

ans = 0
d = {}
for i in s:
    if i in d:
        ans += d[i]
        d[i] += 1
    else:
        d[i] = 1
print(ans)