Harryxun/stf_run huggingface dataset:
from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if x<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)
#print(lst)
fac1=[1]
fac2=[1]
C1=C-1
C2=C+1
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else fac1[idx])
    bit=value
    count=0
    while value and _C:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))


### FIXED CODE ###

from heapq import *
import sys
from collections import *
from itertools import *
from decimal import *
import copy
from bisect import *
import math
sys.setrecursionlimit(4100000)
def gcd(a,b):
    if(a%b==0):return(b)
    return (gcd(b,a%b))
input=lambda :sys.stdin.readline().rstrip()


N=int(input())
X=input()
C=X.count("1")

lst=[]
lstcount=[]
for x in [C-1,C+1]:
    flg=0
    if x<=0:
        lst.append(0)
        lstcount.append(0)
    else:
        Z=0
        p=1
        for i in range(N):
            if X[-i-1]=="1":
                Z+=p
            p*=2
            if Z>=x:
                Z%=x
                flg=1
            if flg:
                p%=x
        lst.append(Z)
        lstcount.append(flg)
#print(lst)
fac1=[1]
fac2=[1]
C1=max(C-1,1)
C2=max(C+1,1)
for i in range(N):
    fac1.append(fac1[-1]*2%C1)
    fac2.append(fac2[-1]*2%C2)

for i in range(N):

    _C=C+(1 if X[i]=="0"  else -1 )
    if _C==0:
        print(0)
        continue
    if  X[i]=="0":
        lstidx=1
    else:
        lstidx=0

    idx=(N-1-i)

    value=lst[lstidx]+(fac2[idx] if  X[i]=="0" else -fac1[idx])
    #print(value,X[i]=="0",lst,C-1,C+1)
    bit=value
    count=0
    while value and _C:
        count+=1
        value%=_C
        _C=0
        bit=value
        while bit:
            _C+=bit&1
            bit>>=1
    print(max(count,1))
def sr(x):
    y = ''
    for i in range(len(x)-1,-1,-1):
        y = '%s%s' %(y,x[i])
        print(y)
    print(y)    
    return y

s = input()
q = int(input())

for i in range(q):
    x = input().split()
    
    if (x[0] == '1'):
        #s = s[::-1]
        s = sr(s)
    else:
        s = '%s%s'%(x[2],s) if (x[1] == '1') else '%s%s'%(s,x[2])

print(s)


### FIXED CODE ###

from collections import deque

revFlag = False

s = deque(input())
q = int(input())

for i in range(q):
    a,b,c, *_ = input().split() + [None, None]
    
    if(a == '1'):
        revFlag = not revFlag
        
    else:
        b = int(b)
        if(revFlag):
            b = (int(b)%2)+1
        
        if(b == 1):
            s.appendleft(c)
        else:
            s.append(c)
            
    #print(_,*s, sep="")

if(revFlag):
    s.reverse()
    
print(*s, sep='')
#c = [list(map(int,input().split())) for _ in range(5)]
c = [int(input()) for _ in range(5)]

last = 10

for i in range(5):
    if c[i][0] % 10 ==  0:
        continue
    else:
        if last > c[i][0] % 10:
            last = c[i][0] % 10
            idx = i
    
ans = 0


for i in range(5):
    if i == idx:
        ans = ans + c[i][0]
    else:
        if c[i][0] % 10 == 0:
            ans = ans + c[i][0]
        else:
            ans= ans + ( c[i][0] // 10 + 1 ) * 10


print(ans)

### FIXED CODE ###

c = [int(input()) for _ in range(5)]

last = 10

idx = 0

for i in range(5):
    if c[i] % 10 ==  0:
        continue
    else:
        if last > c[i] % 10:
            last = c[i] % 10
            idx = i
    
ans = 0


for i in range(5):
    if i == idx:
        ans = ans + c[i]
    else:
        if c[i] % 10 == 0:
            ans = ans + c[i]
        else:
            ans= ans + ( c[i] // 10 + 1 ) * 10


print(ans)
import math
2 * R * math.pi

### FIXED CODE ###

print(int(input()) * 6.28)
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def solve1(N, W, weight, value):
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for w in range(W + 1):
            if w - weight[i] >= 0:
                dp[i + 1][w] = dp[i][w - weight[i]] + value[i]
            if dp[i + 1][w] < dp[i][w]:
                dp[i + 1][w] = dp[i][w]

    return dp[N][W]


def solve2(N, W, weight, value):
    w0 = weight[0]
    M = W // w0
    if M == 0:
        return 0

    weight_adj = [w - w0 for w in weight]
    w_total = sum(weight_adj)

    dp = [[[0] * (w_total + 1) for j in range(N + 1)] for i in range(M + 1)]
    for i in range(M):
        for j in range(N):
            for w in range(w_total + 1):
                if w - weight_adj[j] >= 0:
                    dp[i + 1][j + 1][w] = dp[i][j][w - weight_adj[j]] + value[j]
                if dp[i + 1][j + 1][w] < dp[i + 1][j][w]:
                    dp[i + 1][j + 1][w] = dp[i + 1][j][w]
                if dp[i + 1][j + 1][w] < dp[i][j + 1][w]:
                    dp[i + 1][j + 1][w] = dp[i][j + 1][w]

    return max(dp[M][N][W - w0 * M], dp[M - 1][N][min(W - w0 * (M - 1), w_total)])


def main():
    N, W, *wv = map(int, read().split())
    weight = wv[::2]
    value = wv[1::2]

    if weight[0] < 500:
        ans = solve1(N, W, weight, value)
    else:
        ans = solve2(N, W, weight, value)

    print(ans)
    return


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def solve1(N, W, weight, value):
    dp = [[0] * (W + 1) for _ in range(N + 1)]
    for i in range(N):
        for w in range(W + 1):
            if w - weight[i] >= 0:
                dp[i + 1][w] = dp[i][w - weight[i]] + value[i]
            if dp[i + 1][w] < dp[i][w]:
                dp[i + 1][w] = dp[i][w]

    return dp[N][W]


def solve2(N, W, weight, value):
    w0 = weight[0]
    M = W // w0
    if M == 0:
        return 0

    weight_adj = [w - w0 for w in weight]
    w_total = sum(weight_adj)

    dp = [[[0] * (w_total + 1) for j in range(N + 1)] for i in range(M + 1)]
    for i in range(M):
        for j in range(N):
            for w in range(w_total + 1):
                if w - weight_adj[j] >= 0:
                    dp[i + 1][j + 1][w] = dp[i][j][w - weight_adj[j]] + value[j]
                if dp[i + 1][j + 1][w] < dp[i + 1][j][w]:
                    dp[i + 1][j + 1][w] = dp[i + 1][j][w]
                if dp[i + 1][j + 1][w] < dp[i][j + 1][w]:
                    dp[i + 1][j + 1][w] = dp[i][j + 1][w]

    return max(dp[M][N][min(W - w0 * M, w_total)], dp[M - 1][N][min(W - w0 * (M - 1), w_total)])


def main():
    N, W, *wv = map(int, read().split())
    weight = wv[::2]
    value = wv[1::2]

    if weight[0] < 500:
        ans = solve1(N, W, weight, value)
    else:
        ans = solve2(N, W, weight, value)

    print(ans)
    return


if __name__ == '__main__':
    main()
w,h,x,y = map(double, input().split())
if  w/2 == x and h/2 == y:
	ans = 1
else:
	ans = 0
print (w*h/2,ans)

### FIXED CODE ###

w,h,x,y = map(int, input().split())
if  w/2 == x and h/2 == y:
	ans = 1
else:
	ans = 0
print (w*h/2.0,ans)
import sys
sys.setrecursionlimit(10**9)

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return x,self.dist[x]
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
            return self.parents[x],self.dist[x]
    
    def union(self,x,y,d):
        rx,_=self.find(x)
        ry,_=self.find(y)
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        print('Yes')
if __name__=='__main__':
    main()


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**9)

read=sys.stdin.read
class Unionfind():
    def __init__(self,n):
        self.parents=[-1]*n
        self.dist=[0]*n 
    
    def find(self,x):
        if self.parents[x]<0:
            return self.dist[x],x
        else:
            tmp=self.find(self.parents[x])
            self.dist[x]+=tmp[0]
            self.parents[x]=tmp[1]
        return self.dist[x], self.parents[x]
    
    def union(self,x,y,d):
        rx=self.find(x)[1]
        ry=self.find(y)[1]
        diff=self.dist[y]-self.dist[x]-d
        if rx==ry:
            if diff!=0:
                return True
            return False
        if diff<0:
            rx,ry=ry,rx
            diff=-diff
        self.parents[ry]=min(self.parents[ry],self.parents[rx]-diff)
        self.parents[rx]=ry
        self.dist[rx]=diff
        return False
    
def main():
    n,m,*lrd=map(int,read().split())
    v=Unionfind(n)
    for l,r,d in zip(*[iter(lrd)]*3):
        if v.union(l-1,r-1,d):
            print('No')
            break
    else:
        if max(-d-1 for d in v.parents if d<0) >10**9:
            print('No')
        else:
            print('Yes')
if __name__=='__main__':
    main()
import sys as chokudairedcoderatcoderowner
A,B,C = map(int,input().split())

if A == B:
  print(C)
else if A == C:
  print(B)
else:
  print(A)

### FIXED CODE ###

import sys as cghavcjhcbejwcbbsmbcjsdbcjdcadhbcjbdsjjcdjabjadbjsbcjdsbcsbcnsbcdnbcmbcmdabcdbjwhckfmknvskndleccdajbubcrjhebuoqbjhbjcdnaaayruegfubefruebhvy38bjhbvvbhcba
A,B,C = map(int,cghavcjhcbejwcbbsmbcjsdbcjdcadhbcjbdsjjcdjabjadbjsbcjdsbcsbcnsbcdnbcmbcmdabcdbjwhckfmknvskndleccdajbubcrjhebuoqbjhbjcdnaaayruegfubefruebhvy38bjhbvvbhcba.stdin.readline().split())

if A == B:
  print(C)
elif A == C:
  print(B)
else:
  print(A)
import itertools
import math
from scipy.special import comb

n, k = map(int, input().split())
mod = pow(10, 9)+7

for i in range(k):
    b = comb(k-1, i)
    r = comb(n-k+1, i+1)
    # print(n-k+1, i+1)
    print(int((b*r)%(mod)))


### FIXED CODE ###

from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0:
        return 1
    a = reduce(mul, range(n, n-r, -1))
    b = reduce(mul, range(1, r+1))
    return a//b

n, k = map(int, input().split())
mod = pow(10, 9) + 7

for i in range(k):
    if i > n-k:
        print(0)
    else:
        b = cmb(k-1, i)
        r = cmb(n-k+1, i+1)
        print(int((b*r)%mod))
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, s: "List[int]", c: "List[int]"):
    s=list(set(s));c=list(set(c))
    if len(s)!=len(c) or N>max(s):
        print(-1)
        exit()
    a=[0]*N
    for i in range(len(s)):
        a[i-1]=c[i]
    if a[0]==0:
        print(-1)
        exit()
    print("".join(map(str,a)))
    #print(s,c)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    s = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        s[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, s, c)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, s: "List[int]", c: "List[int]"):
    sc=[]
    for i in range(M):
        sc.append([s[i],c[i]])
    sc=list(map(list,set(map(tuple,sc))))
    sc.sort()
    for i in range(len(sc)):
        if sc[i][0]==1 and sc[i][1]==0 and not N==1:
            print(-1)
            exit()
    if M==0 and N==1:
        print(0)
        exit()
    if M==0 or len(sc)==1 and c[0]==0 and not s[0]==1:
        q=[1]
        for i in range(N-1):
            q.append(0)
        print("".join(map(str,q)))
        exit()
    for i in range(len(sc)-1):
        if sc[i][0]==sc[i+1][0]:
            print(-1)
            exit()
    #if N>max(set(s)):
    #    print(-1)
    #    exit()
    a=[0]*N
    for i in range(len(s)):
        a[s[i]-1]=c[i]
    if a[0]==0 and not N==1:
        a[0]=1
    print("".join(map(str,a)))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    s = [int()] * (M)  # type: "List[int]"
    c = [int()] * (M)  # type: "List[int]"
    for i in range(M):
        s[i] = int(next(tokens))
        c[i] = int(next(tokens))
    solve(N, M, s, c)

if __name__ == '__main__':
    main()
a = input().split()
a += input().split()
a += input().split()
n = int(input())
b = set([(int)(input()) for i in range(n)])

bingo = False
if set([a[0], a[1], a[2]).issubset(b):
	bingo = True
if set([a[3], a[4], a[5]).issubset(b):
	bingo = True
if set([a[6], a[7], a[8]).issubset(b):
	bingo = True
if set([a[0], a[3], a[6]).issubset(b):
	bingo = True
if set([a[1], a[4], a[7]).issubset(b):
	bingo = True
if set([a[2], a[5], a[8]).issubset(b):
	bingo = True
if set([a[0], a[4], a[8]).issubset(b):
	bingo = True
if set([a[2], a[4], a[6]).issubset(b):
	bingo = True
print(bingo)

### FIXED CODE ###

a = input().split()
a += input().split()
a += input().split()
n = int(input())
b = set([(input()) for i in range(n)])

bingo = False
if set([a[0], a[1], a[2]]).issubset(b):
	bingo = True
if set([a[3], a[4], a[5]]).issubset(b):
	bingo = True
if set([a[6], a[7], a[8]]).issubset(b):
	bingo = True
if set([a[0], a[3], a[6]]).issubset(b):
	bingo = True
if set([a[1], a[4], a[7]]).issubset(b):
	bingo = True
if set([a[2], a[5], a[8]]).issubset(b):
	bingo = True
if set([a[0], a[4], a[8]]).issubset(b):
	bingo = True
if set([a[2], a[4], a[6]]).issubset(b):
	bingo = True
if bingo:
  print("Yes")
else:
  print("No")
n = int(input())
t = map(int, input())
bottle_neck = min(t)
ti = int(n/bottle_neck)
if n % bottle_neck == 0:
    pass
else:
    ti+=1
print(ti+4)

### FIXED CODE ###

import math
n = int(input())
t=[]
for i in range(5):
    t.append(int(input()))
bottle_neck = min(t)
ti = math.ceil(n/bottle_neck)
print(ti + 4)
N = int(input())
A = list(map(int, input().split()))
ans = [0] * N
for i in range(n - 1):
    ans[A[i] - 1] += 1
for i in range(n):
    print(ans[i])



### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = [0] * N
for i in range(N - 1):
    ans[A[i] - 1] += 1
for i in range(N):
    print(ans[i])
a,b=map(int,input()).split())
print("Draw" if a==b else "Alice" if a==1 else "Bob"if b==1 else "Alice" if a>b else "Bob")

### FIXED CODE ###

a,b=map(int,input().split())
print("Draw"if a==b else"Alice"if a==1 else"Bob"if b==1 else"Alice"if a>b else"Bob")
from functools import reduce
import fractions

N = int(input().rstrip())
As = input().rstrip().split(" ")
As = [int(p) for p in As]

cand = As[0]
for i in range(1, N):
    cand = cand * As[i] // fractions.gcd(cand, As[i])

sum = 0

for num in As:
    sum = sum + cand / num

print(int(sum %  (10 ** 9 + 7)))


### FIXED CODE ###

from functools import reduce
import fractions

def lcm_base(x, y):
    return (x * y) // fractions.gcd(x, y)

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)

N = int(input().rstrip())
As = input().rstrip().split(" ")
As = [int(p) for p in As]

cand = lcm_list(As)

sum = 0

for num in As:
    sum = sum + cand // num

print(sum % int(1e9+7) )
n = input()
b = [int(x) for x in input().split()]
c = 0
while True:
    for i,x in enumerate(b):
        if x%2 != 0:
            break
        b[x] = int(x/2)
    c += 1
print(c)

### FIXED CODE ###

n = input()
b = [int(x) for x in input().split()]
c = 0
flg = True
while flg:
    for i,x in enumerate(b):
        if x!=0 and x%2 != 0:
            flg=False
            break
        b[i] = int(x/2)
    c += 1
print(c-1)
N = int(input())
Alist = list(map(int, input().split()))

Alist = [[idx+1, a] for (idx, a) in enumerate(Alist)]

Alist.sort(key=lambda x:x[1])

ans = [a for a, _ in Alist]
print(" ".join(ans))

### FIXED CODE ###

N = int(input())
Alist = list(map(int, input().split()))
 
Alist = [[idx+1, a] for (idx, a) in enumerate(Alist)]
 
Alist.sort(key=lambda x:x[1])
 
ans = [str(a) for a, _ in Alist]
print(" ".join(ans))
N, A, B = map(int, input().split())
 
rep = "b" * A + "r" * B
C = N // (A + B)
D = N % (A + B)
 
ans = A * C + min(A, D)
print(ans)

### FIXED CODE ###

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

C = N // (A + B)
D = N % (A + B)

ans = A * C + min(A, D)
print(ans)
for line in sys.stdin:
    array = [float(x) for x in line.split()]
    ar1 = array[0:3]
    ar2 = array[3:]
    i = ar1[0]
    ar1 = [x*ar2[0] for x in ar1]
    ar2 = [x*i for x in ar2]
    y = (ar1[2] - ar2[2])/(ar1[1]-ar2[1])
    ar1 = array[0:3]
    x = (ar1[2]-ar1[1]*y)/ar1[0]
    print('%.3f %.3f' % (round(x,3), round(y,3)))

### FIXED CODE ###

import sys

for line in sys.stdin:
    array = [float(x) for x in line.split()]
    ar1 = array[0:3]
    ar2 = array[3:]
    i = ar1[0]
    ar1 = [x*ar2[0] for x in ar1]
    ar2 = [x*i for x in ar2]
    y = (ar1[2] - ar2[2])/(ar1[1]-ar2[1])
    ar1 = array[0:3]
    x = (ar1[2]-ar1[1]*y)/ar1[0]
    print('%.3f %.3f' % (round(x,3), round(y,3)))
from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
box = [1]*(N+1)
flag = False
n1_pass = set()
n1_now = 0
for _ in range(M):
    x,y = [int(x) for x in stdin.readline().rstrip().split()]
    box[x] -= 1
    box[y] += 1
    if box[x] == 0:
        n1_pass.remove(x)
    if x == 1 and not flag:
        n1_pass.add(y)
        n1_now = y
        flag = True
    if flag and x == n1_now:
        n1_pass.add(y)
        n1_now = y
ans = 0
for i in n1_pass:
    if box[i] > 0:
        ans += 1
print(ans)

### FIXED CODE ###

from sys import stdin
N,M = [int(x) for x in stdin.readline().rstrip().split()]
box = [1]*(N+1)
red = [False]*(N+1)
red[1] = True
for _ in range(M):
    x,y = [int(x) for x in stdin.readline().rstrip().split()]
    if red[x]:
        red[y] = True
    box[x] -= 1
    box[y] += 1
    if box[x] == 0:
        red[x] = False
ans = 0
for i in red:
    if i:
        ans += 1
print(ans)
import sys
[print([670, 660, 633, 592, 540, 480, 415, 348, 282, 220, 165, 120, 84, 56, 35, 20, 10, 4, 1][abs(18 - int(e))]) for e in sys.stdin]


### FIXED CODE ###

import sys
d=[sum((10-abs(9-i))*(10-abs(9+i-j))for i in range(j+1))for j in range(19)[::-1]]+[0]*14
[print(d[abs(18-int(e))])for e in sys.stdin]
from sys import stdin

input = stdin.readline


def p_a():
    n = int(input())
    print(((n + 1) // 2) / n)


def p_b():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))

    print(sum(map(lambda x: x >= k)))


if __name__ == '__main__':
    p_b()


### FIXED CODE ###

from sys import stdin

input = stdin.readline


def p_a():
    n = int(input())
    print(((n + 1) // 2) / n)


def p_b():
    n, k = map(int, input().split())
    h = list(map(int, input().split()))

    print(sum(map(lambda x: x >= k, h)))


if __name__ == '__main__':
    p_b()
a,b=map(int,input().split())
c=int(input())
d=list(map(int,input().split()))
e=[input() for _ in range(b)]
f=list(map(int,input().split()))

print(a-c)

### FIXED CODE ###

import itertools
a,b=map(int,input().split())
c=[]
for i in range(1,b*2+1):
    c.append(list(map(int,input().split())))
n=c[1::2]
n=list(itertools.chain.from_iterable(n))
print(a-len(set(n)))
import math
A, B, H, M =map(int, input().split())
Hs = H*30 + M*0.5
Ms = 6*M
shita = Hs-Ms
shita = abs(shita)
if  shita >= 180:
    shita = 360 - shita
shita = math.radians(shita)
C = A*A + B*B - 2*A*B*(math.cos(shita))
print (math.sqrt(C))

### FIXED CODE ###

N = int(input())
N = N % 10
if N in (2, 4, 5, 7, 9):
    print ("hon")
elif N in (0, 1, 6, 8):
    print ("pon")
elif N == 3:
    print ("bon")
n = int(input())
a = list(map(int, input().split()))
if n % 2 == 0:
  dp = [[0, 0] for i in range(n)]
  dp[0][0] = a[0]
  dp[1][1] = a[1]
  dp[2][0] = a[0] + a[2]
  for i in range(3, n):
    dp[i][0] = dp[i - 2][0] + a[i]
    dp[i][1] = max(dp[i - 3][0], dp[i - 2][1]) + a[i]
  print(max(dp[n - 2][0], dp[n - 1][1]))
else:
  dp = [[0, 0, 0] for i in range(n)]
  dp[0][0] = a[0]
  dp[1][1] = a[1]
  dp[2][0] = a[0] + a[2]
  dp[2][2] = a[2]
  dp[3][1] = a[1] + a[3]
  dp[3][2] = a[0] + a[3]
  for i in range(3, n):
    dp[i][0] = dp[i - 2][0] + a[i]
    dp[i][1] = max(dp[i - 3][0], dp[i - 2][1]) + a[i]
    dp[i][2] = max(dp[i - 4][0], dp[i - 3][1], dp[i - 2][2]) + a[i]
  print(max(dp[n - 3][0], dp[n - 2][1], dp[n - 1][2]))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
if n % 2 == 0 and n >= 4:
  dp = [[0, 0] for i in range(n)]
  dp[0][0] = a[0]
  dp[1][1] = a[1]
  dp[2][0] = a[0] + a[2]
  for i in range(3, n):
    dp[i][0] = dp[i - 2][0] + a[i]
    dp[i][1] = max(dp[i - 3][0], dp[i - 2][1]) + a[i]
  print(max(dp[n - 2][0], dp[n - 1][1]))
elif n % 2 != 0 and n >= 5:
  dp = [[0, 0, 0] for i in range(n)]
  dp[0][0] = a[0]
  dp[1][1] = a[1]
  dp[2][0] = a[0] + a[2]
  dp[2][2] = a[2]
  dp[3][1] = a[1] + a[3]
  dp[3][2] = a[0] + a[3]
  for i in range(3, n):
    dp[i][0] = dp[i - 2][0] + a[i]
    dp[i][1] = max(dp[i - 3][0], dp[i - 2][1]) + a[i]
    dp[i][2] = max(dp[i - 4][0], dp[i - 3][1], dp[i - 2][2]) + a[i]
  print(max(dp[n - 3][0], dp[n - 2][1], dp[n - 1][2]))
elif n == 2:
  print(max(a[0], a[1]))
else:
  print(max(a[0], a[1], a[2]))
N = int(input())
A = list(map(int, input().split()))
x = [0]*(2*10**5)
for i in range(N-1):
    x[A[i]] += 1
for i in range(1,N+1):
    print(x[i])

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
x = [0]*(2*10**5+1)
for i in range(N-1):
    x[A[i]] += 1
for i in range(1,N+1):
    print(x[i])
s=input()
k=int(input())
cnt=0
same_length=1
for i in range(len(s)-1):
	if s[i]==s[i+1]:
		same_length +=1
	else:
		cnt+=int(same_length//2)
		same_length=1
cnt+=int(same_length//2)
if s[0]==s[-1] and s[-1]!=s[-2] and s[0]!=s[1]:
	cnt+=1
print(cnt*k)

### FIXED CODE ###

s=input()
k=int(input())
if len(s)==1:
	print(k//2)
	exit()
cnt=0
same_length=1
first=1
for i in range(len(s)-1):
 		 if s[i]==s[i+1]:
 		 	same_length+=1
 		 	if cnt==0:first+=1
 		 elif s[i]!=s[i+1]:
 		 	if cnt==0:s_left=first
 		 	cnt+=int(same_length//2)
 		 	same_length=1
if same_length==len(s):
	print(len(s)*k//2)
	exit()
s_right=same_length
cnt+=int(same_length//2)
if s[0]==s[-1] and s_left%2==1 and s_right%2==1:
	print(cnt*k+k-1)
else:
	print(cnt*k)
S = input()
T = input()

for i in range(len(T)):
  if i == 0:
    if T[:len(T)-i] in S:
      print(0)
  else:
    if T[:len(T)-i] in S and S[len(T)-i+1] != T[:len(T)-i]:
      print(i)

### FIXED CODE ###

S = input()
T = input()

ans = len(T)

for i in range(len(S)-len(T)+1):
  tmp = len(T)
  for j in range(len(T)):
    if T[j] == S[i+j]:
      tmp -= 1
      ans = min(ans,tmp)
print(ans)