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

def merge(a, left, mid, right):
    global x
    n1 = mid - left
    n2 = right - mid
    l = [0 for i in range(n1+1)]
    r = [0 for i in range(n2+1)] 
    for i in range(n1):
        l[i] = a[left + i]
    for i in range(n2):
        r[i] = a[mid + i]
    l[n1] = float("inf")
    r[n2] = float("inf")
    i = 0
    j = 0
    for k in range(left,right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
            x += 1
        else :
            a[k] = r[j]
            j += 1
            x += 1

def mergeSort(a, left, right):
    if left+1 < right:
        mid = int((left + right)/2)
        mergeSort(a, left, mid)
        mergeSort(a, mid, right)
        merge(a, left, mid, right)

n = int(input())
s = list(map(int,input().split()))
global x
x = 0
mergeSort(s,0,n)
print(*s)
print(x)


### FIXED CODE ###


def merge(a, left, mid, right):
    x = 0
    l = a[left:mid] + [float("inf")]
    r = a[mid:right] + [float("inf")]
    i = 0
    j = 0
    for k in range(left,right):
        if l[i] <= r[j]:
            a[k] = l[i]
            i += 1
        else :
            a[k] = r[j]
            j += 1
        x += 1
    return x

def mergeSort(a, left, right,x):
    if left+1 < right:
        mid = int((left + right)/2)
        mergeSort(a, left, mid,x)
        mergeSort(a, mid, right,x)
        x[0] += merge(a, left, mid, right)

n = int(input())
s = list(map(int,input().split()))
x = [0]
mergeSort(s,0,n,x)
print(*s)
print(x[0])
### BUGGY CODE ###

s = input()
while True:
  l = len(s)
  s = s.replace('ST', '', 1)
  if l == len(s):
    break
print(len(s))


### FIXED CODE ###

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

n = int(input())
a = list(map(int, input().split()))
q = int(input())
for i in range(q):
  bc = list(map(int, input().split()))
  res = bc[0]
  for bit in range(n):
    if a[bit] == res:
      a[bit] = bc[1]
  print(sum(a))

### FIXED CODE ###

import collections
n = int(input())
a = list(map(int, input().split()))
count = collections.Counter(a)
q = int(input())
s = sum(a)

for i in range(q):
  b, c = map(int, input().split())
  s = s - (b - c) * count[b]
  
  count[c] += count[b]
  count[b] = 0
  print(s)
### BUGGY CODE ###

from collections import Counter


n=int(input())
S = []
for i in range(n):
    S.append(input())

cnt = 0
for i,s in enumerate(S):
    for j,s2 in enumerate(S):
        if i >= j: continue
        if Counter(s) == Counter(s2):
            cnt += 1

print(cnt)

### FIXED CODE ###

from collections import Counter


n=int(input())
S = []
for i in range(n):
    S.append(''.join(sorted(input())))

cnt = Counter(S)
 
ans = 0
for num in cnt.values():
    ans += num*(num-1)//2
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

import itertools

N,Q = map(int,input().split())
S = input()

b = [S[i]=='A' and S[i+1]=='C' for i in range(N-1)]
b.insert(0,0)
b = list(itertools.accumulate(b))

for _ in range(Q):
    l,r = map(int,input().split())
    print(b[r-1]-b[l-1])
### BUGGY CODE ###

n = int(input())
tl = []
al = []
dl = []

for i in range(n):
    a, b = (int(i) for i in input().split())
    tl.append(a)
    al.append(b)

ans = 0
for i in range(n//2+1):
    tm = max(tl)
    am = max(al)
    if tm >= am:
        idxl = [i for i, v in enumerate(tl) if v == tm]
        idx = al.index(max([al[i] for i in idxl]))
        ans += tl[idx]
        tl[idx] = 0
        al[idx] = 0
    else:
        idxl = [i for i, v in enumerate(al) if v == am]
        idx = tl.index(max([tl[i] for i in idxl]))
        ans += tl[idx]
        tl[idx] = 0
        al[idx] = 0
        
    tm = max(tl)
    am = max(al)
    if tm >= am:
        idxl = [i for i, v in enumerate(tl) if v == tm]
        idx = al.index(max([al[i] for i in idxl]))
        ans -= al[idx]
        tl[idx] = 0
        al[idx] = 0
    else:
        idxl = [i for i, v in enumerate(al) if v == am]
        idx = tl.index(max([tl[i] for i in idxl]))
        ans -= al[idx]
        tl[idx] = 0
        al[idx] = 0

print(ans)

### FIXED CODE ###

n = int(input())
l = [[0]*3 for _ in range(n)]
for i in range(n):
    a, b = map(int, input().split())
    l[i] = [a+b, a, b]
l.sort(reverse=True)
ans = 0
for i in range(n):
    if i % 2 == 0:
        ans += l[i][1]
    else:
        ans -= l[i][2]
print(ans)
### BUGGY CODE ###

N,A,B=map(int, input().split())
C=0
D=int(N/(A+B))

for i in range(D):
	C+=A
	N=N-(A+B)
if N>=A:
	C+=A
else:
	C+=N
print(C)

### FIXED CODE ###

N,A,B=map(int, input().split())
ans=N//(A+B)*A
i=N%(A+B)
ans+=min(i,A)
print(ans)
### BUGGY CODE ###

import numpy

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

ans = 0

for i in range(N-1):
  res = numpy.cumsum(A[i+1:N])
  ans += A[i]*res[-1]
  
mod = 10**9 + 7
print(ans%mod)

### FIXED CODE ###

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

ans = 0
res = [0] * N
res[0] = A[0]
for i in range(len(A)-1):
    res[i+1] = res[i] + A[i+1]

sum_A = sum(A)

for i in range(N-1):
  ans += A[i]*(sum_A-res[i])
  
mod = 10**9 + 7
print(ans%mod)
### BUGGY CODE ###

def is_ub(string):
    return max([string.count(i) for i in set(string)]) > len(string)/2

s = input()
for i in range(len(s)-1):
    for j in range(i+1, len(s)):
        if is_ub(s[i:j+1]):
            print(i+1, j+1)
            exit()
print(-1, -1)

### FIXED CODE ###

s = input()
if len(s) == 2:
    if s[0] == s[1]:
        print(1, 2)
    else:
        print(-1, -1)
else:
    for i in range(len(s)-2):
        if len(set(s[i:i+3])) < 3:
            print(i+1, i+3)
            exit()
    print(-1, -1)
### BUGGY CODE ###

n = int(input())
a = []
for num in range(n):
	a.append(int(input()))
for num in range(n):
	temp = a.copy()
	del temp[num]
	print(max(temp))


### FIXED CODE ###

n = int(input())
a = []
first = 0
second = 0
for num in range(n):
	hoge = int(input())
	a.append(hoge)
	if hoge >= first:
		second = first
		first = hoge
	elif second <= hoge and hoge <= first:
		second = hoge

#print(first, second)
for num in range(n):
	if(first <= a[num]):
		print(second)
	else:
		print(first)
### BUGGY CODE ###

#restoring read network
ans=0
import numpy as np
from scipy.sparse import csr_matrix 
from scipy.sparse.csgraph import floyd_warshall
n=int(input())
mat=np.array([[0 for i in range(n)] for j in range(n)],dtype=np.int)
data=np.array([[0 for i in range(n)] for j in range(n)],dtype=np.int)
for _ in range(n):
    x=list(map(int,input().split()))
    for j in range(n):
        mat[_][j]=x[j]
        data[_][j]=x[j]
        
csr=csr_matrix(mat)
csr=floyd_warshall(csr)
if np.array_equal(csr,data):
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            cnt=0
            for k in range(n):
                if data[i][j]>=data[i][k]+data[k][j]:
                    cnt+=1
            if cnt==2:
                ans+=data[i][j]                
    print(ans)            
else:
    print(-1)

### FIXED CODE ###

n=int(input())

mat=[[0 for i in range(n)] for j in range(n)]
data=[[0 for i in range(n)] for j in range(n)]
for _ in range(n):
    x=list(map(int,input().split()))
    for j in range(n):
        mat[_][j]=x[j]
        data[_][j]=x[j]
def warshall_floyd(d):
    #d[i][j]=i番目の頂点からj番目の頂点までの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

newmat=warshall_floyd(mat)
if newmat==data:
    ans=0
    for i in range(n):
        for j in range(i+1,n):
            ans+=data[i][j]*int(all(data[i][j]<data[i][k]+data[k][j] for k in range(i))&all(data[i][j]<data[i][k]+data[k][j] for k in range(i+1,j))&all(data[i][j]<data[i][k]+data[k][j] for k in range(j+1,n)))     
    print(ans)      
else:
    print(-1)
### BUGGY CODE ###

from functools import reduce
N, K = map(int, input().split())

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

before = reduce(lambda a, b: a * b, A[:K])
for i in range(0, N - K):
    temp = before // A[i] * A[K + i]
    if temp > before:
        print("Yes")
    else:
        print("No")
    before = temp

### FIXED CODE ###

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

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

for i in range(0, N - K):
    if A[i] < A[K + i]:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [tuple(map(int, input().split())) for i in range(N)]
W = H + max(A for (A, B) in AB)
dp = [INF] * (W + 1)
dp[0] = 0
for i, (A, B) in enumerate(AB):
    for j in range(A, W+1):
        dp[j] = min(dp[j], dp[j-A] + B)
print(min(dp[H:]))

### FIXED CODE ###

INF = 2**60 # 無限大を表す値
H, N = map(int, input().split())
AB = [map(int, input().split()) for i in range(N)]
dp = [INF] * (H + 1)
dp[0] = 0
for A, B in AB:
    for j in range(H+1):
        dp[j] = min(dp[j], dp[max(j-A, 0)] + B)
print(dp[H])
### BUGGY CODE ###

import math

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2:
        return False
    # 2は素数
    elif num == 2:
        return True
    # 偶数は素数ではない
    elif num % 2 == 0:
        return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = []
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.append(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
# print(callIsPrime(10**5))

sosuu = callIsPrime(10**5)

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    count = 0
    for i in range(l, r+1, 2):
        # print(i)
        if i in sosuu and (i+1)//2 in sosuu:
            count += 1
    print(count)

### FIXED CODE ###

import math

# 素数判定関数
def isPrime(num):
    # 2未満の数字は素数ではない
    if num < 2:
        return False
    # 2は素数
    elif num == 2:
        return True
    # 偶数は素数ではない
    elif num % 2 == 0:
        return False

    # 3 ~ numまでループし、途中で割り切れる数があるか検索
    # 途中で割り切れる場合は素数ではない
    for i in range(3, math.floor(math.sqrt(num)) + 1, 2):
        if num % i == 0:
            return False

    # 素数
    return True

# 素数判定
def callIsPrime(input_num=1000):
    numbers = set()
    # ループしながら素数を検索する
    for i in range(1, input_num):
        if isPrime(i):
            numbers.add(i)

    # 素数配列を返す
    return numbers

# 関数の呼び出し
# print(callIsPrime(10**5))

sosuu = callIsPrime(10**5)
count_dic = {}
count = 0
for i in range(1, 10**5, 2):
    if i in sosuu and (i+1)//2 in sosuu:
        count += 1
    count_dic[i] = count
# print(count_dic)

Q = int(input())
for _ in range(Q):
    l, r = map(int, input().split())
    # if r == l:
    #     print(count_dic[r]-count_dic[l]+1)
    # else:
    print(count_dic[r] - count_dic[max(l-2, 1)])
### BUGGY CODE ###

import itertools

N = int(input())

a = list(range(N))[1:]
b = list(itertools.combinations_with_replacement(a, 3))
c = [0] * (N + 1)

count = 0

for i in range(len(b)):
    f = b[i][0] ** 2 + b[i][1] ** 2 + b[i][2] ** 2 + b[i][0] * b[i][1] + b[i][1] * b[i][2] + b[i][2] * b[i][0]
    if f <= N:
        c[f] += len(sorted(set(itertools.permutations(b[i]))))

for i in range(1, N + 1):
    print(c[i])


### FIXED CODE ###

import math

N = int(input())

ans = [0] * (N + 1)

for i in range(1, int(math.sqrt(N)) + 1):
    for j in range(1, int(math.sqrt(N)) + 1):
        for k in range(1, int(math.sqrt(N)) + 1):
            v = i * i + j * j + k * k + i * j + j * k + k * i
            if v <= N:
                ans[v] += 1

for i in range(1, N + 1):
    print(ans[i])
### BUGGY CODE ###

import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N, K = map(int, readline().split())
H = list(map(int, readline().split()))

dp = [INF] * N
dp[0] = 0

# 配るDP
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            dp[i+j] = min(dp[i+j], dp[i]+abs(H[i] - H[i+j]))
    
ans = dp[-1]
print(ans)

### FIXED CODE ###

import sys

readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
read = sys.stdin.buffer.read
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

N, K = map(int, readline().split())
H = list(map(int, readline().split()))

dp = [INF] * N
dp[0] = 0

# 配るDP
for i in range(N):
    for j in range(1, K+1):
        if i+j < N:
            dp[i+j] = min(dp[i+j], dp[i]+abs(H[i] - H[i+j]))
    
ans = dp[-1]
print(ans)
### BUGGY CODE ###

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

print(min([S[:i].count('W')+S[(i+1):].count('E') for i in range(N)]))

### FIXED CODE ###

N = int(input())
S = input()
cumE = [0 for i in range(N+1)]

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

cumW = [i - cumE[i] for i in range(N)]
cumE2 = [cumE[N] - cumE[i+1] for i in range(N)]
print(min([cumW[i] + cumE2[i] for i in range(N)]))
### BUGGY CODE ###

import itertools
import bisect
n = int(input())
s = input()
listR = []
listG = []
listB = []
counter = 0
for i in range(len(s)):
    if s[i] == "R":
        listR.append(i)
    elif s[i] == "G":
        listG.append(i)
    elif s[i] == "B":
        listB.append(i)

for bits in itertools.product(listR, listG):
    diff = max(bits) - min(bits)
    remover = 0
    if sum(bits) % 2 == 0:
        mid = int(sum(bits) / 2)
    else:
        mid = 1000000
    if (max(bits) + diff) in listB:
        remover += 1
    if (min(bits) - diff) in listB:
        remover += 1
    if mid in listB:
        remover += 1
    counter += (len(listB) - remover)
print(counter)

### FIXED CODE ###

import itertools
import bisect
n = int(input())
s = input()
listR = []
listG = []
listB = []
counter = 0
for i in range(len(s)):
    if s[i] == "R":
        listR.append(i)
    elif s[i] == "G":
        listG.append(i)
    elif s[i] == "B":
        listB.append(i)

listB = sorted(listB)
def binary_search_loop(data, target):
    imin = 0
    imax = len(data)-1
    while imin <= imax:
        imid = imin + (imax - imin) // 2
        if target == data[imid]:
            return True
        elif target < data[imid]:
            imax = imid -1
        else:
            imin = imid + 1
    return False
for bits in itertools.product(listR, listG):
    diff = max(bits) - min(bits)
    remover = 0
    if sum(bits) % 2 == 0:
        mid = int(sum(bits) / 2)
    else:
        mid = 1000000
    if binary_search_loop(listB, max(bits) + diff):
        remover += 1
    if binary_search_loop(listB, min(bits) - diff):
        remover += 1
    if binary_search_loop(listB, mid):
        remover += 1
    counter += (len(listB) - remover)
print(counter)
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = {}
B = [0]*N
C = N//L
ANS = {}
count = 0
for i,x in enumerate(input().split()):
    i = int(i)
    x = int(x)
    B[i] = x
    if x in A : A[x] += [i]
    else : A[x] = [i]
for i in sorted(A) :
    for j in A[i] :
        count += 1
        for k in range(L) :
            if j + k not in ANS : ANS[j+k] = i
    if count  > C // 2 : break
        
for i in range(L):
    if i not in ANS : ANS[i] = min(B[:i+1])
for i in range(L,N):
    if i not in ANS : ANS[i] = min(B[i+1-L:i+1])
for i in range(L-1,N-1) : print(ANS[i], end=" ")
print(ANS[N-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 ###

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

passwords =[]

a_log=[]
ab_log=[]

for a in range(n-2):
    
    is_a_kaburi = 0
    
    for i in a_log:
        
        if i == s[a]:
            is_a_kaburi = 1
            
    if is_a_kaburi == 0:
        
        a_log.append(a)
        
        for b in range(a+1,n-1):
            
            is_ab_kaburi = 0
            
            for i in ab_log:
                
                if i == s[a]+s[b]:
                    is_ab_kaburi = 1
                    
            if is_ab_kaburi == 0:
                
                ab_log.append(a+b)
    
                for c in range(b+1,n):
                    
                    is_abc_kaburi = 0
                    pw = s[a] + s[b] + s[c] 
                    
                    for i in passwords:
                
                        if i == pw:
                            is_abc_kaburi = 1
                            
                    if is_abc_kaburi == 0:
                        passwords.append(pw)
    
                        
                        # print(pw, is_a_kaburi, is_ab_kaburi)

print(len(passwords))

### FIXED CODE ###

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

score = 0

for p in range(1000):
    
    pw = str(p).zfill(3)
    
    start = 0
    n_match = 0
    
    for j in range(3):
        for i in range(start, len(s)):
            
            if s[i] == pw[j]:
                start = i+1
                n_match = n_match+1
                
                if j == 3-1:
                    # print(pw)
                    score = score+1
                
                break
        if n_match <= j:
            break
            
print(score)
### BUGGY CODE ###

K=int(input())
ans=len(str(K))*9
for i in range(1,3*10**6):
    a=list(str(K*i))
    a2=list(map(int,a))
 
    ans=min(ans,sum(a2))
 
print(ans)


### FIXED CODE ###

from collections import deque

def BFS01(d,K):
    d[1] = 1
    q = deque([1])
    while q:
        n = q.popleft()
        l, r = map(lambda x: (x) % K, [n * 10, n + 1])
        if d[l] > d[n]:
            d[l] = d[n]
            q.appendleft(l)

        if d[r] > d[n] + 1:
            d[r] = d[n] + 1
            q.append(r)
    return d[0]

K = int(input())
d = [float('inf')] * K

print(BFS01(d,K))
### BUGGY CODE ###

# coding: utf-8
import sys


def DP_K(h,dp,k,i):
    ans = sys.maxsize
    for j in range(1,min(i,k)+1):
        ml = abs( h[i] - h[i-j] ) + dp[i-j]
        ans = min( ans, ml)
    return ans


def main():
    N,K = map(int,input().split())
    h = list(map(int,input().split()))
    dp = [0]*N
    
    for i in range(1,N):
       dp[i] =  DP_K(h,dp,K,i)
        
    print(dp[-1])
    
    
if __name__=='__main__':
    main()

### FIXED CODE ###

import numpy as np

if __name__=='__main__':
    N,K = map(int,input().split())
    hight = list( map(int,input().split()))
    hight = np.array(hight + [0]*(K+2))
    max_h = 10**9
    dp = [max_h]*(N+K+2)
    dp[0] = 0
    dp = np.array(dp)

    for i in range(N):
        a = hight[i]
        b = hight[i+1:i+K+1]
        np_abs = np.abs(b-a)
        dp[i+1:i+K+1] = np.minimum(np_abs+dp[i],dp[i+1:i+K+1])

        
    print(dp[N-1])
### BUGGY CODE ###

N,K = map(int,input().split())
stones = list(map(int,input().split()))
dp =[1000000007] *N

dp[0]=0
dp[1]=abs(stones[1]-stones[0])

for i in range(2,N):
    start = max(0, i - K)
    for j in range(start, i):
        dp[i] = min(abs(stones[i] - stones[j]) + dp[j],dp[i])

print(dp[-1])


### FIXED CODE ###

N,K = map(int,input().split())
stones = list(map(int,input().split()))
dp =[0] *N

for i in range(1,N):
    dp[i] = min(abs(stones[i] - stones[j]) + dp[j] for j in range(max(0, i - K), i))

print(dp[-1])
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    
    N, L = map(int, input().split())
    dic = {}
    for _ in range(N):
        s = input().rstrip('\n')
        for i in range(len(s)):
            dic[s[:i+1]] = 1
    
    g = 0
    for s in dic.keys():
        t = [si for si in s]
        t[-1] = '0' if t[-1] == '1' else '1'
        t = ''.join(t)
        if t not in dic:
            tmp = L - len(s) + 1
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
    
    if g:
        print('Alice')
    else:
        print('Bob')


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    from collections import defaultdict
    input = sys.stdin.readline

    mod = 10**10+7
    mod2 = 10**10+9
    mod3 = 998244353
    N, L = map(int, input().split())
    dic = defaultdict(int)
    dic2 = defaultdict(int)
    dic3 = defaultdict(int)
    h_list = []
    h2_list = []
    h3_list = []
    pair = {}
    pair2 = {}
    pair3 = {}
    M = 0
    for _ in range(N):
        s = input().rstrip('\n')
        h = 0
        h2 = 0
        h3 = 0
        for i in range(len(s)):
            M += 1
            h = (h*1007 + int(s[i]) + 1) % mod
            pair[h] = (h + 1)%mod if s[i] == '0' else (h-1)%mod
            h2 = (h2 * 2009 + int(s[i]) + 1) % mod2
            pair2[h2] = (h2 + 1)%mod2 if s[i] == '0' else (h2-1)%mod2
            h3 = (h3 * 3001 + int(s[i]) + 1) % mod3
            pair3[h3] = (h3 + 1) % mod3 if s[i] == '0' else (h3 - 1) % mod3
            dic[h] = i+1
            dic2[h2] = i+1
            dic[h3] = i+1
            h_list.append(h)
            h2_list.append(h2)
            h3_list.append(h3)

    g = 0
    seen = defaultdict(int)
    seen2 = defaultdict(int)
    seen3 = defaultdict(int)
    for i in range(M):
        s, s2, s3 = h_list[i], h2_list[i], h3_list[i]
        if seen[s] and seen2[s2] and seen3[s3]:
            continue
        t = pair[s]
        t2 = pair2[s2]
        t3 = pair3[s3]
        if dic[t] == 0 or dic2[t2] == 0 or dic3[t3] == 0:
            p = [dic[s], dic2[s2], dic3[s3]]
            p.sort()
            tmp = L - p[1] + 1
            '''
            if not seen[s]:
                tmp = L - dic[s] + 1
            elif not seen[s2]:
                tmp = L - dic2[s2] + 1
            else:
                tmp = L - dic3[s3] + 1
            '''
            cnt = 0
            while tmp % 2 == 0:
                tmp //= 2
                cnt += 1
            g ^= (2**cnt)
            #print(g, s, s2, t, t2, dic[t], dic2[t2])
        seen[s] = 1
        seen2[s2] = 1
        seen3[s3] = 1

    if g:
        print('Alice')
    else:
        print('Bob')


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

X = int(input())

root = int(X**(1/5))

if root**5 < X:
    rest = X - root**5
    another = -int(rest**(1/5))
else:
    rest = root**5 - X
    another = int(rest**(1/5))

tmp = 1
while root**5 - another**5 != X:
    another_plus = another + tmp
    another_minus = another - tmp
    if root**5 - another_plus**5 == X:
        another = another_plus
        break
    if root**5 - another_minus**5 == X:
        another = another_minus
        break
    tmp += 1


print(root, another)


### FIXED CODE ###

X = int(input())

import sys

for a in range(-118, 120):
    for b in range(-119, 119):
        if a**5 - b**5 == X:
            print(a, b)
            sys.exit()
### BUGGY CODE ###

s = input()

ans = 0
temp = 0
for n, _ in enumerate(s):
    if s[n] == "A":
        for j, _ in enumerate(s[n:]):
            if s[n + j] == "Z":
                temp = j + 1
        ans = max(ans, temp)

print(ans)



### FIXED CODE ###

s = input()

a = 0
for n, i in enumerate(reversed(s)):
    if i == "Z":
        a = len(s) - n
        break

b = 0
for n, i in enumerate(s):
    if i == "A":
        b = n
        break

print(a-b)