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

import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = II()
a = LI()

b = [0]*(n+1)
for i in set(a):
    c = a.count(i)
    b[i] += (c*(c-1)/2)
for i in a:
    print(int(sum(b) - (a.count(i)-1)))

### FIXED CODE ###

import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 7)

def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
# 入力全てを整数に変換したものの配列を受け取る
def LI(): return list(map(int, sys.stdin.readline().split()))
# 入力全てを整数に変換して1引いたものの配列を受け取る
def LLI(rows_number): return [LI() for _ in range(rows_number)]

n = II()
a = LI()

b = [0]*(n+1)
count = 0
for i in range(n):
    b[a[i]] += 1
for i in range(n+1):
    count += b[i]*(b[i]-1)/2
for i in a:
    print(int(count-b[i]+1))
### BUGGY CODE ###

import math
N =int(input())
for i in range(N):
  count = 0
  M = int(math.sqrt(i+1))
  for j in range(M):
    for k in range(M):
      for l in range(M):
        if((j+1)**2 + (k+1)**2 + (l+1)**2 + (j+1)*(k+1) + (k+1)*(l+1) + (l+1)*(j+1) == i+1):
          count+=1
        if ((j+1)**2 + (k+1)**2 + (l+1)**2 + (j+1)*(k+1) + (k+1)*(l+1) + (l+1)*(j+1) > i+1):
          break
  print(count)

### FIXED CODE ###

import math
N = int(input())
ans_list = [0 for i in range(N)]
index = int(math.sqrt(N))

for x in range(1,index):
  for y in range(1,index):
    for z in range(1,index):
      n = x**2 + y**2 + z**2 + x*y + y*z + z*x 
      if (n <= N):
        ans_list[n-1] += 1
for i in range(N):
  print(ans_list[i])
### BUGGY CODE ###

import math

def bisearch(function, ok, ng):
    tmp = 0
    while abs(ok-ng) > 1:
        mid = (ok + ng)//2
        ans = function(mid)
        if ans > tmp:
            ok = mid
        else:
            ng = mid
        print("mid:{}".format(mid))
        tmp = ans
    return ok

def calc(x):
    return (math.floor(A*x/B) - A*math.floor(x/B))

A, B, N = map(int, input().split())
ok = N
ng = 0

# print(bisearch(calc, ok, ng))
ans = []
tmp = calc(1)
for i in range(1, N+1):
    a = calc(i)
    ans.append(a)
    if tmp > a:
        break
    tmp = a

print(max(ans))

### FIXED CODE ###

import math

def calc(x):
    return (math.floor(A*x/B) - A*math.floor(x/B))

A, B, N = map(int, input().split())
print(calc(min(B-1, N)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)


k = int(input())
number = 9

ans = 0
for i in range(10,10**7):
    check = 'OK'
    l = len(str(i))
    keta = list(str(i))
    for j in range(l-1):
        if abs(int(keta[j]) - int(keta[j+1])) <= 1:
            pass
        else:
            check = 'NG'
    if check == 'OK':
        number += 1
        if number == k:
            ans = i
            break
if k <= 9:
    print(k)
else:
    print(ans)


### FIXED CODE ###

k = int(input())
ans = [i for i in range(1,10)]

i = 0

for i in range(k):
    now = ans[i]
    if str(now)[-1] == '0':
        ans.append(now*10)
        ans.append(now*10+1)
    elif str(now)[-1] == '9':
        ans.append(now*10+8)
        ans.append(now*10+9)
    else:
        ans.append(now*10+now%10-1)
        ans.append(now*10+now%10)
        ans.append(now*10+now%10+1)
    if len(ans) > k:
        break

print(ans[k-1])
### BUGGY CODE ###

def abc161_C(N,K):
    if K == 1:
        return print(0)
    Min = 0
    diff_list = [N]
    while 1:
        diff = abs(N - K)
        N = diff
        if diff in diff_list:
            return print(min(diff_list))
        elif diff == 0:
            return print(0)
        else:
            diff_list.append(diff)
            
    
N,K = map(int,input().split())
abc161_C(N,K)

### FIXED CODE ###

def abc161_C(N,K):
    if K == 1:
        return print(0)
    Min = 0
    N = N%K
    diff_list = [N]
    while 1:
        diff = abs(N - K)
        N = diff
        if diff in diff_list:
            return print(min(diff_list))
        elif diff < K/2:
            diff_list.append(diff)
            return print(min(diff_list))
        else:
            diff_list.append(diff)
    
N,K = map(int,input().split())
abc161_C(N,K)
### BUGGY CODE ###

n,q = map(int,input().split())
S = input()
l = 0
r = 0

for i in range(q):
  l,r = map(int,input().split())
  ans = S[l-1:r].count("AC")
  print(ans)
  

### FIXED CODE ###

n,q=(map(int,input().split()))
s=input()
count=0
c=[0]*n
for i in range(1,n):
        if s[i-1]=='A':
            if s[i]=='C':
               count+=1
        c[i]=count
for _ in range(q):
    l,r=(map(int,input().split())) 
    print(c[r-1]-c[l-1])
### BUGGY CODE ###

X=input()

for i in range(int(len(X)/2)):
    s=X.find('ST')
    if s==-1:
        break
    else:
        X=X[:s]+X[s+2:]

print(len(X))

### FIXED CODE ###

X=input()

ans=0
for i in range(len(X)):
    if X[i]=='S':
        ans+=1
    else:
        if ans==0:
            ans=0
        else:
            ans-=1
print(ans*2)
### BUGGY CODE ###

def main120():
    import sys
    S_org = input()
    S = []

    for s in range(len(S_org)):
        S.append(S_org[s])
    S = list(map(int, S))

    cont = True
    index = 0
    count = 0

    if len(S) == 1:
        print(0)
        sys.exit()

    else:
        while(cont):
            if S[index] == S[index+1]:
                index += 1
            else:
                count += 2
                S.pop(index)
                S.pop(index)
                index = 0
    
            if index == len(S) - 2:
                if S[index] != S[index+1]:
                    count += 2
                print(count)
                sys.exit()


main120()

### FIXED CODE ###

def main120():
    import sys
    S_org = input()
    S = []

    for s in range(len(S_org)):
        S.append(S_org[s])
    S = list(map(int, S))

    cont = True
    index = 0
    count = 0

    if len(S) == 1:
        print(0)
        sys.exit()

    else:
        while(cont):
            if S[index] == S[index+1]:
                index += 1
            else:
                count += 2
                S.pop(index)
                S.pop(index)
                if index > 0:
                    index -= 1

            if index == len(S) - 2:
                if S[index] != S[index+1]:
                    count += 2
                print(count)
                sys.exit()


main120()
### BUGGY CODE ###

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

cnt = 1

for i in range(len(P)):
    for j in range(0, i):
        if P[i] <= P[j]:
            if i == j+1:
                cnt += 1
            pass
        else:
            break

print(cnt)

### FIXED CODE ###

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

cnt = 0
mini = float('inf')

for i in range(0, len(P)):
    if P[i] < mini:
        cnt += 1
        mini = P[i]

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

#!/usr/bin/env python3
import sys

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    mLEN = len(format(max(A),'b'))
    bA = [[0]*N for _ in range(mLEN)]

    for i in range(N):
        a = format(A[i],'b').zfill(mLEN)
        for k in range(mLEN):
            bA[k][i] = a[k]

    answer = 0
    for keta in range(mLEN):
        zero = bA[keta].count('0')
        one = N-zero
        a = 0

        for i in range(N):
            if bA[keta][i] == '1':
                one -= 1
            else:
                zero -= 1

            if bA[keta][i] == '1':
                a += zero
            else:
                a += one
        answer += a*pow(2,mLEN-1-keta,MOD)
    
    print(answer%MOD)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import numpy as np

MOD = 1000000007  # type: int

def solve(N: int, A: "List[int]"):
    mLEN = len(format(max(A),'b'))

    A = np.array(A)
    ans = 0
    d = 1
    while d < (1 << mLEN):
        cnt = np.count_nonzero(A & d)
        ans += (N - cnt) * cnt * d
        ans %= MOD
        d <<= 1
    print(ans)
    return

def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, A)

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

s1 = input()
s2 = input()
list = s1

for i in range(len(list)):
    if s1[i] != s2[i]:
      s1 = s1.translate(str.maketrans( s1[i]+s2[i], s2[i]+s1[i]) )
    if s1[0:i] != s2[0:i]:
      break

if s1==s2:
  print ("Yes")
else:
  print ("No")


### FIXED CODE ###

def translate(x,y):
    if x == y[0]:
      return y[1]
    if x == y[1]:
      return y[0]
    return x

s1 = list(input())
s2 = list(input())
list = s1

count = 0
for i in range(len(list)):
    if s1[i] != s2[i]:
      x = s1[i]
      y = s2[i]
      for j in range(len(s1)):
        if s1[j] == x:
          s1[j]=y
        elif s1[j] == y:
          s1[j]=x
      #s1 = s1.translate(str.maketrans( s1[i]+s2[i], s2[i]+s1[i]) )
      #s1.replace( s1[i], "X").replace( s2[i], x).replace( 'X' , y)
      #s1 = list(map(translate, s1))
      
      count = count+1
    if count > 27:
      break

if s1==s2:
  print ("Yes")
else:
  print ("No")
### BUGGY CODE ###

import sys
import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import floyd_warshall

n, k, *ab = map(int, sys.stdin.buffer.read().split())
aaa = np.array(ab[0::2], dtype=np.int64) - 1
bbb = np.array(ab[1::2], dtype=np.int64) - 1
ccc = np.ones(n - 1, dtype=np.int64)
graph = csr_matrix((ccc, (aaa, bbb)), shape=(n, n))
dists = floyd_warshall(graph, directed=False)

if k % 2 == 0:
    print((dists > k // 2).sum(axis=0).min())
else:
    ans = n
    over = dists > k // 2
    for a, b in zip(ab[0::2], ab[1::2]):
        ans = min(ans, (over[a - 1] & over[b - 1]).sum())
    print(ans)


### FIXED CODE ###

import sys
from collections import deque


def bfs(links, s, limit):
    not_reachable = [True] * len(links)
    q = deque([(0, s, -1)])
    while q:
        cost, v, p = q.popleft()
        if cost > limit:
            break
        not_reachable[v] = False
        cost += 1
        q.extend((cost, u, v) for u in links[v] if u != p)
    return not_reachable


def solve(n, k, ab):
    if k == 1:
        return n - 2

    links = [set() for _ in range(n)]
    for a, b in zip(ab[0::2], ab[1::2]):
        a -= 1
        b -= 1
        links[a].add(b)
        links[b].add(a)

    ans = n
    thr = k // 2
    if k % 2 == 0:
        ans = min(sum(bfs(links, v, thr)) for v in range(n))
    else:
        dists = [bfs(links, v, thr) for v in range(n)]
        for a, b in zip(ab[0::2], ab[1::2]):
            a -= 1
            b -= 1
            ans = min(ans, sum(d1 and d2 for d1, d2 in zip(dists[a], dists[b])))
    return ans


n, k, *ab = map(int, sys.stdin.buffer.read().split())
print(solve(n, k, ab))
### BUGGY CODE ###

import itertools

n = int(input())
sin = [''.join(sorted(input())) for _ in range(n)]

ans = []

for i in set(sin):
    if sin.count(i)  > 1:
        combi = list(itertools.combinations(range(sin.count(i)), 2))
        ans.append(len(combi))

print(sum(ans))


### FIXED CODE ###

from collections import Counter

n = int(input())
sin = [''.join(sorted(input())) for _ in range(n)]

ans = 0

for i in Counter(sin).values():
    ans += i*(i-1) //2
print(ans)
### BUGGY CODE ###

n = int(input())

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

checked = []
zipped = zip(list(range((10**5+1))), [0]*(10**5+1))
nums = dict(zipped)
for i in a:
  if i not in checked:
    nums[i] = a.count(i)
    checked.append(i)
  
  
totals = [0] * (10**5 + 1)
for i in nums:
  if i == 0:
    totals[0] = nums[0] + nums[1]
  elif i == (10**5):
    totals[0] = nums[10**5-1] + nums[10**5]
  else:
    totals[i] = nums[i-1] + nums[i] + nums[i+1]
  
  
print(max(totals))  

### FIXED CODE ###

n = int(input())

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

d = {}

for i in a:
  for j in range(i - 1, i + 2): #aの値の両隣まで
    d[j] = d.get(j, 0) + 1#getは第一引数で指定したキーがなかったら第二引数で指定した値を戻す
    
    
print(max(d.values()))
### BUGGY CODE ###

K = int(input())

if K % 2 == 0:
    print(-1)

for i in range(1, 10**5):
    n = "7" * i
    n = int(n)
    if n % K == 0:
        print(i)
        exit()
print(-1)

### FIXED CODE ###

K = int(input())

# k_keta = len(str(K))
# print(k_keta)

#偶数は弾く
if K % 2 == 0:
    print(-1)
    exit()

r = 0
for i in range(1, 10**6): #何回目のループか
    r = (10 * r + 7) % K
    if r % K == 0:
        print(i)
        break
else:
    print(-1)
### BUGGY CODE ###

n = int(input())
ans = n

i = 2
while i <= n:
    if n%i == 0:
        ans = ans//i*(i-1)
        while n%i == 0:
            n //= i
    i+=1

print(ans)

### FIXED CODE ###

n = int(input())
ans = n

i = 2
while i*i <= n:
    if n%i == 0:
        ans = ans//i*(i-1)
        while n%i == 0:
            n //= i
    i+=1
if n != 1:
    ans = ans//n*(n-1)

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

import sys
input = sys.stdin.readline

max_size = 2*10**4 + 1
h, n = map(int, input().split())
DP = [float('INF')] * max_size
DP[0] = 0

for _ in range(n):
    damage, cost = map(int, input().split())
    for idx in range(damage, max_size):
        DP[idx] = min(DP[idx], DP[idx-damage] + cost)

print(min(DP[h:]))


### FIXED CODE ###

import sys
input = sys.stdin.readline

max_size = 2*10**4 + 1
h, n = map(int, input().split())
DP = [float('INF')] * max_size
DP[0] = 0

for _ in range(n):
    damage, cost = map(int, input().split())
    for idx in range(damage, max_size):
        DP[idx] = min(DP[idx], DP[idx-damage] + cost)

print(min(DP[h:]))
### BUGGY CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    N = int(input())
    A = [int(i) for i in input().split()]
    Q = int(input())
    BC = []
    for i in range(Q):
        BC.append(list(map(int, input().split())))
    dic = Counter(A)
    for i in BC:
        B, C = i[0], i[1]
        dic[C] += dic[B]
        dic[B] = 0
        ans = 0
        for k, v in dic.items():
            ans += int(k)*v
        print(ans)

resolve()

### FIXED CODE ###

def resolve():
    import sys
    input = sys.stdin.readline
    from collections import Counter
    N = int(input())
    A = [int(i) for i in input().split()]
    Q = int(input())
    BC = []
    for i in range(Q):
        BC.append(list(map(int, input().split())))
    dic = Counter(A)
    ans = 0
    for k, v in dic.items():
        ans += int(k)*v
    for i in BC:
        B, C = i[0], i[1]
        ans += - B*dic[B] + C*dic[B]
        dic[C] += dic[B]
        del dic[B]
        print(ans)

resolve()
### BUGGY CODE ###

# -*- coding:utf-8 -*-
n = int(input())
a = list(map(int,input().split()))
b = []
for tmp in a:
    b.append(tmp)
    b.reverse()
b = map(str,b)
print(" ".join(b))

### FIXED CODE ###

# -*- coding:utf-8 -*-
from collections import deque
def odd(num):
    return True if num%2!=0 else False
n = int(input())
a = list(input().split())
b = deque()
for tmp in range(len(a)):
    if odd(n) == odd(tmp+1):
        b.appendleft(a[tmp])
    else:
        b.append(a[tmp])
print(' '.join(b))
### BUGGY CODE ###

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

h, w = map(int, input().split())
painted = [list(input()) for _ in range(h)]
starts = []
for y in range(h):
    for x in range(w):
        if painted[y][x] == '#':
            starts.append((y, x))


def paint_black(starts):
    que = deque()
    for start in starts:
        que.append(start)
    cnt = 0
    while not all([i == '#' for row in painted for i in row]):
        next_position = []
        cnt += 1
        while que:
            y, x = que.popleft()
            for iy, ix in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                ny = y + iy
                nx = x + ix
                if (0 <= ny < h) and (0 <= nx < w):
                    if painted[ny][nx] != '#':
                        painted[ny][nx] = '#'
                        next_position.append((ny, nx))

        for start in next_position:
            que.append(start)
    return cnt

cnt = paint_black(starts)
print(cnt)

### FIXED CODE ###

import sys

input = sys.stdin.readline


def main():
    h, w = map(int, input().split())
    # 蛮兵
    painted = [['#'] * (w + 2)]
    painted += [['#'] + list(input().rstrip()) + ['#'] for _ in range(h)]
    painted.append(['#'] * (w + 2))
    que = []

    for y in range(1, h + 1):
        for x in range(1, w + 1):
            if painted[y][x] == '#':
                painted[y][x] = 0
                que.append((y, x))
    while que:
        qq = []
        for y, x in que:
            if painted[y - 1][x] == '.':
                painted[y - 1][x] = painted[y][x] + 1
                qq.append((y - 1, x))
            if painted[y + 1][x] == '.':
                painted[y + 1][x] = painted[y][x] + 1
                qq.append((y + 1, x))
            if painted[y][x + 1] == '.':
                painted[y][x + 1] = painted[y][x] + 1
                qq.append((y, x + 1))
            if painted[y][x - 1] == '.':
                painted[y][x - 1] = painted[y][x] + 1
                qq.append((y, x - 1))
        que = qq

    print(painted[y][x])


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

from scipy.special import comb


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

A.sort()
n = A[-1]

before_cmb = -1
max_cmb = -1
r = 0
for i in range(N):
    tmp_cmb = comb(n, A[i], exact=True)
    if max_cmb < tmp_cmb:
        max_cmb = tmp_cmb
        r = A[i]

    if before_cmb == -1:
        before_cmb = tmp_cmb
    elif before_cmb >= tmp_cmb:
        break

    before_cmb = tmp_cmb
print(n, r)


### FIXED CODE ###

import bisect

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

A.sort()
n = A[-1]
mid = bisect.bisect(A, n/2)

if abs(n/2-A[mid-1]) > abs(n/2-A[mid]):
    print(n, A[mid])
else:
    print(n, A[mid-1])
### BUGGY CODE ###

print(min(eval('sum(map(int,input().split())),'*int(input()))))

### FIXED CODE ###

n,*t=map(int,open(0).read().split());print(sum(sorted(zip(t[::2],t[1::2]))[-1]))
### BUGGY CODE ###

n = int(input())
s = input()

c=0
for k in range(n):
    for j in range(n):
        if j>=k:
            break
        for i in range(n):
            if i>=j:
                break
            if (s[i]!=s[j]) and (s[j]!=s[k]) and (s[i]!=s[k]) and ((j-i)!=(k-j)):
                c+=1

print(c)


### FIXED CODE ###

n = int(input())
s = input()

t="RGBRGB"

c=0
cm=0
for i in range(3):
    for j in range(1,n-1):
        if s[j]==t[i] :
            low = s[:j].count(t[i+1])
            high = s[j:].count(t[i+2])
            c += low*high
            low = s[:j].count(t[i+2])
            high = s[j:].count(t[i+1])
            c += low*high
            for k in range(1,j+1):
                if j+k>n-1 :
                    break
                if s[j-k]!=t[i] and s[j+k]!=t[i] and s[j-k]!=s[j+k]:
                    cm+=1


print(c-cm)
### BUGGY CODE ###

n, m = map(int, input().split())
li_input = list()
cities = dict()

for i in range(m):
    li_input.append(list(map(int, input().split())))

for pref in {i[0] for i in li_input}:
    t_city = list(filter(lambda x: x[0] == pref, li_input))
    for idx, city in enumerate(sorted(t_city, key=lambda x: x[1]), start=1):
        cities[str(city[1])] = idx

for c in li_input:
    print('{0:06}{1:06}'.format(c[0], cities[str(c[1])]))


### FIXED CODE ###

n, m = map(int, input().split())
li_input = list()
counter = dict()
cities = dict()

for i in range(m):
    li_input.append(list(map(int, input().split())))

sorted_city = sorted(li_input, key=lambda x: x[1])

for c in sorted_city:
    idx = counter.get(c[0], 0)
    cities[c[1]] = idx

    # count up
    counter[c[0]] = idx + 1


for c in li_input:
    print('{0:06}{1:06}'.format(c[0], cities[c[1]] + 1))
### BUGGY CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
for i, p in enumerate(P):
    G[p].append(i+1)
Q = [None]*(N+1)
A = [None]*(N+1)
for i in range(N, -1, -1):

    # 子ノードのdequeを集める
    R = None
    for j in G[i]:
        S = Q[j]
        if not R:
            R = S
            continue

        # |R| > |S|
        if len(R) < len(S):
            R, S = S, R

        # dequeの小さい方から大きい方へマージする処理
        for s, r in zip(S, R):
            a0, a1, a2, c0 = s
            b0, b1, b2, c1 = r
            r[0] = a0*b0 % MOD
            r[1] = (a0*b1 + a1*b0) % MOD
            r[2] = (a0*b2 + a1*b1 + a2*b0 + a1*b2 + a2*b2 + a2*b1) % MOD
            r[3] = c0+c1

    k = len(G[i])
    if k:
        r = [[pow(2, k, MOD) - k, k, 0, k]]
    else:
        r = []
    if R:
        # a0 <- a2
        for e in R:
            e[0] += e[2]
            e[2] = 0
        r.extend(R)
        Q[i] = r
    else:
        Q[i] = r
ans = pow(2, N, MOD)
for a0, a1, a2, c in Q[0]:
    ans += pow(2, N+1-c, MOD) * a1 % MOD
print(ans % MOD)

### FIXED CODE ###

# seishin.py
from collections import deque
N = int(input())
*P, = map(int, input().split())
MOD = 10**9 + 7

G = [[] for i in range(N+1)]
U = [0]*(N+1)
C = [0]*(N+1)
for i, p in enumerate(P):
    G[p].append(i+1)
    U[i+1] = u = U[p]+1
    C[u] += 1
Q = [None]*(N+1)
PP = {}
def pp(k):
    if k not in PP:
        PP[k] = p = pow(2, k, MOD)
        return p
    return PP[k]
L = [0]*(N+1)

ept = []
sz = L.__getitem__
for i in range(N, -1, -1):
    g = G[i]
    if not g:
        continue

    # 子ノードのdequeを集める
    g.sort(key=sz, reverse=1)
    k = len(g)
    e = [pp(k) - k, k, 0]

    g0 = g[0]
    L[i] = L[g0] + 1
    if L[g0] == 0:
        Q[i] = deque([e])
        continue
    Q[i] = R = Q[g0]
    if k > 1:
        # a0 <- a2
        for s, r in zip(Q[g[1]] or ept, R):
            r[0] += r[2]; r[2] = 0

        for j in g[1:]:
            S = Q[j]
            if not S:
                break

            # dequeの小さい方から大きい方へマージする処理
            for (a0, a1, a2), r in zip(S, R):
                b0, b1, b2 = r; a0 += a2
                r[0] = a0*b0 % MOD
                r[1] = (a0*b1 + a1*b0) % MOD
                r[2] = ((a0+a1)*b2 + a1*b1) % MOD
    R.appendleft(e)
print((pp(N) + sum(pp(N+1-c) * a1 % MOD for (a0, a1, a2), c in zip(Q[0], C[1:]))) % MOD)
### BUGGY CODE ###

N,Q = map(int,input().split())
line = list(input())
for i in range(Q):
    l,r = map(int,input().split())
    count = 0
    for i in range(l-1,r-1):
        if line[i] == 'A' and line[i+1] == 'C':
            count += 1
    print(count)

### FIXED CODE ###

N,Q = map(int,input().split())
S = input()
AC_cnt = [0] * N
for i in range(N-1):
  if S[i] == 'A' and  S[i+1] == 'C':
    AC_cnt[i+1] = AC_cnt[i] + 1
  else:
    AC_cnt[i+1] = AC_cnt[i]

for i in range(Q):
  begin, end = map(int,input().split())
  print(AC_cnt[end-1]-AC_cnt[begin-1])
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline
 
n = int(input())
l = list(map(int, input().split()))
l.sort()

cnt = 0
for i in range(n):
  for j in range(n-i-1):
    cnt += bisect.bisect_left(l[j+i+2:], l[i] + l[j+i+1])
    
print(cnt)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
 
n = int(input())
l = [int(li) for li in input().split(' ')]
l.sort()

cnt = 0
for i in range(n):
  for j in range(i+1, n):
    cnt += bisect.bisect_left(l, l[i]+l[j])-j-1
    
print(cnt)
### BUGGY CODE ###

K,S = input().split()
count = 0

for x in range(int(K)+1):
  for y in range(int(K)+1):
    for z in range(int(K)+1):
      if x+y+z== int(S):
        count+=1

print(count)

### FIXED CODE ###

K,S = [int(x) for x in input().split()]
count = 0

for x in range(int(K)+1):
  for y in range(int(K)+1):
    if 0<=S-x-y<=K:
      count+=1


print(count)