Harryxun/stf_run huggingface dataset:
def main():
    print(*solve())


def solve():
    X = int(input())
    N = 10 ** 9 + 7

    step = 2 if X % 2 else step = 1  # if X is odd number, (A - B) also must be odd.

    for x in range(1, N, step):  # x means (A - B)
        if X % x:  # X must be divided by (A - B)
            continue

        for a in range(N):
            b = a - x

            diff = X - (a ** 5 - b ** 5)
            if diff == 0:
                return a, b

            if diff < 0 < b:
                break


if __name__ == "__main__":
    main()


### FIXED CODE ###

"""
A^5 - B^5
= (A - B)(A^4 + A^3*B + A^2*B^2 + A*B^3 + B^4)
= (A - B){(A + B) * (A^3 + B^3) + A^2*B^2}
= (A - B){(A + B)^2 * (A^2 - AB + B^2) + A^2*B^2}

-> (A + B)^2 > 1, (A^2 - AB + B^2) > 1, A^2*B^2 > 1.
"""


def main():
    print(*solve())


def solve():
    X = int(input())

    for a in range(-1000, 1000):
        for b in range(-1000, 1000):
            if a ** 5 - b ** 5 == X:
                return a, b


if __name__ == "__main__":
    main()
N, M = [int(_) for _ in input().split()]
XYZ = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


def same(x, y):
    return find(x) == find(y)


for x, y, z in XYZ:
    unite(x, y)
for i in range(1, N + 1):
    find(i)
print(len(set(UF[1:])))


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
N, M = [int(_) for _ in input().split()]
XYZ = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


def same(x, y):
    return find(x) == find(y)


for x, y, z in XYZ:
    unite(x, y)
s = set()
for i in range(1, N + 1):
    s.add(find(i))
print(len(set(s)))
S=str(input())
if S==AAA or S==BBB:
    print('No')
else:
    print('Yes')

### FIXED CODE ###

S=str(input())
if S=='AAA' or S=='BBB':
    print('No')
else:
    print('Yes')
N, M = map(int, input().split())
num = ['']*N
valid = True
#create number from input
for i in range(M):
  s, c = map(int, input().split())
  if (num[s-1] == ''):
    num[s-1] = c
  elif (num[s-1] != c):
    valid = False
    break
#check whether 0 is at front
if (N > 1):
  if (num[0]==0):
    valid = False
  
if valid:
  first = True
  #fill the blank parts
  if (num[0]==''):
    num[0]==1
  for i in range(1,N):
    num[i] = 0
  #convert list to number
  answer = 0
  for i in range(N):
    answer *= 10
    answer += num[i]
  print(answer)
else:
  print(-1)


### FIXED CODE ###

N, M = map(int, input().split())
num = ['']*N
valid = True
#create number from input
for i in range(M):
  s, c = map(int, input().split())
  if (num[s-1] == ''):
    num[s-1] = c
  elif (num[s-1] != c):
    valid = False
    break
#check whether 0 is at front
if (N > 1):
  if (num[0]==0):
    valid = False
  
if valid:
  #fill the blank parts
  for i in range(N):
    if (num[i] == ''):
      if (i == 0):
        if (N == 1):
          num[i] = 0
        else:
          num[i] = 1
      else:
      	num[i] = 0
  #convert list to number
  answer = 0
  for i in range(N):
    answer *= 10
    answer += num[i]
  print(answer)
else:
  print(-1)
def calc_cost(now, next):
  global h_list
  global N
  if next > N - 1: return
  if dp[next] > dp[now] + abs(h_list[next] - h_list[now]):
    dp[next] = dp[now] + abs(h_list[next] - h_list[now])

  calc_cost(next, next + 1)
  calc_cost(next, next + 2)

N = int(input())
h_list = list(map(int, input().split()))
dp = [float('INF') for i in range(N)]
dp[0] = 0

calc_cost(0, 1)
calc_cost(0, 2)

print(dp[N - 1])

### FIXED CODE ###

N = int(input())
h_list = list(map(int, input().split()))
dp = [float('INF') for i in range(N)]
dp[0] = 0

def calc_cost(now, next):
  global h_list
  global dp
  global N
  if next > N - 1: return
  if dp[next] > dp[now] + abs(h_list[next] - h_list[now]):
    dp[next] = dp[now] + abs(h_list[next] - h_list[now])

for i in range(N):
  calc_cost(i, i + 1)
  calc_cost(i, i + 2)

print(dp[N - 1])
ans=-1
nums=input().split(" ")
t8,t10=int(nums[0]),int(nums[1])
value=max(round(t8*100/8),round(t10*100/10))+1
for i in range(value):
  v=value-i
  tax8=v*8/100
  tax10=v*10/100
  if tax8>=t8 and tax8<t8+1 and tax10>=t10 and tax10<t10+1:
    ans=v
  elif tax8<t8 or tax10<t10:
    break
print(ans)

### FIXED CODE ###

letter=input()
if "A" not in letter:
  print("No")
elif "B" not in letter:
  print("No")
else:
  print("Yes")
import sys
s = input()
for i, (x, y) in enumerate(zip(s, s[1:])):
    if x == y:
        print(i+1, i+2)
        sys.exit()
if len(s) == 2:
    print(-1, -1)
for i, (x, y, z) in enumerate(zip(s, s[1:], s[2])):
    if x == z:
        print(i+1, i+3)
        sys.exit()
print(-1, -1)

### FIXED CODE ###

import sys
s = input()
for i, (x, y) in enumerate(zip(s, s[1:])):
    if x == y:
        print(i+1, i+2)
        sys.exit()
if len(s) <= 2:
    print(-1, -1)
    sys.exit()
for i, (x, y, z) in enumerate(zip(s, s[1:], s[2:])):
    if x == z:
        print(i+1, i+3)
        sys.exit()
print(-1, -1)
n=map(int,raw_input().split())
a=n[0]
b=n[1]
S=a*b
L=(2*a)+(2*b)
print(S' 'L)


### FIXED CODE ###

#cording; UTF-8
a,b=[int(x) for x in input().split()]

S = a*b
L = 2*(a+b)
print(S,L)
k = int(input())
x = 7%k
s = set()
while s.count(x) == 0:
  s.append(x)
  x = (10*x + 7)

### FIXED CODE ###

k = int(input())
x = 7%k
s = []

for i in range(k):
  if x == 0:
    print(i+1)
    exit()
  s.append(x)
  x = (10*x + 7)%k

  
  
print(-1)
n=int(input())
a=list(map(int,input().split()))
a=eval("+".join(str(a)))
l=0
while a%2==0:
  l+=1
print(l)

### FIXED CODE ###

length = int(input())
a_list = map(int, input().split())

num_list = []
for a in a_list:
    t = a
    num = 0
    while t % 2 == 0:
        num += 1
        t = t / 2
    num_list.append(num)

print(min(num_list))
#こぴぺです。
N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

A = sorted(A)
BC = sorted(BC, key=lambda x: -x[1])

i = 0
for bc in BC:
  for j in range(bc[0]):
    if A[i] > bc[1]: break
    A[i] = bc[1]
    i += 1

print(sum(A))

### FIXED CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for i in range(M)]

A = sorted(A)
BC = sorted(BC, key=lambda x: -x[1])

lenA = len(A)
i = 0
for bc in BC:
  for j in range(bc[0]):
    if i > lenA-1: break
    if A[i] > bc[1]: break
    A[i] = bc[1]
    i += 1

print(sum(A))
function main()
    a, b, x = split(readline())
    a = parse(Int, a)
    b = parse(Int, b)
    x = parse(Int, x)    
    if a <= x && a + b >= x
        println("YES")
    else
        println("NO")
    end
end
main()

### FIXED CODE ###

a, b, c = input().split()
a = int(a)
b = int(b)
c = int(c)
if a <= c and a + b >= c:
    print("YES")
else:
    print("NO")
m,k = map(int,input().split())
if m == 0:
    if k == 0:
        print(0,0)
    exit()
if m == 1:
    if k== 0:
        print(0,0,1,1)
    exit()
if k < 2**m:
    l = [i for i in range(1,2**m) if i != k ]
    print(*l,k,*l[::-1],k)
else:
    print(-1)

### FIXED CODE ###

m,k = map(int,input().split())
if m == 0:
    if k == 0:
        print(0,0)
    else:
        print(-1)
    exit()
if m == 1:
    if k== 0:
        print(0,0,1,1)
    else:
        print(-1)
    exit()
if k < 2**m:
    l = [i for i in range(2**m) if i != k ]
    l = l + [k] + l[::-1] + [k]
    print(*l)
else:
    print(-1)
N = int(input())

two_ad = 0
four_ad = 0
other = 0
for _ in range(N):
  a = int(input())
  if a % 4 == 0 and a % 2 == 0:
    four_ad += 1
  elif a % 4 == 0:
    four_ad += 1
  elif a % 2 == 0:
    two_ad += 1
  else:
    other += 1

if not two_ad and not four_ad:
  ans = "No"
elif not two_ad:
  if other == four_ad + 1 or four_ad > other:
    ans = "Yes"
  else:
    ans = "No"
elif not four_ad:
  ans = "No"
elif not other:
  ans = "Yes"
elif four_ad == other == two_ad:
  ans = "Yes"
else:
  ans = "No"
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
two_ad = 0
four_ad = 0
other = 0
for a in A:
  if a % 4 == 0:
    four_ad += 1
  elif a % 2 == 0:
    two_ad += 1
  else:
    other += 1

ans = "No"
if four_ad >= other:
  ans = "Yes"
elif four_ad == other - 1 and not two_ad:
  ans = "Yes"
print(ans)
a = input()
a = [int(a)]
b = a[1]*a[2]
if b >= a[0]:
  print('Yes')
elif b < a[0]:
  print('No')

### FIXED CODE ###

a,b,c = map(int, input().split())
if a <= b*c :
  print('Yes')
elif a > b*c :
   print('No')
h,n = map(int,input().split())
a_ = list(map(int,input().split()))

a_.sort()
for i in range(n):
    a_[i] = 0
print(sum(a_))


### FIXED CODE ###

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

if len(h_) <= k:
    print(0)
else:
    h_.sort(reverse = True)
    for i in range(k):
        h_[i] = 0
    print(sum(h_))
n = int(input)
if n % 1000 == 0:
  print("0")
  exit()
print(1000 - (n % 1000))

### FIXED CODE ###

n = int(input())
if n % 1000 == 0:
  print("0")
  exit()
print(1000 - (n % 1000))
a=input()
n=[]
for i in range(len(a)):
  if i%2==1:
    n.append(i)
ans=''
for i in n:
  ans+=i
print(ans)

### FIXED CODE ###

a=input()
n=[]
for i in range(len(a)):
  if i%2==0:
    n.append(i)
ans=''
for i in n:
  ans=ans+a[i]
print(ans)
import math
a,b=map(int,input().split())
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

print(lcm(a, b))

### FIXED CODE ###

from fractions import gcd
a,b=map(int,input().split())
print((a*b)//gcd(a,b))
n=int(input())
a=list(map(int, input().split()))
a_s=sorted(a)
for i in range(0,n,2):
    if a_s[i]<0 and a_s[i+1]<0:
        a_s[i]=-a_s[i]
        a_s[i+1]=-a_s[i+1]
    elif a_s[i]<0 and -a_s[i]>a_s[i+1]:
        a_s[i]=-a_s[i]
        a_s[i+1]=-a_s[i+1]
    else:
        break
print(sum(a_s))

### FIXED CODE ###

n=int(input())
a=list(map(int, input().split()))
a_s=sorted(a)
for i in range(0,n-1,2):
    if a_s[i]<0 and a_s[i+1]<0:
        a_s[i]=-a_s[i]
        a_s[i+1]=-a_s[i+1]
    elif a_s[i]<0 and -a_s[i]>a_s[i+1]:
        a_s[i]=-a_s[i]
        a_s[i+1]=-a_s[i+1]
    else:
        break
print(sum(a_s))
i = list(map(int, input().split()))
N = i[0]
R = i[1]

if N >= 10:
    insc = R
else:
    insc = R + 100(10-N)

print(insc)

### FIXED CODE ###

i = list(map(int, input().split()))
N = i[0]
R = i[1]

if N >= 10:
    insc = R
else:
    insc = R + 100*(10-N)

print(insc)
N = int(input())
A = list(map(int, input().split(' ')))
Q = int(input())
BC = [list(map(int, list(input().split(' ')))) for i in range(Q)]

count = [0] * 10**5
for i in range(N):
    count[A[i]] += 1

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split(' ')))
Q = int(input())
BC = [list(map(int, list(input().split(' ')))) for i in range(Q)]

count = [0] * (10**5 + 5)
for i in range(N):
    count[A[i]] += 1

s = sum(A)
for i in range(Q):
    s = s - BC[i][0] * count[BC[i][0]] + BC[i][1] * count[BC[i][0]]
    count[BC[i][1]] += count[BC[i][0]]
    count[BC[i][0]] = 0
    print(s)
import sys

n, q = map(int, sys.stdin)
g = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, sys.stdin)
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
xs = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, sys.stdin)
    p -= 1
    xs[p] += x

costs = [0 for i in range(n)]
visited = [False for _ in range(n)]


def rec(prev_v, v, value):
    if visited[v]:
        return
    visited[v] = True
    next_value = value + xs[v]
    costs[v] = next_value
    for next_v in g[v]:
        if next_v == prev_v:
            continue
        rec(v, next_v, next_value)


rec(-1, 0, 0)
print(' '.join(map(str, costs)))



### FIXED CODE ###

import sys

n, q = map(int, sys.stdin.readline().split())
g = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, sys.stdin.readline().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
xs = [0 for _ in range(n)]
for i in range(q):
    p, x = map(int, sys.stdin.readline().split())
    p -= 1
    xs[p] += x

visited = [False for _ in range(n)]
# def rec(prev_v, v, value):
#     if visited[v]:
#         return
#     visited[v] = True
#     next_value = value + xs[v]
#     costs[v] = next_value
#     for next_v in g[v]:
#         if next_v == prev_v:
#             continue
#         rec(v, next_v, next_value)
# rec(-1, 0, 0)

current_node = [0]
while len(current_node) > 0:
    next_node = []
    for v in current_node:
        visited[v] = True
        for next_v in g[v]:
            if visited[next_v]:
                continue
            next_node.append(next_v)
            xs[next_v] += xs[v]
    current_node = next_node

print(' '.join(map(str, xs)))
n = int(input())
def main(n):
    x = 800 * n
    if n >= 15:
        y = 200 * math.floor(n / 15)
    print(x - y)

main(n)


### FIXED CODE ###

import math
def main(n):
    x = 800 * n
    y = 0
    if n >= 15:
        y = 200 * math.floor(n / 15)
    print(x - y)

main(int(input()))
N, M = map(int, input().split())
A = [0]*N
for i in range(M):
  s, c = map(int, input().split())
  if A[s-1] == 0:
    A[s-1] = c
  elif A[s-1] != c:
    print(-1)
    exit()

if A[0]>0:
  ans = A[0]*100+A[1]*10+A[2]
else:
  ans = -1
  
print(ans)

### FIXED CODE ###

N, M = map(int, input().split())
A = ["x"]*N
for i in range(M):
  s, c = map(int, input().split())
  if A[s-1] == "x":
    A[s-1] = c
  elif A[s-1] != c:
    print(-1)
    exit()


if A[0]==0 and N>1:
  print(-1)
  exit()
elif N==1 and (A[0]=="x" or A[0] == 0):
  print(0)
  exit()
elif A[0]=="x" or A[0] == 0:
  A[0]=1

for i in range(1,N):
  if A[i]=="x":
    A[i]=0

ans = 0
if A[0]>0:
  for i in range(N):
    ans += A[i]*10**(N-i-1)
else:
  ans = -1
  
print(ans)
import sys
input=sys.stdin.readline
N=input()
if N<=9:
  print(N)
elif 10<=N<=99:
  print(10)
elif 100<=N<=999:
  print(9+(N-99))
elif 1000<=N<=9999:
  print(909)
elif 10000<=N<=99999:
  print(909+(N-9999))
else:
  print(90909)


### FIXED CODE ###

import sys
input=sys.stdin.readline
N=int(input())
ans=0
if N<=9:
  ans=N
elif 10<=N<=99:
  ans=9
elif 100<=N<=999:
  ans=9+(N-99)
elif 1000<=N<=9999:
  ans=909
elif 10000<=N<=99999:
  ans=909+(N-9999)
else:
  ans=90909
print(ans)
N, K = map(int,input().split())
P = list(map(int,input().split()))
prev = 0
for i in range(N):
  p = P[i]
  p = (1+p)//2
  P[i] = prev+p
  prev+=p
ans = 0
for i in range(N-K+1):
  ans = max(ans,P[i+K]-P[i])
print(ans)
  

### FIXED CODE ###

N, K = map(int,input().split())
P = [0]+list(map(int,input().split()))
for i in range(1,N+1):
  p = P[i]
  p = (1+p)/2
  P[i] = p+P[i-1]
ans = 0
for i in range(N-K+1):
  ans = max(ans,P[i+K]-P[i])
print(ans)
n = int(input())
mod = 10**9+ 7
a = list(map(int,input().split()))
ans = (sum(a)%mod)**2 - (sum[x**2 for x in a]%mod)
ans *= 5*10**8+4
ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
mod = 10**9+ 7
a = list(map(int,input().split()))
ans = (sum(a)%mod)**2 - sum([x**2%mod for x in a])
ans *= 5*10**8+4
ans %= mod
print(ans)
a, b, c=map(int, input().split())
m=max(max(a+b, a-b),a*b)
print(m)

### FIXED CODE ###

a, b=map(int, input().split())
print(max(a*b,a+b,a-b))
n = int( input ())
s = sum( list ( str ( n ) ) )
if n % s == 0 :
  ans = 'Yes'
else :
  ans = 'No'
print(ans)

### FIXED CODE ###

n = input ()
s = sum(list( map ( int , list(n))))
num = int(n)
if num % s == 0 :
  ans = 'Yes'
else :
  ans = 'No'
print(ans)
S = input()

## 0を基準として、0と1の境目を調べる
boundary = []
pre_state = '0'
for i in range(len(S)):
  if S[i] != pre_state:
    boundary.append(i)
    pre_state = S[i]
else:
  if S[-1] == '1':
    boundary.append(len(S))
    
## 答えは、端から一番遠い境目
lst = []
for i in range(len(boundary)):
  lst.append(max(boundary[i], len(S)-boundary[i]))
ans = min(lst)
print(ans)


### FIXED CODE ###

S = input()

## 0を基準として、0と1の境目を調べる
boundary = []
pre_state = '0'
for i in range(len(S)):
  if S[i] != pre_state:
    boundary.append(i)
    pre_state = S[i]
else:
  if S[-1] == '1':
    boundary.append(len(S))
    
if len(boundary) == 0:
  print(len(S))
  exit()
    
## 答えは、端から一番遠い境目
lst = []
for i in range(len(boundary)):
  lst.append(max(boundary[i], len(S)-boundary[i]))
ans = min(lst)
print(ans)
N = int(input())
S = input()
count = 0

for i in range(N):
    if S[i] == "#" and S[i+1] == ".":
        break

for j in range(i+1, N):
    if S[j] == ".":
        count += 1

print(count)

### FIXED CODE ###

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

b = 0
w = S.count(".")
ans = w

for i in range(N):
    if S[i] == ".":
        w -= 1
    else:
        b += 1
    ans = min(ans, b + w)

print(ans)
import math
N = int(input())
a = list(map(int, input().split()))

# mはaの(最小公倍数 - 1)
lcm = a[0]
for item in a[1:]:
    lcm = (lcm * item) // math.gcd(lcm, item)
f = 0
for item in a:
    f += (lcm - 1) % item
print(f)

### FIXED CODE ###

import fractions
N = int(input())
a = list(map(int, input().split()))

lcm = a[0]
for item in a[1:]:
    lcm = (lcm * item) // fractions.gcd(lcm, item)
f = 0
for item in a:
    f += (lcm - 1) % item
print(f)
import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 1)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
_d = (2 * 10 ** 5) // d
D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
  
Us[0] = 1 % u
Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i-1] * 2) % u
  Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(X <= 2 * 10 ** 5 + 1):
    if(x[i] == '0'):
      print(solve2(X + 2 ** (n - i - 1), u))
    else:
      if (d == 0):
        print(0)
      else:
        print(solve2(X - 2 ** (n - i - 1), d))
  else:
    if(x[i] == '0'):
      print(solve2(U + Us[n-i-1], u))
    else:
      if (d == 0):
        print(0)
      else:
        print(solve2(D - Ds[n-i-1], d))


### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 6)

n = int(input())
x = input()
z = '1' * n
o = '0' * n
X = int(x, 2)

if (n == 1 and x == '1'):
  print(0)
  exit()

if (z == x):
  u = n - 1
  d = n - 1
elif (o == x):
  u = 1
  d = 1
else:
  tmp = len(list(filter(lambda x: x == '1', x)))
  u = tmp + 1
  d = tmp - 1


def popcount(i):
  return i % len(list(filter(lambda x: x == '1', format(i, 'b'))))


def solve(i, count):
  if (i <= 2 * 10**5 and ans[i] != 0):
    return count + ans[i]
  elif (i == 0):
    return count
  else:
    return solve(popcount(i), count + 1)


def solve2(i, div):
  if (i <= 2 * 10**5):
    return ans[i]
  else:
    return ans[i % div] + 1


ans = [0] * (2 * 10 ** 5 + 4)
_u = (2 * 10 ** 5) // u
U = X % u + (u * _u) + u
if(d != 0):
  _d = (2 * 10 ** 5) // d
  D = X % d + (d * _d) * 2 + d * 2
Us = [0] * (2 * 10 ** 5)
Ds = [0] * (2 * 10 ** 5)
for i in range(1, 2 * 10 ** 5 + 4):
  ans[i] = solve(i, 0)
Us[0] = 1 % u
if(d != 0):
  Ds[0] = 1 % d
for i in range(1, 2 * 10 ** 5):
  Us[i] = (Us[i - 1] * 2) % u
  if(d != 0):
    Ds[i] = (Ds[i-1] * 2) % d

for i in range(n):
  if(x[i] == '0'):
    print(solve2(U + Us[n-i-1], u))
  else:
    if (d == 0):
      print(0)
    else:
      print(solve2(D - Ds[n-i-1], d))
n,l=map(int,input().split())
r=list(map(int,input().split()))
last=0;tiepoint=0
for i in range(n-1):
  if r[i]+r[i+1]>last:
    last=r[i]+r[i+1]
    tiepoint=i
if last>=l:print("Possible")
  for i in range(n):
    if i==tiepoint:continue
    print(i)
else:print("Impossible")

### FIXED CODE ###

import sys
sys.setrecursionlimit(200000)
n,l=map(int,input().split())
r=list(map(int,input().split()))
last=0;tiepoint=0
for i in range(n-1):
  if r[i]+r[i+1]>last:
    last=r[i]+r[i+1]
    tiepoint=i
if last>=l:
  print("Possible")
  for i in range(tiepoint):
    print(i+1)
  for i in range(tiepoint+1,n-1)[::-1]:
      print(i+1)
  print(tiepoint+1)
else:print("Impossible")
n,q=map(int,input().split())
s=input()
A=[0]*(n+1)
cnt=0
for i in range(n):
    A[i]=cnt
    if s[i]=='A' and s[i+1]=='C':
        cnt+=1
ANS=[]
for i in range(q):
    l,r=map(int,input().split())
    ANS.append(A[r-1]-A[l-1])
for ans in ANS:
    print(ans)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()+'Z'
A=[0]*(n+1)
cnt=0
for i in range(n):
    A[i]=cnt
    if s[i]=='A' and s[i+1]=='C':
        cnt+=1
ANS=[]
for i in range(q):
    l,r=map(int,input().split())
    ANS.append(A[r-1]-A[l-1])
for ans in ANS:
    print(ans)
import itertools
def main():
    n = int(input())
    a = list(map(int, input().split()))
    a_compact = []
    sabun = []
    for i in range(1, n):
        sabun.append(a[i] - a[i-1])
    for i, kabuka in enumerate(a):
        if i == 0:
            a_compact.append(kabuka)
        elif i == len(a)-1:
            if a[-2] != a[-1]:
                acom.append(kabuka)
        else:
            if sabun[i-1] != 0:
                check = sabun[i-1] * sabun[i]
                if check <= 0:
                    a_compact.append(kabuka)
    sabun_compact = []

    for i in range(1, len(a_compact)):
        sabun_compact.append(a_compact[i] - a_compact[i-1])
    money = 1000
    kabu = 0
    for i, s in enumerate(sabun_compact):
        # print(i)
        # print('money' + str(money))
        # print('kabunum' + str(kabu))
        if s > 0:
            kabu = money//a_compact[i]
            money -= a_compact[i]*kabu
        else:
            money += a_compact[i]*kabu
            kabu = 0
    money += a_compact[-1]*kabu
    print(money)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n = int(input())
    a = list(map(int, input().split()))
    last = a[0]
    money = 1000
    kabu = 0
    for i, kabuka in enumerate(a):
        if i == len(a)-1:
            break
        if a[i+1] > a[i]:
            kabu = money//a[i]
            money += (a[i+1] - a[i]) * kabu
    print(money)
if __name__ == '__main__':
    main()
n,m=map(int,input().split())
a = [-1]*(n+1)

ans = 0
for i in range(m):
  s,c=map(int,input().split())
  if a[s] == -1 or a[s] == c:
    a[s] = c
  else:
    print(-1)
    exit()
if n == 1:
  print(max(0, a[i]))
  exit()
if a[1] == 0:
  if n>1:
    print(-1)
    exit()
  else:
    print(ans)
else:
  ans = max(1, a[1])
  for i in range(2, n+1):
    ans = ans*10+max(0, a[i])
print(ans)


### FIXED CODE ###

n,m=map(int,input().split())
a = [-1]*(n+1)

ans = 0
for i in range(m):
  s,c=map(int,input().split())
  if a[s] == -1 or a[s] == c:
    a[s] = c
  else:
    print(-1)
    exit()
if n == 1:
  print(max(0, a[1]))
  exit()
if a[1] == 0:
  if n>1:
    print(-1)
    exit()
  else:
    print(ans)
else:
  ans = max(1, a[1])
  for i in range(2, n+1):
    ans = ans*10+max(0, a[i])
print(ans)
n,m,l = map(int, input().split())
INF = 1001001001
dist = [[INF for i in range(n)] for i in range(n)]
#make graph
for i in range(n):
  dist[i][i] = 0
for i in range(m):
  a, b, c = map(int, input().split())
  dist[a-1][b-1] = dist[b-1][a-1] = c
#warshall-froyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
dist2 =  [[INF for i in range(n)] for i in range(n)]
for i in range(n):
  for j in range(n):
    if dist[i][j] <=l:
      dist2[i][j] = 1
#warshall-froyd
for k in range(n):
  for i in range(n):
    for j in range(n):
      dist2[i][j] = min(dist2[i][j], dist2[i][k]+dist2[k][j])
q = int(input())
for i in range(q):
  s,t = map(int, input().split())
  if dist2[s-1][t-1] == INF:
    print(-1)
  else:
    print(dist2[s-1][t-1]-1)

### FIXED CODE ###

A, B = map(int, input().split())
s = A-2*B
if s>0:
  print(s)
else:
  print(0)
print('Yay!'if max(map(int,input().split()))<'9' else':(')

### FIXED CODE ###

a,b=map(int,input().split())
if max(a,b)<=8:
    print('Yay!')
else:
    print(':(')
n = input()
s = input()
count = 0
for i in range(1,int(n)-1):
  if s[i-1] + s[i] + s[i+1] = "ABC":
    count = count + 1
print(count)

### FIXED CODE ###

N = int(input())
S = input()
print(S.count("ABC"))