Harryxun/sft_time huggingface dataset:
### 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.999
    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 ###

import sys

def solve():
    N = int(sys.stdin.readline().rstrip())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A = sorted(A, reverse=True)
    maxA = A[0]
    cntA = [0 for i in range(maxA+1)]
    for a in A:
        cntA[a] += 1

    ans = 0
    ones = (1 << 31) - 1
    for a in A:
        if cntA[a] == 0:
            continue
        cntA[a] -= 1
        #print('a =',a)
        b = (1 << a.bit_length()) - a
        if cntA[b] > 0:
            cntA[b] -= 1
            ans += 1
    return ans

print(solve())

#  1  1  7   9
#     3  5   11
#        13
#     15
#  2  6  10
#     14
#  4  4  12
#
#  8


### FIXED CODE ###

import sys
import collections

def solve():
    N = int(sys.stdin.readline().rstrip())
    A = list(map(int,sys.stdin.readline().rstrip().split()))
    A = sorted(A, reverse=True)
    maxA = A[0]
    cntA = collections.Counter(A)

    ans = 0
    for a in A:
        if cntA[a] == 0:
            continue
        cntA[a] -= 1
        #print('a =',a)
        b = (1 << a.bit_length()) - a
        if cntA[b] > 0:
            cntA[b] -= 1
            ans += 1
    return ans

print(solve())

#  1  1  7   9
#     3  5   11
#        13
#     15
#  2  6  10
#     14
#  4  4  12
#
#  8
### BUGGY CODE ###

S=input()
lens=len(S)

mod=10**9+7


Asum=[0]*lens
#Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Asum[i]=Asum[i-1]+1
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]
    elif S[i]=="C":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]+1
        qsum[i]=qsum[i-1]
    elif S[i]=="?":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]+1
    else:
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]        

CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,QSUM))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod


    elif S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-1)))%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*(3**max(0,(QSUM-2)))%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*(3**max(0,(QSUM-3)))%mod

        
    



#count=0
#for a in range(lens-2):
#    if S[a]=="A" or S[a]=="?":
#        for b in range(a+1,lens-1):
#            if S[b]=="B" or S[b]=="?":
#                for c in range(b+1,lens):
#                    if S[c]=="C" or S[c]=="?":
#                        count+=1
print(count%mod)


            


### FIXED CODE ###

S=input()
lens=len(S)

mod=10**9+7


Asum=[0]*lens
#Bsum=[0]*lens
Csum=[0]*lens
qsum=[0]*lens

for i in range(lens):
    if S[i]=="A":
        Asum[i]=Asum[i-1]+1
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]
    elif S[i]=="C":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]+1
        qsum[i]=qsum[i-1]
    elif S[i]=="?":
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]+1
    else:
        Asum[i]=Asum[i-1]
        Csum[i]=Csum[i-1]
        qsum[i]=qsum[i-1]        

CSUM=Csum[lens-1]
QSUM=qsum[lens-1]


count=0
for i in range(1,lens-1):
    if S[i]=="B":
        count+=Asum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM),mod)%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-2),mod)%mod


    elif S[i]=="?":
        count+=Asum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-1),mod)%mod
        count+=Asum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-2),mod)%mod
        count+=qsum[i-1]*(CSUM-Csum[i])*pow(3,max(0,QSUM-2),mod)%mod
        count+=qsum[i-1]*(QSUM-qsum[i])*pow(3,max(0,QSUM-3),mod)%mod
        
    



#count=0
#for a in range(lens-2):
#    if S[a]=="A" or S[a]=="?":
#        for b in range(a+1,lens-1):
#            if S[b]=="B" or S[b]=="?":
#                for c in range(b+1,lens):
#                    if S[c]=="C" or S[c]=="?":
#                        count+=1
print(count%mod)
### BUGGY CODE ###


mod = 10 ** 9 + 7


N = int(input().rstrip())
As = list(map(int, input().rstrip().split()))
ans = 0

for i in range(N - 1):
	for j in range(1, N - i):
		ans += As[i] * As[i + j]
	
print(ans % mod)



### FIXED CODE ###


mod = 10 ** 9 + 7


N = int(input().rstrip())
As = list(map(int, input().rstrip().split()))
ans = 0
add = 0

for i in range(N):
	add += As[i]
	add %= mod
ans = add * add % mod

for i in range(N):
	ans -= As[i] * As[i] % mod
	if (ans < 0):
		ans += mod

ans *= int((mod + 1) / 2)
ans %= mod

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

# -*- coding: utf-8 -*-

# 入力から変数を初期化
N, H = map(int, input().split())
a = []
b = []
for i in range(N):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
ans = H

# 振る刀の最大値
amax = max(a)

# 投げる刀を降順でソートしておく
b.sort(reverse=True)

# 攻撃力の高い刀から順にk本投げ、残りの体力をamaxを使って削る
for k in range(N+1):
    damage_throw = 0 + sum(b[0:k])
    H_minus_throw = H - damage_throw
    if H_minus_throw <= 0:
        tmp_ans = k
    else:
        num_swing = -(-H_minus_throw // amax)
        tmp_ans = k + num_swing
    ans = min(tmp_ans, ans)

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

# 入力から変数を初期化
N, H = map(int, input().split())
a = []
b = []
for i in range(N):
    ai, bi = map(int, input().split())
    a.append(ai)
    b.append(bi)
ans = H

# 振る刀の最大値
amax = max(a)

# 投げる刀を降順でソートしておく
b.sort(reverse=True)

# 攻撃力の高い刀から順にk本投げ、残りの体力をamaxを使って削る
damage_throw = 0
for k in range(N+1):
    damage_throw += 0 if k == 0 else b[k-1]
    H_minus_throw = H - damage_throw
    if H_minus_throw <= 0:
        tmp_ans = k
    else:
        num_swing = -(-H_minus_throw // amax)
        tmp_ans = k + num_swing
    ans = min(tmp_ans, ans)

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

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import deque

N = int(input())

A = [0 for i in range(N)]
for i in range(N) :
    L = list(map(int,input().split()))
    for j in range(len(L)) :
        L[j] -= 1
    A[i] = deque(L)

#print(A)
ans = 0
flg = 0

zuru = 0

while flg == 0 :
    zuru += 1
    cnt = 0
    cnt2 = 0
    flg = 1

    if zuru >= 10**5 :
        ans = 499500
        print(ans)
        exit()
    
    for i in range(N) :
        if len(A[i]) == 0 :
            cnt += 1
        elif A[i][0] == -1 :
            A[i].popleft()
        elif A[i][0] < i :
            cnt2 += 1
            continue
        elif i == A[A[i][0]][0] :
            a = A[i].popleft()
            A[a][0] = -1
            flg = 0
        else :
            cnt2 += 1
    if cnt == N :
        flg = 1
    elif flg == 0 :
        ans += 1
    elif (N-cnt) == cnt2 :
        ans = -1

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

from collections import deque

N = int(input())

A = [0 for i in range(N)]
for i in range(N) :
    L = list(map(int,input().split()))
    for j in range(len(L)) :
        L[j] -= 1
    A[i] = deque(L)

#print(A)
ans = 0
flg = 0

zuru = 0

while flg == 0 :
    zuru += 1
    cnt = 0
    cnt2 = 0
    flg = 1

    if zuru >= 10**4 :
        ans = 499500
        print(ans)
        exit()
    
    for i in range(N) :
        if len(A[i]) == 0 :
            cnt += 1
        elif A[i][0] == -1 :
            A[i].popleft()
        elif A[i][0] < i :
            cnt2 += 1
            continue
        elif i == A[A[i][0]][0] :
            a = A[i].popleft()
            A[a][0] = -1
            flg = 0
        else :
            cnt2 += 1
    if cnt == N :
        flg = 1
    elif flg == 0 :
        ans += 1
    elif (N-cnt) == cnt2 :
        ans = -1

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

import functools
import numpy as np

n, X = map(int, input().split())
x = list(map(int, input().split()))

x.append(X)
x = np.array(x)
min_x = np.array([min(x) for _ in range(n+1)])
x = (sorted(x) - min_x)[1:]


def gcd(nums):
    return functools.reduce(euclid, nums)


def euclid(a, b):
    while b:
        a, b = b, a % b
    return a


print(gcd(x))


### FIXED CODE ###

import functools
import numpy as np

n, X = map(int, input().split())
x = list(map(int, input().split()))


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


if n > 1:
    if abs(x[0]-X) == 0:
        ans = euclid(abs(x[1]-X), abs(x[2]-X))
    elif abs(x[1]-X) == 0:
        ans = euclid(abs(x[0]-X), abs(x[2]-X))
    else:
        ans = euclid(abs(x[0]-X), abs(x[1]-X))

    for xi in x[2:]:
        ans = euclid(ans, abs(xi-X))
        if ans == 1:
            break

else:
    ans = abs(x[0] - X)

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

N = int(input())
A = [int(input()) for i in range(N)]
ans = [0]*N

ans[0] = max(A[1:])
ans[N-1] = max(A[:-1])

for i in range(1, N-1):
    ans[i] = max(max(A[:i]), max(A[i+1:]))

print(*ans, sep="\n")

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
ans = [0]*N

first = sorted(A)[-1]
second = sorted(A)[-2]

for i in range(N):
    if A[i]==first:
        ans[i] = second
    else:
        ans[i] = first

print(*ans, sep="\n")
### BUGGY CODE ###

def main():
    import math
    a, b, n = map(int, input().split())
    ans = 0
    
    if n > 10 ** 5:
        for x in range(n, int(math.sqrt(n)), -1):
            fx = math.floor(a * x / b) - math.floor(x / b) * a
            #print(fx)
            if ans < fx:
                ans = fx
            if ans > fx + 10 ** 3:
                #exit()
                pass
    else: 
        for x in range(n, 0, -1):
            fx = math.floor(a * x / b) - math.floor(x / b) * a
            #print(fx)
            if ans < fx:
                ans = fx
            if ans > fx + 10 ** 3:
                #exit()
                pass

    print(ans)

if __name__ == "__main__":
    main()

### FIXED CODE ###


def main():
    import math
    a, b, n = map(int, input().split())
    if n >= b:
        ans = math.floor(a * (b-1)/b)
    else:
        ans = math.floor(a * n / b)
    
    print(ans)
    




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

#coding:utf-8

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

for reader in range(N):
    changer = 0
    for i in range(N):
        if (reader < i and S[i] == "E")\
        or (reader > i and S[i] == "W"):
            changer += 1
    if changer < ans:
        ans = changer

print(ans)

### FIXED CODE ###

N = int(input())
S = input()
ans = 0

for i in range(N):
    if S[i] == "E":
        ans += 1
min_ans = ans

for reader in range(1, N):
    minus = 0
    if S[reader] == "E":
        minus = 1
    if S[reader - 1] == "W":
        ans += 1
    elif S[reader - 1] == "E":
        ans -= 1
    if ans - minus < min_ans:
        min_ans = ans - minus
        count = reader

print(min_ans)
### BUGGY CODE ###

import sys
from collections import deque
import numpy as np
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = np.ones([h+2, w+2])
for i in range(h):
    g[i+1] = [1] + [int(x == '#') for x in input().strip()] + [1]

ans = -1
q = deque([])
for i in range(1, h+1):
    for j in range(1, w+1):
        if g[i, j]:
            q.append((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]

while q:
    q_ = q
    q = deque([])
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if g[ti, tj] == 0:
                g[ti, tj] = 1
                q.append((ti, tj))
print(ans)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
h, w = [int(x) for x in input().strip().split()]
g = [[x for x in list(input().strip())] for _ in range(h)]

ans = -1
q = []
for i in range(h):
    for j in range(w):
        if g[i][j] == '#':
            q.append((i, j))
vec = [(0, 1), (1, 0), (0, -1), (-1, 0)]
while q:
    q_ = deque(q)
    q = deque([])
    ans += 1
    while q_:
        i, j = q_.pop()
        for x, y in vec:
            ti, tj = i+x, j+y
            if 0 <= ti < h and 0 <= tj < w:
                if g[ti][tj] == '.':
                    g[ti][tj] = '#'
                    q.append((ti, tj))
print(ans)
### BUGGY CODE ###

N = int(input())

a = [int(x) for x in input().split(" ")]
ans = 1
fail = False
zero = False
for i in range(N):
	ans*=a[i]
	if(ans>1000000000000000000 or ans<0) :
		fail = True
	elif(a[i]==0) :
		zero = True
		break

if(fail and not zero) :
	print("-1")
else:
	print(ans)

### FIXED CODE ###

N = int(input())

a = [int(x) for x in input().split(" ")]
ans = 1
fail = False
zero = False
for i in range(N):
	if(not fail):
		ans*=a[i]
	if(not fail and ans>1000000000000000000 or ans<0) :
		fail = True
	elif(a[i]==0) :
		zero = True
		ans=0
		break

if(fail and not zero) :
	print("-1")
else:
	print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())
n = 0
for i in range(K + 1):
    for j in range(K + 1):
        if (i + j) > S:
            continue
        elif (S - i - j) > K:
            continue
        for k in range(K + 1):
            if (i + j + k) == S:
                n += 1
print(str(n))


### FIXED CODE ###

K, S = map(int, input().split())
n = 0
for x in range(K + 1):
    for y in range(K + 1):
        if (x + y) > S:
            break
        elif (S - (x + y)) <= K:
            n += 1
print(str(n))
### BUGGY CODE ###

#-*- coding:utf-8 -*-
import copy
import fractions
from functools import reduce


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

gcd_list =[]

for i, a in enumerate(A):
    A_except_a = copy.deepcopy(A)
    A_except_a.pop(i)
    
    gcd = reduce(fractions.gcd, A_except_a)
    gcd_list.append(gcd)

print(max(gcd_list))

### FIXED CODE ###

import fractions
from functools import reduce

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

m1 = [0] * (N + 1)
m2 = [0] * (N + 1)
for i in range(1, N + 1):
  m1[i] = fractions.gcd(m1[i - 1], a_list[i - 1])
  m2[N - i] = fractions.gcd(m2[N - i + 1], a_list[N - i])

m = [0] * N
for i in range(N):
  m[i] = fractions.gcd(m1[i], m2[i + 1])

print(max(m))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n,q=map(int,input().split())
A=[[] for i in range(n)]
node=[0]*n

for i in range(n-1):
    a,b=map(int,input().split())
    a -=1;b -=1
    A[a].append(b)
    A[b].append(a)

for i in range(q):
    p,x=map(int,input().split())
    node[p-1] +=x


def calculate(num,pre=-1):
    for i in A[num]:
        if i==pre:continue
        node[i] +=node[num]
        calculate(i,num)


calculate(0)
print(*node)

### FIXED CODE ###

# coding: utf-8
# Your code here!

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意

#n = int(input())
n,q = [int(i) for i in readline().split()]

g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x

ans = [0]*n
#ans[0] = add[0]

def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)

dfs(0,-1,0)

#print(add)

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

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

for i in range(n,m+1):
    if m%i == 0: 
        print(m//i)
        exit()

### FIXED CODE ###

import bisect

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

n_facs_s = []
n_facs_l = []
for i in range(1, int(-(-m**0.5//1))+1):
    if m%i == 0:
        n_facs_s.append(i)
        n_facs_l.append(m//i)


n_faces = n_facs_s + n_facs_l[::-1]
ind = bisect.bisect_right(n_faces, n)
if n_faces[ind-1] == n:
    ind-=1
print(m//n_faces[ind])
### BUGGY CODE ###

n,s = map(int,input().split())
a = list(map(int,input().split()))
dp = [[0 for i in range(s+1)] for j in range(n+1)]
dp[0][0] = 1
MOD = 998244353
for i in range(n):
    for j in range(s+1):
        dp[i+1][j] = dp[i][j]*2
        if a[i] <= j:
            dp[i+1][j] += dp[i][j-a[i]]
        dp[i+1][j] %= MOD
print(dp[n][s])

### FIXED CODE ###

n,s = map(int,input().split())
a = list(map(int,input().split()))
dp = [[0 for i in range(s+1)] for j in range(n+1)]
dp[0][0] = 1
MOD = 998244353
for i in range(n):
    for j in range(s+1):
        dp[i+1][j] = dp[i][j]*2
        if a[i] <= j:
            dp[i+1][j] += dp[i][j-a[i]]
        dp[i+1][j] %= MOD
print(dp[n][s])
### BUGGY CODE ###

import sys
N = list(input())

N_rev = N[::-1]
#print(N_rev[1:5])

while len(N_rev) > 0:
  if N_rev[0] == "m" and N_rev[1] == "a" and N_rev[2] == "e" and N_rev[3] == "r" and N_rev[4] == "d":
      N_rev = N_rev[5:]
      #print("subscript[dream]",N_rev)
  elif N_rev[0] == "r" and N_rev[1] == "e" and N_rev[2] == "m" and N_rev[3] == "a" and N_rev[4] == "e" and N_rev[5] == "r" and N_rev[6] == "d":
      N_rev = N_rev[7:]
      #print("subscript[dreamer]",N_rev)
  elif N_rev[0] == "r" and N_rev[1] == "e" and N_rev[2] == "s" and N_rev[3] == "a" and N_rev[4] == "r" and N_rev[5] == "e":
      N_rev = N_rev[6:]
      #print("subscript[eraser]",N_rev)
      
  elif N_rev[0] == "e" and N_rev[1] == "s" and N_rev[2] == "a" and N_rev[3] == "r" and N_rev[4] == "e":
      N_rev = N_rev[5:]

  else:
    print("NO")
    sys.exit()

if len(N_rev) == 0:
  print("YES")

### FIXED CODE ###

import re
S = input()
'''
メタ文字：
^ = 文字列の先頭、
| = OR
+ = 直前のパターンを1回以上繰り返し、
$ = 文字列の末尾
'''
if re.match("^(dream|dreamer|erase|eraser)+$", S):
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

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

S = input().rstrip()
T = input().rstrip()

# Sの方が長くする
LS = len(S)
LT = len(T)
n = (LT + (-LT) % LS) // LS
S *= (n+1)
S = S[:LS+LT]

MOD = 10 ** 9 + 7
base = 1234
base_inv = pow(base,MOD-2,MOD) 
power = [1] * (LS+LT)
power_inv = [1] * (LS+LT)
for n in range(1,LS+LT):
    power[n] = power[n-1] * base % MOD
    power_inv[n] = power_inv[n-1] * base_inv % MOD

def to_rolling_hash(S):
    ret = [0] * len(S)
    prev = 0
    for i,s in enumerate(S):
        x = (prev + power[i] * ord(s)) % MOD
        ret[i] = x
        prev = x
    return ret

S_hash = to_rolling_hash(S) + [0]
T_hash = to_rolling_hash(T)[-1] # 文字列全体

can_start = [(S_hash[i + LT - 1] - S_hash[i - 1]) * power_inv[i] % MOD == T_hash for i in range(LS)]

INF = 10 ** 18
visited = [False] * LS
dp = [None] * LS

def dfs(i):
    if visited[i]:
        if dp[i] is None:
            # ループ
            return INF
        return dp[i]
    visited[i] = True
    if not can_start[i]:
        dp[i] = 0
        return 0
    x = dfs((i + LT) % LS) + 1
    dp[i] = x
    return x

answer = max(dfs(i) for i in range(LS))

if answer >= INF:
    answer = -1

print(answer)


### FIXED CODE ###

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

S = input().rstrip()
T = input().rstrip()

S,T

# Sの方が長くする
LS = len(S)
LT = len(T)
n = (LT + (-LT) % LS) // LS
S *= (n+1)
S = S[:LS+LT]

MOD = 10 ** 16 + 61
base = 12345
base_inv = pow(base,MOD-2,MOD) 
power = [1] * (LS+LT)
power_inv = [1] * (LS+LT)
for n in range(1,LS+LT):
    power[n] = power[n-1] * base % MOD
    power_inv[n] = power_inv[n-1] * base_inv % MOD

def to_rolling_hash(S):
    ret = [0] * len(S)
    for i,s in enumerate(S):
        ret[i] = (ret[i-1] + power[i] * ord(s)) % MOD
    return ret

S_hash = to_rolling_hash(S) + [0]
T_hash = to_rolling_hash(T)[-1] # 文字列全体

can_start = [(S_hash[i + LT - 1] - S_hash[i - 1]) * power_inv[i] % MOD == T_hash for i in range(LS)]

INF = 10 ** 18
visited = [False] * LS
dp = [None] * LS

arr = [INF] * LS

q = [(i,0) for i,bl in enumerate(can_start) if not bl]

while q:
    qq = []
    for x,d in q:
        if arr[x] == INF:
            arr[x] = d
            qq.append(((x-LT)%LS, d+1))
    q = qq

answer = max(arr)

if answer >= INF:
    answer = -1

print(answer)
### BUGGY CODE ###

import math
from functools import reduce

# reduce(function, iterable, initializer)
def gcd(*number):
    return reduce(math.gcd, number)

def gcd_list(number):
    return reduce(math.gcd, number)

sum = 0
K = int(input())
for i in range(1,K+1):
    for j in range(1,K+1):
        tmp = gcd(i, j)
        for k in range(1,K+1):
            sum += gcd(tmp, k)

print(sum)


### FIXED CODE ###

import math
from functools import reduce

# reduce(function, iterable, initializer)
def gcd(*number):
    return reduce(math.gcd, number)

def gcd_list(number):
    return reduce(math.gcd, number)

def main():
    sum = 0
    K = int(input())
    for i in range(1,K+1):
        for j in range(1,K+1):
            tmp = math.gcd(i, j)
            for k in range(1,K+1):
                sum += math.gcd(tmp, k)
    print(sum)

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



N = int(input())
E = []
A = [[-1 for j in range(N+1)] for i in range(N+1)]
edges = [[] for i in range(N+1)]

for i in range(N-1):
  a, b = map(int, input().split())
  E.append((a,b))
  edges[a].append(b)
  edges[b].append(a)

def dfs(u):
  visited = set()
  visited.add(u)
  stack = [(u, -1, -1)]
  mcolor = -1

  while stack:
    u, p, c = stack.pop()

    next = 1
    for v in edges[u]:
      if v != p and v not in visited:
        if next == c:
          next += 1
        
        mcolor = max(mcolor, next)
        A[u][v] = next
        A[v][u] = next
        visited.add(v)
        stack.append((v, u, next))
        next += 1
  
  return mcolor

print(dfs(1))

for edge in E:
  a, b = edge
  print(A[a][b])

### FIXED CODE ###


N = int(input())
edges = [[] for _ in range(N+1)]


for i in range(N-1):
  a, b = map(int, input().split())
  if i == 0:
    root = a
  edges[a].append((b, i))
  edges[b].append((a, i))

ans = [-1 for i in range(N-1)]
def dfs(u):
  flag = ["white"] * (N + 1)
  stack = [(u, -1, -1)]

  while stack:
    u, parent, color = stack.pop()
    flag[u] = "black"

    nextColor = 1
    for (next, index) in edges[u]:
      if next != parent and flag[next] != "black":
        if nextColor == color:
          nextColor += 1
        stack.append((next, u, nextColor))
        ans[index] = nextColor
        nextColor += 1

dfs(root)

print(max(ans))

for a in ans:
  print(a)
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
quiz = [list(map(int, input().split())) for i in range(q)]

for i in quiz:
    cnt = s[i[0]-1:(i[1])].count('AC')
    print(cnt)

### FIXED CODE ###

# ACのインデックスを求める
# インデックスから、含まれる個数を求める(2分探索)
from bisect import bisect_left
N,Q = map(int, input().split())
S = input()
tmp = ''
ac_count = []
for i, c in enumerate(S):
	if tmp + c == 'AC':
		ac_count.append(i-1)
	tmp = c
ac_count.sort()

for i in range(Q):
	l, r = map(int, input().split())
	print(len(S[bisect_left(ac_count, l-1) : bisect_left(ac_count, r-1)]))