Harryxun/stf_run huggingface dataset:
import math
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

def roundup(n):
    return int(math.ceil(n /10)) * 10
def get_digit(number):
    return number % 10   
s = 0
m = []
li = [A, B, C, D, E]
for i in range(len(li)):
    if get_digit(li[i]) >= 1:
        m.append(get_digit(li[i]))
f = False
        
for l in range(len(li)):
    if min(m) == get_digit(li[l]) and f == False:
        s += li[l]
        f = True
    else:
        s += roundup(li[l])
print(s)

### FIXED CODE ###

import math
A = int(input())
B = int(input())
C = int(input())
D = int(input())
E = int(input())

def roundup(n):
    return int(math.ceil(n /10)) * 10
def get_digit(number):
    return number % 10   
s = 0
m = []
li = [A, B, C, D, E]
for i in range(len(li)):
    if get_digit(li[i]) >= 1:
        m.append(get_digit(li[i]))
f = False
m.sort()        
for l in range(len(li)):
    if len(m) > 0:
        if m[0] == get_digit(li[l]) and f == False:
            s += li[l]
            f = True
        else:
            s += roundup(li[l])
            # print(roundup(li[l]))
    else:
        s =sum(li)
print(s)
n=int(input())-1

edges = {}
lens = {}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    edges.setdefault(a, []).append(b)
    edges.setdefault(b, []).append(a)
    lens[(a,b)] = c

q, k = map(int, input().split())

dists = {}
def build(x, d=0):
    dists[x] = d
    for c in edges[x]:
        if c not in dists:
            build(c, d + lens[(min(x,c), max(x,c))])

build(k)


for _ in range(q):
    [x, y] = map(int, input().split())
    print(dists[x] + dists[y])

### FIXED CODE ###

n=int(input())-1

edges = {}
lens = {}
for _ in range(n):
    [a, b, c] = map(int, input().split())
    if a > b:
        a,b=b,a
    edges.setdefault(a, []).append(b)
    edges.setdefault(b, []).append(a)
    lens[(a,b)] = c

q, k = map(int, input().split())

dists = {}
def build(x, d=0):
    ss = [(x, 0)]
    while ss:
        x, d = ss.pop()
        if x not in dists:
            dists[x] = d
            for c in edges.get(x, []):
                ss.append((c, d + lens[(min(x,c), max(x,c))]))

build(k)

for _ in range(q):
    [x, y] = map(int, input().split())
    print(dists[x] + dists[y])
def aa087():
    x = int(input())
    a = int(input())
    b = int(input())

    c = x - a
    d = math.floor(c/b)
    c -= b*d
    print(c)

aa087()

### FIXED CODE ###

import math

def aa087():
    x = int(input())
    a = int(input())
    b = int(input())

    c = x - a
    d = math.floor(c/b)
    c -= b*d
    print(c)

aa087()
# -*- coding: utf-8 -*-

X, Y = map(int,input().split())

ans = 0
if X % 2 == 0 and Y % 2 == 0:
    print(0)
else:
    for i in range(X):
        if X == (1 + 2) * i:
            a = i
    print(a)
    print((a * 2) % (10 ** 9 + 7))


### FIXED CODE ###

# -*- coding: utf-8 -*-
#コンビネーション
def cmb(n, r):
    if (r < 0) or (n < r):
        return 0
    r = min(r, n - r)
    return fact[n] * factinv[r] * factinv[n-r] % mod

N = 10 ** 6  # N は必要分だけ用意する
mod = pow(10, 9) + 7
fact = [1, 1]  # fact[n] = (n! mod p)
factinv = [1, 1]  # factinv[n] = ((n!)^(-1) mod p)
inv = [0, 1]  # factinv 計算用

for i in range(2, N + 1):
    fact.append((fact[-1] * i) % mod)
    inv.append((-inv[mod % i] * (mod // i)) % mod)
    factinv.append((factinv[-1] * inv[-1]) % mod)

import math
x, y = map(int,input().split())

if (2 * y - x) % 3 != 0 and (2 * x - y) % 3 != 0:
    print(0)
else:
    a = (2 * y - x) // 3
    b = (2 * x - y) // 3
    ans = cmb(a+b, a)
    print(ans % (pow(10, 9) + 7))
def comb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

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

C = comb(N*M-2, K-2)
#print(int(C))

A = int(0)
for d in range(N):
    a = (N-d)*(M**2)

    A += int(d*a)

B = int(0)
for d in range(M):
    b = (M-d)*(N**2)
    B += int(d*b)

ans = int((A+B)*C)
ans = ans%(1000000007)
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop

# input
N,M =map(int,input().split())
A = [0]*N
B = [0]*M
C = [0]*M

A = list(map(int, input().split()))
A.sort()
for i in range(M):
    B[i],C[i] = list(map(int,input().split()))


def solve():

    pairs = zip(C, B)
    sortedpairs = sorted(pairs, key=lambda x: x[0])
    for i in range(M):
        B[i]=sortedpairs[i][1]
        C[i]=sortedpairs[i][0]

    ansA=[0]*N
    for j in range(N):
        ansA[j] = A[j]

    p = int(0)
    j = int(0)
    while  j<N and M>=1+p :
        jd = int(0)
        if ansA[j] >= C[M - 1 - p]:
            break
        while  B[M-1-p]-jd>0 :
            if j==N : break
            if ansA[j]>=C[M-1-p] :
                break
            else:
                ansA[j]=C[M-1-p]
            jd +=1
            j +=1

        p +=1

    ans = int(0)
    for j in range(N):
        ans += ansA[j]

    print(ans)

solve()
r = 50001
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

while True:
    n = int(raw_input())
    if n == 0:
        break
    count = 0
    for i in range(n/2):
        if p[i] == 1:
            m = n - (i+1)
            if p[m-1] == 1:
                count += 1
    print count

### FIXED CODE ###

def get():
	p,w = map(int, raw_input().split(","))
	for i in range(W-w,-1,-1):
		if bag[i] > 0 and bag[i]+p > bag[i+w]:
			bag[i+w] = bag[i]+p
	else:
		if p > bag[w]: bag[w] = p
	return

c = 1
while True:
	W = int(raw_input())
	if W == 0: break
	bag = [0]*(W+1)
	N = int(raw_input())
	for i in range(N): get()
	w_all = max(bag)
	money = bag.index(w_all)
	print "Case {}:\n{}\n{}".format(c,w_all,money)
	c += 1
import numpy as np
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
A = np.array(A)
B = np.array(B)
if np.sum(A) < np.sum(B):
    print(-1) 
else:
    sub_a_b = A-B
    p_sub = sorted(list(sub_a_b[sub_a_b>0]),reverse = True)
    # print(p_sub)  
    m_sub = list(sub_a_b[sub_a_b<0])
    max_counter = p_sub[0]
    m_sub_sum = abs(sum(m_sub))
    count = 1 + len(m_sub) 
    # print(p_sub[0:1])
    for i in range(len(p_sub)):
        if max_counter >= m_sub_sum:
            print(count)
            exit()
        else:
            max_counter += p_sub[i+1]
            count += 1

### FIXED CODE ###

n = list(map(int, input().split()))
if (1 in n) and (9 in n) and (7 in n) and 4 in n:
    print("YES")
else:
    print("NO")
n, x = map(int, input().split())

def func(a, b):
    if a < b:
        if b%a == 0:
            return b/a*2 - 1
        else:
            return 2*a + func(a, b-a)
    else:
        if a%b == 0:
            return a/b*2 - 1
        else:
            return 2*b + func(a-b, b)
            
if x == n/2:
    print(3*x)
else:
    print(x+(n-x)+func(x,n-x))

### FIXED CODE ###

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

def func(a, b):
    if a < b:
        if b%a == 0:
            return (b//a*2 - 1)*a
        else:
            q, mod = divmod(b,a)
            return 2*q*a + func(a, mod)
    elif a > b:
        if a%b == 0:
            return (a//b*2 - 1)*b
        else:
            q, mod = divmod(a,b)
            return 2*q*b + func(mod, b)
    else:
        return a

if x == n/2:
    print(3*x)
else:
    print(x+(n-x)+func(x,n-x))
n = input()
n = int(n)
x = input()
x = int(x)
t = input()
t = int(t)

if x == 1:
    count = n
else:
    count = n//x
    if n%x == 0:
        pass
    else:
        count = count + 1

print(t*count)

### FIXED CODE ###

def solve(n, x, t):
    return (n + x - 1) // x * t

n, x, t = map(int, input().split())
print(solve(n, x, t))
from collections import Counter

n=int(input())
s=[int(i) for i in input().split()]
div=int(10**9+7)
c = Counter(s)
j=-1
for i in range(1, n + 1):
    if c[i] == 2:
        j = i
        break
a, b = [i for i in range(n + 1) if s[i] == j]

f=[1]
t=1
for i in range(1,n+2):
    t=t*i
    f.append(t)


for i in range(1,n+2):
    x=round(f[n+1]/(f[i]*f[n+1-i]))
    y=round(f[a+n-b]/(f[i-1]*f[a+n-b-i+1]))
    ans=(x-y)%div
    print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
occur = [0 for i in range(n + 1)]
MOD = 1000000007
for i in range(n + 1):
    if occur[a[i]] > 0: val = n - 1 - i + occur[a[i]]
    else: occur[a[i]] = i + 1
inv = [0 if i > 2 else 1 for i in range(n + 2)]
pinv = [0 if i > 2 else 1 for i in range(n + 2)]
perm = [0 if i > 2 else 1 for i in range(n + 2)]
for i in range(2, n + 2):
    inv[i] = -int(MOD / i) * inv[MOD % i] + MOD
    pinv[i] = pinv[i - 1] * inv[i] % MOD
    perm[i] = perm[i - 1] * i % MOD
def C(n, m):
    return (perm[m] * pinv[n] % MOD) * pinv[m - n] % MOD if n <= m else 0
for i in range(1, n + 2):
    temp = C(i, n + 1) - C(i - 1, val)
    if temp < 0: temp += MOD
    print(temp)
for i in range(3001):
    a, b = map(int, input().split())
    if a <= b:
        print(a, b)
    else:
        print(b, a)


### FIXED CODE ###

for i in range(3000):
    a, b = map(int, input().split())
    if a == 0 and b == 0:
        break
    if a <= b:
        print(a, b)
    else:
        print(b, a)
def main():
    W,H,x,y,r=map(int,input().split())
    if W>=2*r AND H>=2*r AND W<=x+r AND H<=y+r:
        print('Yes')
    else:
        print('No')

if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    W,H,x,y,r=map(int,input().split())
    if x-r>=0 and y-r>=0 and W>=x+r and H>=y+r:
        print('Yes')
    else:
        print('No')

if __name__=='__main__':
    main()
A, B = map(long, raw_input().split())
ans = 0
for i in range(A, B+1):
    ans ^= i
    # print(ans, i)
print(ans)


### FIXED CODE ###

A, B = map(int, input().split())
ans = 0
cnt = 0
def f(arg):
    ans = 0
    if arg < 0:
        return 0
    for pos in range(1, 41):
        # ループする数
        loop = 1 << pos
        # cnt = sum([int((n & v) / v) for n in range(arg+1)])
        cnt = int((arg + 1) / loop) * (loop >> 1)
        cnt += max(0, (arg + 1) % (loop) - (loop >> 1))
        ans += cnt%2 * (loop>>1)
        # print(arg, pos, loop, cnt, ans)
        if loop > arg:
            break
    return ans
print(f(A-1)^f(B))
N=int(input())
A=list(input()for i in range(N))
if len(A)==len(set(A)):
    if all(A[i][-1]==A[i+1][0]) for i in range(N-2):
        print('Yes')
    else:print('No')
else:print('No')

### FIXED CODE ###

N=int(input())
A=list(input()for i in range(N))
if len(A)==len(set(A)):
    if all(A[i][-1]==A[i+1][0] for i in range(N-1)):
        print('Yes')
    else:print('No')
else:print('No')
def main():
  N = int(input())

  max_left = [0] * N
  max_right = [0] * N

  ary = []

  for i in range(N):
    ary.append(int(input()))

  for i in range(0, N-1):
    max_left[i+1] = max(max_left[i], a[i])

  for i in range(N - 1, 0, -1):
    max_right[i-1] = max(max_right[i], ary[i]):

  for i in range(0, N):
	v = max(max_left[i], max_right[i])
	print(v)

main()


### FIXED CODE ###

def main():
    N = int(input())

    max_left = [0] * N
    max_right = [0] * N

    ary = []

    for i in range(N):
        v = int(input())
        ary.append(v)

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

    for i in range(N - 1, 0, -1):
        max_right[i-1] = max(max_right[i], ary[i])

    for i in range(N):
        v = max(max_left[i], max_right[i])
        print(v)


main()
W,H,x,y,r=map(int,input().split())
W=-r;H=-r;
if min([x,y]>=r)and x<=W and y<=H:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

W,H,x,y,r=map(int,input().split())
if min([x,y])>=r and x<=(W-r) and y<=(H-r):
    print("Yes")
else:
    print("No")
N,M = list(map(int,input().split()))
ps = []
for i in range(M):
    ps.append(list(map(str,input().split())))
    
ps_new = sorted(ps , key=lambda x: x[0])
toi = []

for i in range(M):
    toi.append(ps[i][0])
    
toi2 = toi[0]
toi3 = [toi2]

for i in range(M):
    if toi2 != toi[i]:
        toi3.append(toi[i])
        toi2 = toi[i]
toi3.append("0")

toi = ps_new[0][0]
j = 0
count1 = 0
count2 = 0
count3 = 0

for i in range(M):
    if toi == ps[i][0]:
        count2 += 1
        if count2 == 1:
            shokai = i
        if ps_new[i][1] == "AC":
            count1 += 1
            j += 1
            toi = toi3[j]
            count2 = 0
            count3 = count3 + (i-shokai)
            
print(count1,count3)

### FIXED CODE ###

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

AC = [0]*N
WA = [0]*N
miss = 0

for i in range(M):
    p,S = list(map(str,input().split()))
    p = int(p)-1
    
    if S == 'AC' and AC[p] == 0:
        AC[p] = 1
        miss += WA[p]
        
    WA[p] += 1
        
print(sum(AC),miss)
n=int(input())
s=len(bin(n)-2)
if 2**(s-1)==n:
  print("No")
else:
  print("Yes")
  print(2**(s-1)-1,1+n)
  for i in range(1,2**(s-1)-2):
    print(i,i+1)
    print(i+n,i+n+1)
  print(2**(s-1),2**(s-1)+1)
  print(2**(s-1)+1,1)
  print(2**(s-1)+n,1)
  print(2**(s-1)+n,2**(s-1)+1+n)
  for i in range(2**(s-1)+2,n+1):
    print(i,i-1+n)
    print(i+n,i-2**(s-1))
    
      

### FIXED CODE ###

n=int(input())
s=len(bin(n))-2
if 2**(s-1)==n:
  print("No")
elif n==3:
  print("Yes")
  for i in range(1,6):
    print(i,i+1)
else:
  print("Yes")
  print(2**(s-1)-1,1+n)
  for i in range(1,2**(s-1)-1):
    print(i,i+1)
    print(i+n,i+n+1)
  print(2**(s-1),2**(s-1)+1)
  print(2**(s-1)+1+n,1)
  print(2**(s-1),1)
  print(2**(s-1)+n,2**(s-1)+1+n)
  for i in range(2**(s-1)+2,n+1):
    print(i,i-1+n)
    print(i+n,i-2**(s-1))
s=raw_input()
print(s.count("+")-s.count("-"))


### FIXED CODE ###

print(4-input().count("-")*2)
n,k=map(int,input().split())
if (n+1)/2>=k:
  print('YES')
else:
  print('')NO

### FIXED CODE ###

n,k=map(int,input().split())
if (n+1)/2>=k:
  print('YES')
else:
  print('NO')
n = input()
A = map(int, raw_input().split())

Q = input()
m = map(int, raw_input().split())

f = []

for i in range(n):
    j = 2000
  while 0 < j:  
    if(j + A < 2000 && f[j] == 1):
      f[j + A] == 1
    j- = 1

for i in range(Q)
    if(f[m] == 1):
    print "yes"
  else:
    print "no"

### FIXED CODE ###

n = int(raw_input())
A = map(int,raw_input().split())
Q = int(raw_input())
m = map(int,raw_input().split())

def s(i, m):
  if m == 0:
    return True
  if i >= n or m > sum(A):
    return False
  r = s(i + 1, m) or s(i + 1, m - A[i])
  return r

for j in range(Q):
  if s(0, m[j]):
    print "yes"
  else:
    print "no"
h, a = map(int, input().split())

if h%a == 0:
  print((int))h/a))
else:
  print((int)(h/a)+1)

### FIXED CODE ###

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

if h%a == 0:
  print((int)(h/a))
else:
  print((int)(h/a)+1)
import sys
sys.setrecursionlimit(2000)
h, w = map(int, raw_input().split())
s = [[c for c in raw_input()] for i in range(h)]
def isValid(i, j):
    if i < 0 or i >= h or j < 0 or j >= w:
        return False
    return True
    
def dfs(s, i, j):
    if not isValid(i, j) or s[i][j] == "0" or s[i][j] == ".":
        return 0
    if s[i][j] == "#":
        s[i][j] = "0"
        a = dfs(s, i+1, j)
        b = dfs(s, i-1, j)
        c = dfs(s, i, j+1)
        d = dfs(s, i, j-1)
        return 1 + a + b + c + d

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            ccs = dfs(s, i, j)
            #print ccs
            if ccs == 1:
                print "No"
                exit()
print "Yes"

### FIXED CODE ###

import sys
sys.setrecursionlimit(3000)
h, w = map(int, raw_input().split())
s = [[c for c in raw_input()] for i in range(h)]
def isValid(i, j):
    if i < 0 or i >= h or j < 0 or j >= w:
        return False
    return True
    
def dfs(s, i, j):
    if not isValid(i, j) or s[i][j] == "0" or s[i][j] == ".":
        return 0
    if s[i][j] == "#":
        s[i][j] = "0"
        a = dfs(s, i+1, j)
        b = dfs(s, i-1, j)
        c = dfs(s, i, j+1)
        d = dfs(s, i, j-1)
        return 1 + a + b + c + d

for i in range(h):
    for j in range(w):
        if s[i][j] == "#":
            ccs = dfs(s, i, j)
            #print ccs
            if ccs == 1:
                print "No"
                exit()
print "Yes"
r,g b = input().split()
if int((g*10+b)%4==0):
    print('YES')
else:
    print('No')
    


### FIXED CODE ###

r,g,b=map(int,input().split())
X = r * 100 + g * 10 + b
if X % 4 == 0:
    print('YES')
else:
    print('NO')
a, b = map(int(input().split())
if a > 0:
  print("Positive")
elif a < 0 :
  if (b - a) % 2 == 0 :
      print("Positive")
  else:
      print("Negative")
else:
   print("Zero")

### FIXED CODE ###

a, b = map(int, input().split())
if a > 0 :
  print("Positive")
elif b < 0 :
  if (b - a) % 2 == 0 :
      print("Negative")
  else:
      print("Positive")
else:
   print("Zero")
n = int(input())
s = input()
cnt = 0
for i in range(n):
    if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C":
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
s = input()
cnt = 0
for i in range(n-2):
    if s[i]=="A" and s[i+1]=="B" and s[i+2]=="C":
        cnt += 1
print(cnt)
import numpy as np

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

X = list(map(int,input().split()))
X = [abs(i-x) for i in X]
# print(X)

def gcd(m,n):
    mx = max(m,n)
    mn = min(m,n)
    tmp = mx%mn
    if tmp == 0:
        return mn
    else:
        return gcd(mn, tmp)

def gcd_list(data):
    if len(data)==1:
        return data[0]
    tmp = gcd(data[0], data[1])
    if len(data)==2:
        return tmp
    else:
        new_data = [tmp]+data[2:]
        return gcd_list(new_data)

# print(gcd_list([2,4,8]))
print(gcd_list(X))

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)

from fractions import gcd

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

X = list(map(int,input().split()))
X = [abs(i-x) for i in X]
# print(X)

# def gcd(m,n):
#     mx = max(m,n)
#     mn = min(m,n)
#     tmp = mx%mn
#     if tmp == 0:
#         return mn
#     else:
#         return gcd(mn, tmp)

def gcd_list(data):
    # if len(data)==1:
    #     return data[0]
    # tmp = gcd(data[0], data[1])
    # if len(data)==2:
    #     return tmp
    # else:
    #     new_data = [tmp]+data[2:]
    #     return gcd_list(new_data)
    ret = data[0]
    for d in data[1:]:
        ret = gcd(ret, d)
    return ret
# print(gcd_list([2,4,8]))
print(gcd_list(X))
import numpy as np

N,M,X = list(map(int, input().split()))

C = []
for i in range(N):
    C.append(list(map(int, input().split())))

ans = 1000000000
found = False

for i in range(2 ** N):
    tmp = [0] * (M + 1)
    books = np.array(tmp)
    for j in range(N): 
        if ((i >> j) & 1):
            books = books + np.array(C[j])

    skill_good = True
    for k in range(1,M+1):
        if books[k] < X:
            skill_good = False

    if books[0] < ans and skill_good:
        ans = books[0]
        found = True

if found:
    print(ans)
else:
    print(-1)
    


### FIXED CODE ###

import numpy as np

N,M,X = list(map(int, input().split()))

C = []
for i in range(N):
    C.append(list(map(int, input().split())))

ans = 1000000000
found = False

for i in range(2 ** N):
    tmp = [0] * (M + 1)
    books = np.array(tmp)
    for j in range(N): 
        if ((i >> j) & 1):
            books = books + np.array(C[j])

    skill_good = True
    for k in range(1,M+1):
        if books[k] < X:
            skill_good = False

    if books[0] < ans and skill_good:
        ans = books[0]
        found = True

if found:
    print(ans)
else:
    print(-1)
S = str(input())
N = len(S)

small = round((N-1)/2)
big = round((N+3)/2)-1
smallS = S[0:small]
bigS = S[big:N]

if L > 5:
    if smallS == bigS:
        print('Yes')
    else:
        print('No')
else:
    print('No')

### FIXED CODE ###

S = str(input())
N = len(S)
 
head = round((N-1)/2)
end = round((N+3)/2-1)

headS = S[:head]
endS = S[end:]

if S==S[::-1] and headS == headS[::-1] and endS == endS[::-1]:
	print('Yes')
else:
  	print('No')
import sys
n = int(input())
A=[int(e)for e in sys.stdin]
cnt = 0
G = [797161,265720,88573,29524,9841,3280,1093,364,121,40,13,4,1]
G = [v for v in G if v <= n]
for g in G:
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j+g] = A[j]
            j = j - g
            cnt += 1
        A[j+g] = v
print(len(G))
print(*G)
print(cnt)
print(*A,sep='\n')


### FIXED CODE ###

import sys
def insertionSort(A, n, g):
    global cnt
    for i in range(g, n):
        v = A[i]
        j = i - g
        while j >= 0 and A[j] > v:
            A[j + g] = A[j]
            j = j - g
            cnt += 1
        A[j + g] = v
def solve():
    n = int(input())
    A = list(map(int, sys.stdin))
    G = [int((2.25**i - 1) / 1.25)for i in range(17, 0, -1)]
    G = [v for v in G if v <= n]
    for g in G:
        insertionSort(A, n, g)
    print(len(G))
    print(*G)
    print(cnt)
    print('\n'.join(map(str, A)))
if __name__ == '__main__':
    cnt = 0
    solve()
N = int(input())
S = input()

x = 0
l = []

for i in S:
    if i == 'I':
        x += 1
    elif i == 'D':
        l.append(x)
        x -= 1
print(max(l))

### FIXED CODE ###

x = 0
max_value = [0]

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

list = [i for i in s]

for j in list:
    if j == 'I':
        x += 1
        max_value.append(x)
    else:
        x -= 1
        max_value.append(x)
print(max(max_value))
s = input()
t = input()

def z_algorithm(s):

    a = [0] * len(s)
    i = 1
    j = 0
    a[0] = len(s)
    while i < len(s):
        while i + j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

new_s = ""
while True:
    new_s += s
    if len(new_s) >= len(t):
        s = new_s
        break

def solve(i, li):
    ans = 0
    if i < 0 or len(li) <= i:
        return 0
    if visited[i]:
        return 0
    if li[i] >= len(t):
        visited[i] = True
        ans += 1 + solve(i+len(t), li)
    if li[i] < len(t):
        visited[i] = True
    return ans

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)

### FIXED CODE ###

s = input()
t = input()

def z_algorithm(s):
    a = [0] * len(s)
    i = 1
    j = 0
    a[0] = len(s)
    while i < len(s):
        while i + j < len(s) and s[j] == s[i+j]:
            j += 1
        a[i] = j
        if j == 0:
            i += 1
            continue
        k = 1
        while i + k < len(s) and k + a[k] < j:
            a[i+k] = a[k]
            k += 1
        i += k
        j -= k
    return a

def solve(i, li):
    ans = 0
    while True:
        if i < 0 or len(li) <= i or visited[i]:
            break
        if li[i] < len(t):
            visited[i] = True
            break
        if li[i] >= len(t):
            visited[i] = True
            ans += 1
            i += len(t)
    return ans

#sを伸ばす
new_s = s
while True:
    if len(new_s) > len(t):
        s = new_s
        break
    new_s += new_s

s = s*3
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans1 = 0
for i in range(len(li)):
    ans1 = max(ans1, solve(i, li))

s += s
li = z_algorithm(t + s)[len(t):]
visited = [False] * len(li)
ans2 = 0
for i in range(len(li)):
    ans2 = max(ans2, solve(i, li))

if ans1 == ans2:
    print(ans1)
else:
    print(-1)