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

#
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def next_kenp(node, edges, dones):
    nodes = set()
    nodes2 = set()
    for n1 in edges[node]:
        for n2 in edges[n1]:
            if n2 not in nodes2:
                nodes2.add(n2)

    for nn in nodes2:
        for n3 in edges[nn]:
            if n3 in dones or n3 in nodes:
                continue
            nodes.add(n3)
    return nodes


def main():
    n, m = map(int, input().split())

    edges = defaultdict(list)

    for _ in range(m):
        u, v = map(int, input().split())
        edges[u].append(v)

    s, t = map(int, input().split())

    dones = set()
    que = deque()
    que.append((s, 0))
    while que:
        node, step = que.popleft()
        next_nodes = next_kenp(node, edges, dones)
        for n in next_nodes:
            if n == t:
                print(step + 1)
                exit()

            if n not in dones:
                que.append((n, step + 1))
                dones.add(n)
    print(-1)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#
import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect
from heapq import heappush, heappop


def main():
    n, m = map(int, input().split())

    edges = defaultdict(list)

    for _ in range(m):
        u, v = map(int, input().split())
        edges[(u, 0)].append((v, 1))
        edges[(u, 1)].append((v, 2))
        edges[(u, 2)].append((v, 0))

    s, t = map(int, input().split())

    # print(new_edges)

    dones = set()
    que = deque()
    que.append(((s, 0), 0))
    while que:
        node, step = que.popleft()

        next_nodes = edges[node]
        # print(next_nodes)
        for n, l in next_nodes:
            if n == t and l == 0:
                print((step + 1) // 3)
                exit()

            if (n, l) not in dones:
                que.append(((n, l), step + 1))
                dones.add((n, l))
    print(-1)


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

R,G,B,N = map(int,input().split())
count = 0
for r in range(N//R+1):
  for g in range((N-R*r)//G+1):
    if (N-R*r-G*g)%B == 0 and (N-R*r-G*g) > -1:
      count += 1
print(count)



### FIXED CODE ###

R,G,B,N = map(int,input().split())
cnt = 0
for r in range(N//R+1):
  for g in range((N-R*r)//G+1):
    if (N-R*r-G*g)%B == 0:
      cnt += 1
print(cnt)
### BUGGY CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect

INF = 10**9+7

if __name__ == "__main__":
    k = int(input())
    if k%2 == 0:
        print(-1)
        sys.exit()
    a = 7
    p = len(str(k)) + 1
    for i in range(p+10**5):
        if a%k == 0:
            print(i+1)
            sys.exit()
        a*=10
        a+=7
    print(k-1)

### FIXED CODE ###

import sys
import itertools
sys.setrecursionlimit(1000000000)
from heapq import heapify,heappop,heappush,heappushpop
import math
import collections
import copy
import bisect

INF = 10**9+7

if __name__ == "__main__":
    k = int(input())
    if k%2 == 0:
        print(-1)
        sys.exit()
    cnt = 1
    a = 7
    d = [a]
    for i in range(10**6+1):
        if d[i]%k == 0:
            print(i+1)
            sys.exit()
        b = 10*d[i]
        b%=k
        b+=7
        b%=k
        d.append(b)
    print(-1)
### BUGGY CODE ###

N,Y = input().split()
N = int(N)
Y = int(Y)

for a in range(N+1):
  for b in range(N+1):
    X = 10000*a + 5000*b + 1000*(N-int(a)-int(b))
    c = N-int(a)-int(b)
    if X==Y and c>=0:
      #print(X)
      break
  else:
    continue
  break
if c<0:
  a=b=c=-1
print(a,b,c)


### FIXED CODE ###

N, Y = map(int, input().split())
for x in range(N+1):
    for y in range(N-x+1):
        z = N-x-y
        if 0 <= z <= 2000 and 10000*x+5000*y+1000*z == Y:
            print(x, y, z)
            exit()
print(-1, -1, -1)
### BUGGY CODE ###

N, M = map(int, input().split())
li = list(map(int, input().split()))
for i in range(M):
  MAX = max(li)
  li[li.index(MAX)] = MAX // 2
print(sum(li))


### FIXED CODE ###

import heapq
N, M = map(int, input().split())
li = list(map(lambda x:int(x) * (-1), input().split()))
heapq.heapify(li)
for i in range(M):
  max_price = heapq.heappop(li)*(-1)
  heapq.heappush(li, (-1) * (max_price // 2))
print(-sum(li))
### BUGGY CODE ###

import re
s = input()
cnt = 0
while 'ABC' in s:
    s = re.sub(r'ABC', 'BCA', s, count=1)
    cnt += 1

print(cnt)

### FIXED CODE ###

import re
s = input()
sub = re.sub('BC', 'X', s)

ans = 0
a = 0
for i in range(len(sub)):
    if sub[i] == 'A':
        a += 1
    elif sub[i] == 'X':
        ans += a
    else:
        a = 0

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

A,B,M = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
p = [i+j for i in a for j in b]
for _ in range(M):
    x,y,c = map(int,input().split())
    p.append(a[x-1]+b[y-1]-c)

print(min(p))

### FIXED CODE ###

A,B,M = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
p = [min(a) + min(b)]
for _ in range(M):
    x,y,c = map(int,input().split())
    p.append(a[x-1]+b[y-1]-c)

print(min(p))
### BUGGY CODE ###

# Aizu Problem 0223: Stray Twins

import sys, math, os, bisect
from queue import Queue

# read input:
PYDEV = os.environ.get('PYDEV')
if PYDEV=="True":
    sys.stdin = open("sample-input.txt", "rt")


def stray_twins(W, H, grid, tx, ty, kx, ky):
    moves = [[1, 0], [-1, 0], [0, 1], [0, -1]]
    Q = Queue()
    Q.put((tx, ty, kx, ky, 0))
    visited = set()
    while not Q.empty():
        tx, ty, kx, ky, t = Q.get()
        visited.add((tx, ty, kx, ky))
        if t >= 100:
            return "NA"
        if tx == kx and ty == ky:
            return t
        for dy, dx in moves:
            dtx = max(0, min(tx + dx, W - 1))
            dty = max(0, min(ty + dy, H - 1))
            dkx = max(0, min(kx - dx, W - 1))
            dky = max(0, min(ky - dy, H - 1))
            if grid[dty][dtx] == 1:
                dtx, dty = tx, ty
            if grid[dky][dkx] == 1:
                dkx, dky = kx, ky
            if (dtx, dty, dkx, dky) not in visited:
                Q.put((dtx, dty, dkx, dky, t + 1))
    
while True:
    W, H = map(int, input().split())
    if W == H == 0:
        break
    tx, ty = [int(_) - 1 for _ in input().split()]
    kx, ky = [int(_) - 1 for _ in input().split()]
    grid = [[int(_) for _ in input().split()] for __ in range(H)]
    print(stray_twins(W, H, grid, tx, ty, kx, ky))

### FIXED CODE ###

from Queue import Queue
mv=((-1,0),(1,0),(0,-1),(0,1))
while True:
    X,Y=map(int,raw_input().split())
    if X==Y==0:break
    tx,ty=map(int,raw_input().split())
    kx,ky=map(int,raw_input().split())
    tx,ty,kx,ky=tx-1,ty-1,kx-1,ky-1
    D=[map(int,raw_input().split()) for i in range(Y)]
    Q=Queue()
    Q.put((tx,ty,kx,ky,0))
    visited=set()
    visited.add((tx,ty,kx,ky))
    while not Q.empty():
        tx,ty,kx,ky,t=Q.get()
        if t>=100:
            print "NA"
            break
        if tx==kx and ty==ky:
            print t
            break
        for i in range(4):
            dtx,dty=tx+mv[i][0],ty+mv[i][1]
            dkx,dky=kx-mv[i][0],ky-mv[i][1]
            if dtx<0 or dtx>=X or dty<0 or dty>=Y:
                dtx,dty=tx,ty
            if dkx<0 or dkx>=X or dky<0 or dky>=Y:
                dkx,dky=kx,ky
            if D[dty][dtx]==1:
                dtx,dty=tx,ty
            if D[dky][dkx]==1:
                dkx,dky=kx,ky
            if (dtx,dty,dkx,dky) not in visited:
                visited.add((dtx,dty,dkx,dky))
                Q.put((dtx,dty,dkx,dky,t+1))
    else:
        print "NA"
### BUGGY CODE ###

# B - One Clue
def main():
    count = int(input())
    data = []
    for i in range(count):
        data.append(''.join(sorted(str(input()))))

    my_dict = {i: data.count(i) for i in data}
    print(sum([sum(range(l)) for l in list(my_dict.values())]))

if __name__ == "__main__":
    main()
    

### FIXED CODE ###

# C - Green Bin
def main():
    count = 0
    dictCount = {}
    for i in [input() for i in range(int(input()))]:
        strInput = ''.join(sorted([c for c in i]))
        if strInput in dictCount:
            count += dictCount[strInput]
            dictCount[strInput] += 1
        else:
            dictCount[strInput] = 1
    print(count)

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

N=int(input())
a=list(map(int,input().split()))
p=0
for i in range(N-1):
	for j in range(i+1,N):
		if a[i]==a[j]:
			p=1
if p==0:
	print('YES')
else:
	print('NO')

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
a=sorted(a)
p=0
for i in range(N-1):
	if a[i]==a[i+1]:
		p=1
if p==0:
	print('YES')
else:
	print('NO')
### BUGGY CODE ###

from collections import defaultdict

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

count = defaultdict(int)
for i in balls:
  count[i] += 1

def cmb(M):
  return M*(M-1)//2

sum = defaultdict(int)
for i in count:
  for j in count:
    if i==j:
      sum[i] += cmb(count[j]-1)
    else:
      sum[i] += cmb(count[j])
      
for i in balls:
  print(sum[i])

  
    

### FIXED CODE ###

from collections import defaultdict

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

count = defaultdict(int)
for i in balls:
  count[i] += 1

def cmb(M):
  return M*(M-1)//2

sum = 0
for i in count:
   sum += cmb(count[i])
#sum = defaultdict(int)
#for i in count:
#  for j in count:
#    if i==j:
#      sum[i] += cmb(count[j]-1)
#    else:
#      sum[i] += cmb(count[j])
#      
for i in balls:
  print(sum - (count[i]-1))
### BUGGY CODE ###

import numpy as np
sList, tList = input(), input()
dp = np.zeros((len(sList)+1, len(tList)+1), dtype=np.int16)


# 横方向で回す
for i, s in enumerate(sList, start=1):
    for j, t in enumerate(tList, start=1):
        dp[i][j] = np.max([dp[i][j - 1], dp[i-1][j],
                           dp[i-1][j-1] + 1 if s == t else 0])
m = dp[i][j]
ans = ""
# traceback
cnt = 0
while i + j != 0:
    if dp[i - 1][j - 1] == m - 1 and tList[j-1] == sList[i-1]:
        ans = tList[j-1] + ans
        i -= 1
        j -= 1
        m -= 1
    else:
        if dp[i - 1][j] == m:
            i -= 1
        elif dp[i][j-1] == m:
            j -= 1
    cnt += 1
print(ans)


### FIXED CODE ###


sList, tList = input(), input()

dp = [[0] * (len(tList) + 1) for _ in range(len(sList)+1)]


# 横方向で回す
for i, s in enumerate(sList, start=1):
    for j, t in enumerate(tList, start=1):
        dp[i][j] = max([dp[i][j - 1], dp[i-1][j],
                        dp[i-1][j-1] + 1 if s == t else 0])
m = dp[i][j]
ans = ""
# traceback
cnt = 0
while i + j != 0:
    if dp[i - 1][j - 1] == m - 1 and tList[j-1] == sList[i-1]:
        ans = tList[j-1] + ans
        i -= 1
        j -= 1
        m -= 1
    else:
        if dp[i - 1][j] == m:
            i -= 1
        elif dp[i][j-1] == m:
            j -= 1
    cnt += 1
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
p = []
for it in range(N):
    p.append(list(map(int,input().split())))
    
dp = [[0 for i in range(W+1)] for j in range(N+1)]
i = 0
for w, v in p:
    i += 1
    for w_limit in range(1, W+1):
        if w_limit < w:
            dp[i][w_limit]=dp[i-1][w_limit]
            continue
        if (dp[i-1][w_limit-w] + v) > dp[i-1][w_limit]:
            dp[i][w_limit] = dp[i-1][w_limit-w] + v
        else:
            dp[i][w_limit]=dp[i-1][w_limit]
print(max(max(dp)))

### FIXED CODE ###

N, W = map(int, input().split())

max_total = 0
p = []
for it in range(N):
    p.append(list(map(int,input().split())))
    max_total += p[-1][1]
    
    
MAX_WEIGHT = 1000000009
dp = [[MAX_WEIGHT for i in range(max_total+1)] for j in range(N+1)]
dp[0][0]=0
i = 0
for w, v in p:
    i += 1
    for target_val in range(0, max_total+1):
        
        if target_val-v >=0 and dp[i-1][target_val] > (dp[i-1][target_val-v]+w):
            dp[i][target_val] = dp[i-1][target_val-v]+w
        else:
            dp[i][target_val] = dp[i-1][target_val]
            
ret = 0
for v, w in enumerate(dp[N]):
    if w<=W and v>ret:
        ret = v
print(ret)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
l=[]
for i in range(m):
    b,c=map(int,input().split())
    l+=[c]*b
l.sort()
l=l[::-1]
ans=0
#print(a,l)
for i in range(n):
    if i<=len(l)-1:
        ans+=max(a[i],l[i])
    else:
        ans+=a[i]

print(ans)

### FIXED CODE ###

import sys
imput=sys.stdin.readline
n,m=map(int,input().split())
a=list(map(int,input().split()))
a.sort()
y=[list(map(int,input().split()))[::-1] for i in range(m)]
y.sort()
y=y[::-1]
#print(y)

l=[]
w=0
for i in range(m):
    w+=y[i][1]
    l+=[y[i][0]]*y[i][1]
    if w>=n:
        break

#print(l)
l=l[:n]
ans=0
#print(a,l)
for i in range(n):
    if i<=len(l)-1:
        ans+=max(a[i],l[i])
    else:
        ans+=a[i]

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

# -*- coding: utf-8 -*-
import sys 
from collections import deque
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, T = map(int, readline().split())
A = list(map(int,readline().split()))
B = sorted(A,reverse = True)

d = defaultdict(int)
for i in range(N-1):
    a = A[i]
    p = B[0] - a
    d[p] += 1
    B.remove(a)
d = sorted(d.items(),reverse=True)
print(d[0][1])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys 
from collections import deque
from collections import defaultdict
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, T = map(int, readline().split())
A = list(map(int,readline().split()))

### セグメント木
# 0-index
# N: 処理する区間の長さ
N0 = 2**(N-1).bit_length()
data = [0]*(2*N0)

# 初期化
def init(A):
    for i in range(N):
        data[i+N0-1] = A[i]
    for i in range(N0-2,-1,-1):
        data[i] = max(data[2*i+1],data[2*i+2])

# a_k の値を x に更新
def update(k, x):
    k += N0-1
    data[k] = x
    while k >= 0:
        k = (k - 1) // 2
        data[k] = max(data[2*k+1], data[2*k+2])

# 区間[l, r)の最小値
def query(l, r):
    L = l + N0; R = r + N0
    s = 0
    while L < R:
        if R & 1:
            R -= 1
            s = max(s, data[R-1])

        if L & 1:
            s = max(s, data[L-1])
            L += 1
        L >>= 1; R >>= 1
    return s

init(A)
d = defaultdict(int)
for i in range(N-1):
    a = A[i]
    high = query(i+1,N+1)
    p = high - a
    d[p] += 1
d = sorted(d.items(),reverse=True)
print(d[0][1])
### BUGGY CODE ###

l = [input() for _ in range(2)]
n = l[0]
S = l[1]
N = int(n)
count = 0

indexR = []
indexG = []
indexB = []

i = 0
j = 0
k = 0

for a in range(N):
    character = str(S)[a:a+1]

    if character == 'R':
        indexR.append(a+1)
    elif character == 'G':
        indexG.append(a+1)
    elif character == 'B':
        indexB.append(a+1)

for r in indexR:
    for g in indexG:
        for b in indexB:
            if abs(r-g) != abs(g-b) and abs(g-r) != abs(r-b) and abs(g-b) != abs(r-b):
                count = count + 1

print(count)

### FIXED CODE ###

from collections import Counter

N = int(input())
S = input()
cnt = Counter(S)

ans = cnt['R']*cnt['G']*cnt['B']
#まずansに要請１を満たす(i, j, k)の組の数を入れておき，ここから，要請２を満たさないものを除いていく。

for i in range(N-2):
    for j in range(i+1, N-1):
        k = j + (j - i)
        #kは　j - i = k - j を満たす。ただし，（i, j, k）が要請１を満たしているとは限らない。
        if k < N:
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -= 1

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

import heapq
def SME():
    A = [[x,i] for i,x in enumerate(Whole)]
    heapq.heapify(A)
    C = set([i for i in range(N)])
    D = set([])
    parameter = 0.99
    count = 0
    ANS = [None] * N
    for j in range(N) :
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    D.add(idx)
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in C.difference(D):
        if i < L : ANS[i] = min(Whole[:i+1])
        else : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = SME()
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

S = input()
init_len = len(S)

while True:
    cur_len = len(S)
    S = S.replace("01", "")
    S = S.replace("10", "")
    if len(S) == cur_len:
        print(init_len - cur_len)
        exit()


### FIXED CODE ###

S = list(input())

zero_S = S.count('0')
one_S = S.count('1')

print(min(zero_S, one_S) * 2)
### BUGGY CODE ###

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

ans = 0

for n in range(N):
    if n == 0:
        pass
    else:
        temp = H[0:n]
        if max(H[0:n]) - H[n] >= 2:
           ans += 1

if ans >= 1:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

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

ans = 'Yes'

for i in reversed(range(0, N-1)):
    if H[i] > H[i+1] + 1:
        ans = 'No'
    elif H[i] == H[i+1] + 1:
        H[i] -= 1

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

a=[input() for i in range(2)]

a_num=a[1]
a_num=a_num.split()

a_mul=1

for i in range(len(a_num)):
	num=int(a_num[i])
	a_mul*=num

if a_mul>10**18:
	a_mul=-1

print(a_mul)



### FIXED CODE ###

a=[input() for i in range(2)]

a_num=a[1]
a_num=a_num.split()
a_list=[int(n) for n in a_num]

a_mul=1

if 0 in a_list:
	print(0)

else:
	for i in a_list:
		a_mul*=i

		if a_mul>10**18:
			a_mul=-1
			break

	print(a_mul)
### BUGGY CODE ###

def solve(i, goal):
    # to decrese goal
    # then return boolean
    if goal == 0:
        return True
    elif i == n:
        return False
    else:
        return solve(i + 1, goal) or solve(i + 1, goal - A[i])

n = input() # parts total
A = map (int, raw_input().split()) # parts
q = input() # goal total
M = map (int, raw_input().split()) # goal

for j in xrange(q):
    goal = M[j]
    if solve(0, goal): # default
        print "yes"
    else:
        print "no"

### FIXED CODE ###

def solve(i, m):
    if m == 0:
        return True
    if n <= i or sum(A) < m:
        return False
    res = (solve(i+1, m) or solve(i+1, m-A[i]))
    return res

n = input()
A = map(int, raw_input().split())
q = input()
M = map(int, raw_input().split())

for m in M:
    if solve(0, m):
        print "yes"
    else:
        print "no"
### BUGGY CODE ###

n,m=map(int,input().split())
ans=0

if m%n==0:
    ans=m//n
else:
    for i in range(1,m//n +1)[::-1]:
        if m%i == 0 and m/i >= n:
            ans = i
            break
print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
m_root=int(m**0.5)
div_l=[]
ans=0

for i in range(1,m_root + 1):
    if m%i == 0:
        div_l.append(i)
        div_l.append(m//i)

if m//n in div_l:
    ans = m//n
else:
    div_l.append(m//n)
    div_l.sort()
    ans = div_l[div_l.index(m//n) - 1]
print(ans)
### BUGGY CODE ###

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

dist = []
dist.append(a[1]-a[0])

for num in range(1, len(a)):
  if num == len(a) - 1:
    dist.append(k-a[num]+a[0])
  else:
    dist.append(a[num+1]-a[num])
#print(dist)

min_index = [i for i, v in enumerate(dist) if v == min(dist)]

right = 0
left = 0
result = []
for start_index in min_index:
  for n in range(0, len(dist)-1):
    x = start_index + n
    y = start_index - n
    if x > len(dist)-1:
      x = (len(dist) - n - start_index) * -1
    if y < 0:
      y = len(dist)-n
    right += dist[x]
    left += dist[y]
  result.append(min(right, left))
  
print(min(result))

### FIXED CODE ###

import numpy as np

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

dist = []
dist.append(a[1]-a[0])

for num in range(1, len(a)):
  if num == len(a) - 1:
    dist.append(k-a[num]+a[0])
  else:
    dist.append(a[num+1]-a[num])
#print(dist)
dist = np.array(dist)

#min_index = np.where(dist == dist.min())[0]
s = np.sum(dist)
result = []
for start_index in range(0, len(dist)):
  if start_index == 0:
    result.append(s - dist[len(dist)-1])
    result.append(s - dist[start_index+1])
  elif start_index == len(dist)-1:
    result.append(s - dist[start_index-1])
    result.append(s - dist[0])
  else:
    result.append(s - dist[start_index-1])
    result.append(s - dist[start_index+1])
print(min(result))
### BUGGY CODE ###

S = input()

max_S = 10**9 + 7

N_Q = S.count("?")
N_C = S.count("C")

AQ_0 = int(3**N_Q)
AQ_1 = AQ_0 // 3
AQ_2 = AQ_1 // 3

BQ_0 = AQ_0//3
BQ_1 = AQ_1//3
BQ_2 = AQ_2//3


t_A = 0
t_Q = 0
if(S[0:1] == "C"):
    t_C = N_C - 1
else:
    t_C = N_C

ans = 0
for i in range(1, len(S)):
    if(S[i - 1:i] == "A"):
        t_A += 1
    elif(S[i - 1:i] == "?"):
        t_Q += 1

    bA = t_A
    bQ = t_Q
    if(S[i:i + 1] == "?"):
        aQ = N_Q - t_Q - 1
    else:
        aQ = N_Q - t_Q
    if(S[i:i + 1] == "C"):
        t_C -= 1
    aC = t_C

    if(S[i:i + 1] == "A" or S[i:i + 1] == "C"):
        continue
    elif(S[i:i+1] == "?"):
        Q_0 = BQ_0
        Q_1 = BQ_1
        Q_2 = BQ_2
    else:
        Q_0 = AQ_0
        Q_1 = AQ_1
        Q_2 = AQ_2

    ans += Q_0 * bA * aC + bQ * aQ * Q_2 + Q_1 * (bA * aQ + bQ * aC)
    ans = ans % max_S

print(ans)

### FIXED CODE ###

S = input()

d = [0, 0, 0, 1]

max_ans = 10**9 + 7

for c in reversed(S):
    # print(c, d)
    m = [c == "A", c == "B", c == "C", c == "?"]
    if(m[3] is True):
        tmp = 3
    else:
        tmp = 1

    for j in range(3):
        d[j] = (tmp * d[j] + int(m[j] or m[3]) * d[j + 1]) % max_ans
    d[3] = (tmp * d[3]) % max_ans

print(d[0])
### BUGGY CODE ###

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

s = a[:k]

for i in range(n-k):
  b = s[0]
  if a[k+i] > b:
    print ('Yes')
  else:
    print ('No')
  s.append(a[k+i])
  s.pop(0)

### FIXED CODE ###

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

s = a[:k]

for i in range(n-k):
  b = s[0]
  if a[k+i] > b:
    print ('Yes')
  else:
    print ('No')
  s.append(a[k+i])
  s.pop(0)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
n = int(input())
a = [int(i) for i in input().split()]

ans = 0
for i in range(n):
    for j in range(i + 1, n):
        if a[i] == j + 1 and a[j] == i + 1:
            ans += 1
print(ans)


### FIXED CODE ###

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

ans = 0
for i in range(n):
    if a[a[i] - 1] == i + 1:
        ans += 1
print(ans // 2)