Harryxun/stf_run huggingface dataset:
n,m = map(int,input().split())
s = list(input())
edges = [tuple(map(int,input().split())) for i in range(m)]


def addEdge(graph,u,v):
    graph[u].add(v)


def deleteNode(graph,node):
    graph.pop(node,None)

from collections import defaultdict
graphAB = defaultdict(set)
graphABopp = defaultdict(set)

connodes = set()
for i,j in edges:
    ii = min(i,j)
    jj = max(i,j)
    addEdge(graphAB,ii,jj)
    addEdge(graphABopp,jj,ii)
    if i != j:
        connodes.add(i)
        connodes.add(j)



def adjAB(node):
    Aflag = 'A' in map(lambda x:s[x-1],graphAB[node])
    Aflag = Aflag or 'A' in map(lambda x:s[x-1],graphABopp[node])
    Bflag = 'B' in map(lambda x:s[x-1],graphAB[node])
    Bflag = Bflag or 'B' in map(lambda x:s[x-1],graphABopp[node])
    if Aflag and Bflag:
        return(True)
    else:
        return(False)



visitlist = [i for i in connodes if not adjAB(i)]
#print(visitset)

while bool(visitlist):
    i = visitlist.pop()
    for j in graphAB[i]:
        graphABopp[j].remove(i)
        if not adjAB(j):
            visitlist.append(j)
            #print(visitset,'add')
    for j in graphABopp[i]:
        graphAB[j].remove(i)
        if not adjAB(j):
            visitlist.append(j)
            #print(visitset,'add')
    graphAB.pop(i,None)
    graphABopp.pop(i,None)

#print(graphAB)
#print(graphABopp)


if graphAB == {} and graphABopp == {}:
    print('No')
else:
    print('Yes')





### FIXED CODE ###

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

ans = 0
acm = 0
for i in ass:
    acm += i
    if x >= acm:
        ans +=1

if acm < x:
    ans -= 1

print(ans)
s=input()
a,b=s.count("a"),s.count("b"),s.count("c")
print("NO" if max(a,b,c)-min(a,b,c)>1 else"YES")

### FIXED CODE ###

s=input()
a,b,c=s.count("a"),s.count("b"),s.count("c")
print("NO" if max(a,b,c)-min(a,b,c)>1 else"YES")
import numpy as np

n, k = map(int, input().split())
A = np.array(list(map(int, input().split())))

S = A.cumprod().tolist()
#print(S)
tmp = S[k-1]
for i in range(n-k):
    if tmp < S[k+i]/S[i]:
        print("Yes")
    else:
        print("No")
    #print(tmp, S[k+i]/S[i])

    tmp = S[k+i]/S[i]


### FIXED CODE ###

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

for i in range(n-k):
    if A[i] < A[k+i]:
        print("Yes")
    else:
        print("No")
def main():
    n, a, b = map(int, input().split())
    if abs(a - b) % 2 == 0:
        print(abs(a - b) // 2)
    else:
        mi = min(a, b) - 1
        ma = n - max(a, b)
        print(min(mi, ma) + (abs(a - b) + 1 // 2))


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    n, a, b = map(int, input().split())
    if abs(a - b) % 2 == 0:
        print(abs(a - b) // 2)
    else:
        mi = min(a, b) - 1
        ma = n - max(a, b)
        print(min(mi, ma) + (abs(a - b) + 1) // 2)


if __name__ == '__main__':
    main()
n = int(input())
m = n%10
if m == 2 or m == 4 or m == 5 or m == 7 or m == 9:
  return 'hon'
elif m == 0 or m == 1 or m == 6 or m == 8:
  return 'pon'
elif m == 3:
  return 'bon'

### FIXED CODE ###

n = int(input())
m = n%10
if m == 2 or m == 4 or m == 5 or m == 7 or m == 9:
  print('hon')
elif m == 0 or m == 1 or m == 6 or m == 8:
  print('pon')
elif m == 3:
  print('bon')
input().split()
s = int(a[0])
w = int(a[1])
 
if w >= s:
    print('unsafe')
else:
    print('safe')

### FIXED CODE ###

a = input().split()
s = int(a[0])
w = int(a[1])
 
if w >= s:
    print('unsafe')
else:
    print('safe')
S = map(int, input().split())
 
cnt = 0
for x in range(K + 1):
    for y in range(K + 1):
        if 0 <= S - x - y <= K:
            cnt += 1
print(cnt)

### FIXED CODE ###

k, s = (int(x) for x in input().split())
 
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k:
            count += 1
print(count)
import sys
input = sys.stdin.readline
def main():  
    S = list(input())
    S.pop()
    length=len(S)
    dp = [0]*13
    dp[0]=1
    mul=1
    mod=1000000007
    for i in range(1,length+1):
        next_dp = [0]*13
        for j in range(13):
            if S[length-i] == "?":
                for k in range(10):
                    j_sub=(j+k*mul)%13
                    next_dp[j_sub]+=dp[j]
                    next_dp[j_sub]%=mod
            else:
                j_sub=(j+int(S[length-i])*mul)%13
                next_dp[j_sub]+=dp[j]
                next_dp[j_sub]%=mod
        dp=next_dp
        mul=mul*10
    print(dp[5]%1000000007, "d")
if __name__ == "__main__":
    main()

### FIXED CODE ###

A,B = list(map(int,input().split()))
if A > B:
    tmp = A
    A = B
    B = tmp

if (B-A)%2 == 0:
    print(B-(B-A)//2)
else:
    print("IMPOSSIBLE")
a, b, c, x = int(input()) for _ in range(4) 

ans = [(i, j, k) for i in range(a+1) for j in range(b+1) for k in range(c+1) if 500*i+100*j+50*k == x]
print(len(ans))


### FIXED CODE ###

a, b, c, x = (int(input()) for _ in range(4))

ans = [(i, j, k) for i in range(a+1) for j in range(b+1) for k in range(c+1) if 500*i+100*j+50*k == x]
print(len(ans))
s=list(input())
k=int(input())
for i in range(100):
    if s[i]!="1":
        p=i+1
        pnum=int(s[i])
        break

if k<p:
    print(1)
else:
    print(pnum)

### FIXED CODE ###

s=list(input())
k=int(input())
for i in range(len(s)):
    if s[i]!="1":
        p=i+1
        pnum=int(s[i])
        break
    p=101

if k<p:
    print(1)
else:
    print(pnum)
S = int(input())
h = int(S / (60*60))
m = int(S / 60) % 60
s = S % 60

print('{}:{}:{}'.format(h.m.s)

### FIXED CODE ###

S = int(input())
h = int(S // (60*60))
m = int(S / 60) % 60
s = S%60

print('{}:{}:{}'.format(h,m,s))
s = input()
c = s.count(1)
print(c)

### FIXED CODE ###

s = input()
c = s.count("1")
print(c)
t = input()
s = ''
for i in range(len(t)):
    if t[i] == 'P' or t[i] == 'D':
        s = s + t[i]
    elif t[i] == '?' and t[i-1] =='P':
        s = s + 'D'
    elif t[i] == '?' and t[i +1] == 'D':
        s = s + 'P'
    else:
        s = s + 'D'
print(s)

### FIXED CODE ###

t = input()
m=len(t)
s = ''
for i in range(len(t)):
    if t[i] == 'P' or t[i] == 'D':
        s = s + t[i]
         
    if t[i] =='?':
        s = s+'D'
print(s)
n,k = map(int, input().split(" "))
s = input()
s[k-1] = s[k-1].lower()
print(s)


### FIXED CODE ###

n,k = map(int, input().split(" "))
s = list(input())
s[k-1] = s[k-1].lower()
print("".join(s))
N = int(input())
P = list(map(int,input().split()))

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

for i,p in enumerate(P) :
    A[p] += i
    B[p] += i

print(*A)
print(*B)


### FIXED CODE ###

N = int(input())
P = list(map(lambda x: int(x)-1, input().split()))

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

for i,p in enumerate(P) :
    A[p] += i
    B[p] += i

print(*A)
print(*B)
n, m=map(int,input().split())
a=list(map(int, input().split()))

for i in range(m):
    b,c=map(int,input().split())
    a+=([c]*b)

a.sort()
a.reverse()
ans=0

for i in range(n):
    ans+=a[i]

print(ans)


### FIXED CODE ###

a,b=map(int,input().split())
if a>=13:
    print(b)
elif 6<=a<13:
    print(b//2)
else:
    print(0)
I=lambda:map(int,input().split())
N=0xfffff
n,q=I()
c=list(I())
Q=[]
R=range
for i in R(q):l,r=I();Q.append(l<<40|r<<20|i)
Q.sort()
A=[[]for i in R(N)]
for i in R(n):A[c[i]].append(i)
B=[0]*N
def P(i,x):
	i+=1
	while i<=n:B[i]+=x;i+=i&-i
for i in A:
	if i:P(i[0],1);i.reverse()
t=0
o=[0]*q
for x in Q:
	l=x>>40-1
	r=x>>20&N
	i=x&N
	while t+1<l:
		b=A[c[t]]
		P(b[-1],-1)
		b.pop()
		if b:P(b[-1],1)
		t+=1
	while r:o[i]+=B[r];r-=r&-r
	while l:o[i]-=B[l];l-=l&-l
for i in o:print(i)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(lambda x: int(x) - 1, input().split()))
query = []
for i in range(q):
    l, r = map(lambda x: int(x) - 1, input().split())
    query.append(l << 40 | r << 20 | i)

query.sort()
ball = [list() for i in range(n)]
for i, x in enumerate(c):
    ball[x].append(i)

# binary indexed tree
bit = [0] * (n + 1)
def add(i, x):
    i += 1
    while i <= n:
        bit[i] += x
        i += i & -i

def get(i):
    i += 1
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s

for i in ball:
    if i:
        add(i[0], 1)
        i.reverse()

at = 0
ans = [0] * q
for x in query:
    l = x >> 40
    r = x >> 20 & 0xfffff
    i = x & 0xfffff
    while at < l:
        b = ball[c[at]]
        add(b[-1], -1)
        b.pop()
        if b:
            add(b[-1], 1)
        at += 1
    ans[i] = get(r) - get(l - 1)

for i in ans:
    print(i)
a,b = map(int,input().split())
import math
c = math.ceil(a/0.08)
d = round(b/ (0.1))
e = math.floor((a+1)/0.08)
f = round((b+1)/0.1)-1
i = c
j = -1
for i in range(c,e+1):
    if d <= i <= f:
        j = i
        break
    else:
        i = i+1
print(j

### FIXED CODE ###

a,b = map(int,input().split())
import math
c = math.ceil(a/0.08)
d = round(b/ (0.1))
e = math.ceil((a+1)/0.08)-1
f = round((b+1)/0.1)-1
i = c
j = -1
for i in range(c,e+1):
    if d <= i <= f:
        j = i
        break
    else:
        i = i+1
print(j)
from copy import deepcopy
s = list(input())
K = int(input())
dummy = "A"
S = deepcopy(s)
if len(set(S)) == 1:
    print(len(S)*K//2)
else:
    replace_cnt = 0
    for i in range(1, len(S)):
        if S[i] == S[i-1]:
            S[i] = dummy
            replace_cnt += 1
    if S[0] != S[-1]:
        print(replace_cnt*K)
    else:
        S = deepcopy(s)
        replace_cnt_two = 0
        l = len(S)
        for i in range(1, l*2):
            if S[i%l] == S[(i-1)%l]:
                S[i] = dummy
                replace_cnt_two += 1
        diff = replace_cnt_two - replace_cnt
        print(diff*(K-1)+replace_cnt)


### FIXED CODE ###

from copy import deepcopy
s = list(input())
K = int(input())
dummy = "A"
S = deepcopy(s)
if len(set(S)) == 1:
    print(len(S)*K//2)
else:
    replace_cnt = 0
    for i in range(1, len(S)):
        if S[i] == S[i-1]:
            S[i] = dummy
            replace_cnt += 1
    if S[0] != S[-1]:
        print(replace_cnt*K)
    else:
        S = s+s
        replace_cnt_two = 0
        for i in range(1, len(S)):
            if S[i] == S[i-1]:
                S[i] = dummy
                replace_cnt_two += 1
        diff = replace_cnt_two - replace_cnt
        print(diff*(K-1)+replace_cnt)
n, M, k = map(int,input().split())
a_l = list(map(int,input().split()))
b_l = list(map(int,input().split()))
read_a = [0]*n
read_b = [0]*M
time = 0
ans = 0
memo = 0
for j in range(n):
    if time + a_l[j] <= k:
        time += a_l[j]
        read_a[j] = 1
        memo = j
        ans = j+1
    else:
        break

kotae = [ans]


def dfs(i,a,t,m):
    global kotae
    if i < M:
        if b_l[i] + t <= k:
            tt = t + b_l[i]
            aa = a + 1
            kotae.append(aa)
            ii = i+1
            mm = m
            #print(aa)
            dfs(ii,aa,tt,mm)
            
        else:
            if m < 0:
                continue
            tt = t - a_l[m]
            mm = m - 1
            aa = a - 1
            ii = i
            #print(aa)
            dfs(ii,aa,tt,mm)
            #print(aa)


dfs(0,ans,time,memo)


print(max(kotae))
    





### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
n, M, k = map(int,input().split())
a_l = list(map(int,input().split()))
b_l = list(map(int,input().split()))
read_a = [0]*n
read_b = [0]*M
time = 0
ans = 0
memo = -1
for j in range(n):
    if time + a_l[j] <= k:
        time += a_l[j]
        read_a[j] = 1
        memo = j
        ans = j+1
    else:
        break

kotae = [ans]


def dfs(i,a,t,m):
    global kotae
    if i < M:
        if b_l[i] + t <= k:
            tt = t + b_l[i]
            aa = a + 1
            kotae.append(aa)
            ii = i+1
            mm = m
            #print(aa)
            dfs(ii,aa,tt,mm)
            
        else:
            if m >= 0:
                tt = t - a_l[m]
                mm = m - 1
                aa = a - 1
                ii = i
                dfs(ii,aa,tt,mm)
            


dfs(0,ans,time,memo)


print(max(kotae))
import numpy as np
a,b = map(int,input().split())
moda=np.mod(a,2019)
modb=np.mod(b,2019)
if (modb<=moda)or((b-a)>=2018):
    print(0)
    exit()

num =list(range(moda,modb+1))
ans = 10000
for i,l in enumerate(num):
    if i == len(num)-1:
        break
    for r in num[i+1:]:
        ans = min(np.mod(l*r,2019),ans)
print(ans)

### FIXED CODE ###

import numpy as np
a,b = map(int,input().split())
moda=np.mod(a,2019)
modb=np.mod(b,2019)
if (modb<=moda)or((b-a)>=673):
    print(0)
    exit()

num =list(range(moda,modb+1))

ans = 10000
for i,l in enumerate(num):
    if i == len(num)-1:
        break
    for r in num[i+1:]:
        ans = min(np.mod(l*r,2019),ans)
print(ans)
s=int(input().replace(' ',''))
print(['YES','NO'][s%4])

### FIXED CODE ###

s=input().split()
s=int(''.join(s))
if s%4==0:
  print('YES')
else:
  print('NO')
import sys
from collections import Counter

#[(105, 3), (120, 1), (106, 1), (119, 1)]
def selection(l1, l2, x ,y):
    
    #print('{}, {}'.format(x, y))
    
    #x yがlengthを超えたとき
    if x >= len(l1) or y >= len(l2):
        return x - 1, y - 1
    
    #それぞれの出現値が同じ場合
    if l1[x][0] == l2[y][0]:
            
        #出現回数が同じとき
        if l1[x][1] == l2[y][1]:
            x += 1
            y += 1
            return selection(l1, l2, x ,y)
    
    #出現回数を比較
    if l1[x][1] > l2[y][1]:
        y -= 1
        return x , y
        
    if l1[x][1] < l2[y][1]:
        x -= 1
        return x , y
    
    return x, y

def main():
    input = sys.stdin.readline
    
    n = int(input())
    m = [int(i) for i in input().split()]
    
    even = [m[i] for i, _ in enumerate(m) if i % 2 == 0]
    odd = [m[i] for i, _ in enumerate(m) if i % 2 == 1]
    
    even_c = Counter(even).most_common()
    odd_c = Counter(odd).most_common()
    
    #print(even_c)
    #print(odd_c)
    
    e, o = selection(even_c, odd_c, 0 ,0)
    
    e = 0 if e < 0 else e
    o = 0 if o < 0 else o
    
    #print('{}, {}'.format(e, o))
    
    #全部ばらばら
    if(even_c[e][1] + odd_c[o][1] == 2):
        print(len(m) - 2)
        return
    
    #全部一緒
    if even_c[e][1] == odd_c[o][1] and even_c[e][0] == odd_c[o][0]:
        print(int(len(m) / 2) )
        return
    
    print( len(m) - (even_c[e][1] + odd_c[o][1]) )
    
    
if __name__ == '__main__':
    main()
    

### FIXED CODE ###

import sys
from collections import Counter
 
def main():
    input = sys.stdin.readline
    
    n = int(input())
    m = [int(i) for i in input().split()]
    
    #偶数列 奇数列
    even = [m[i] for i, _ in enumerate(m) if i % 2 == 0]
    odd = [m[i] for i, _ in enumerate(m) if i % 2 == 1]
    
    #頻値を取り出す
    even_c = Counter(even).most_common()
    odd_c = Counter(odd).most_common()
    
    ans = -1
    
    #print(even_c)
    #print(odd_c)
    #print(len(even_c))
    
    #最頻値の比較
    if even_c[0][0] != odd_c[0][0]:
        ans = len(m) - (even_c[0][1] + odd_c[0][1])
    
    #偶数列と奇数列の最頻値の数字が同じかつ、全て同じ数字じゃない
    elif even_c[0][0] == odd_c[0][0] and len(even_c) > 1:
        ans1 = len(m) - (even_c[0][1] + odd_c[1][1])
        ans2 = len(m) - (even_c[1][1] + odd_c[0][1])
        ans = ans1 if ans1 <= ans2 else ans2
    
    #全て同じ
    else:
        ans = even_c[0][1]
        
    #出力
    print(ans)
    
if __name__ == '__main__':
    main()
import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


A, B, C, D = map(int, input().split())

# A以上B以下でCで割り切れる数の個数
x1 = (A-1) // C
x2 = B // C
x = x2 - x1
#print("x:", x)
# A以上B以下でDで割り切れる数の個数
y1 = (A-1) // D
y2 = B // D
y = y2 - y1
#print("y", y)
# A以上B以下でC,Dで割り切れる数の個数
z1 = (A-1) // lcm(C, D)
z2 = B // lcm(C, D)
z = z2 - z1
#print("lcm:{}".format(lcm(C, D)))
#print("z", z)

# A~B間の整数 - Cの倍数とDの倍数の個数 + CでもDでも割り切れる個数
not_d = B - A+1 - (x + y - z)
print(not_d)


### FIXED CODE ###

""" import math


def lcm(x, y):
    return (x * y) // math.gcd(x, y)


A, B, C, D = map(int, input().split())

# A以上B以下でCで割り切れる数の個数
x1 = (A-1) // C
x2 = B // C
x = x2 - x1
#print("x:", x)

# A以上B以下でDで割り切れる数の個数
y1 = (A-1) // D
y2 = B // D
y = y2 - y1
#print("y", y)

# A以上B以下でC,Dで割り切れる数の個数
z1 = (A-1) // lcm(C, D)
z2 = B // lcm(C, D)
z = z2 - z1
#print("lcm:{}".format(lcm(C, D)))
#print("z", z)

# A~B間の整数 - Cの倍数とDの倍数の個数 + CでもDでも割り切れる個数
not_d = B - (A+1) - (x + y - z)
print(int(not_d))
 """

a, b, c, d = map(int, input().split())

total = b - a + 1


def lem(A, B):
	AB = A * B
	while B != 0:
		A, B = B, A % B
	return AB // A


bsep = (b // c) + (b // d) - (b // lem(c, d))
asep = (a-1) // c + (a-1) // d - (a-1) // lem(c, d)

ans = total - bsep + asep
print(ans)
def isCLKWISE(ph):
    return ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) >= 0
      
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            if isCLKWISE(phU) : break
            else :
                del phU[-2]
                if len(phU) == 2 : break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            if isCLKWISE(phL) : break
            else :
                del phL[-2]
                if len(phL) == 2 : break
    ph = phU + phL[1:-1]
    return ph
  
n = range(int(input()))
P = []
for i in n:
    P.append([int(x) for x in input().split()])
      
Q = ConvexHullScan(P)
Q.reverse()
print(len(Q))
idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(Q)])[2]
R = Q[idx:] + Q[:idx]
for r in R : print(r[0],r[1])

### FIXED CODE ###

def isCLKWISE(ph) : return not ((ph[-1][0] - ph[-3][0])*(- ph[-3][1] + ph[-2][1]) - (ph[-2][0] - ph[-3][0])*(- ph[-3][1] + ph[-1][1] ) < 0)
      
def ConvexHullScan(P):
    P = sorted(P)
    phU = [P[0],P[1]]
    for p in P[2:]:
        phU.append(p)
        while(True):
            try :
                if isCLKWISE(phU) : break
                else : del phU[-2]
            except IndexError : break
    phL = [P[-1],P[-2]]
    for p in P[-3::-1]:
        phL.append(p)
        while(True):
            try :
                if isCLKWISE(phL) : break
                else : del phL[-2]
            except IndexError : break
    ph = phU + phL[1:-1]
    return ph
  
P = [[int(x) for x in input().split()] for _ in range(int(input()))]
P = ConvexHullScan(P)
P.reverse()
print(len(P))
idx = min([[x[1][1],x[1][0],x[0]] for x in enumerate(P)])[2]
for p in P[idx:] + P[:idx] : print(p[0],p[1])
x, y = map(int, raw_input().split())
print(x + y / 2)



### FIXED CODE ###

a = int(input())
b = int(input())
c = int(input())
d = int(input())

print(min(a, b) + min(c, d))
n=int(input())
d=list(map(int,input().split()))

from collections import Counter
q=Counter(d)

if D[0]!=0:
    print(0)
    exit()

ans=1
for i in range(1,max(D)+1):
    ans*=q[i-1]**q[i]
print(ans%998244353)

### FIXED CODE ###

n = int(input())
d = list(map(int,input().split()))
 
from collections import Counter
q=Counter(d)

# 例外対応
if q[0]!=1 or d[0]!=0:
  print(0)
  exit()

ans = 1
for i in range(1,max(d)+1):
  ans *= q[i-1]**q[i]
  if ans == 0:
    break
print(ans%998244353)
a=int(input)
b=a%3600
c=a//3600
d=b%60
e=b//60
print(c,":",e,":",d)

### FIXED CODE ###

a=int(input())
b=a%3600
c=a//3600
d=b%60
e=b//60
print(str(c)+":"+str(e)+":"+str(d))
n = int(input())

s, t = map(input().split())

ans = ''

for i in range(n):
    ans += s[i]
    ans += t[i]

print(ans)

### FIXED CODE ###

n = int(input())

s, t =input().split()

ans = ''

for i in range(n):
    ans += s[i]
    ans += t[i]

print(ans)
from itertools import *
from collections import *
from bisect import *
s=list(input())
t=input()
sets=set(s)

a=len(s)*len(t)
maxcount=len(s)
for i in range(100):
    if maxcount<a
        maxcount**=10
    else:
        break


for T in t:
    if not T in sets:
        print(-1)
        exit()
N=len(s)
dic={}
for i in range(N):
    if not s[i] in dic:
        dic.update({s[i]:[i]})
    else:
        dic[s[i]].append(i)

count=1
prei=0
for i in range(len(t)):
    idx=bisect_left(dic[t[i]],prei)
    if idx<len(dic[t[i]]):
        prei=dic[t[i]][idx]
    else:
        prei=dic[t[i]][0]
        count+=N
    if i==len(t)-1:
        count+=prei



if count<=maxcount:
    print(count)
else:
    print(-1)


### FIXED CODE ###

from itertools import *
from collections import *
from bisect import *
s=list(input())
t=input()
sets=set(s)
"""
a=len(s)*len(t)
maxcount=len(s)
for i in range(100):
    if maxcount<a:
        maxcount**=10
    else:
        break
"""

for T in t:
    if not T in sets:
        print(-1)
        exit()
N=len(s)
dic={}
for i in range(N):
    if not s[i] in dic:
        dic.update({s[i]:[i]})
    else:
        dic[s[i]].append(i)

count=0
prei=0
for i in range(len(t)):
    idx=bisect_left(dic[t[i]],prei)
    if idx<len(dic[t[i]]):
        prei=dic[t[i]][idx]+1
    else:
        prei=dic[t[i]][0]+1
        count+=N
    if i==len(t)-1:
        count+=prei



if count<=len(s)*(10**100):
    print(count)
else:
    print(-1)
import math

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

G = math.gcd(a,b)
L = []

for i in range(2,int(math.sqrt(G))+1):
    if G%i==0:
        for j in L:
            if i%j==0:
                break
        else:
            L.append(i)

print(len(L)+1)

### FIXED CODE ###

from math import sqrt

a,b = map(int,input().split())
 
L = []
 
if a < b: a,b = b,a
while b!=0:
    r = a%b
    a,b = b,r
 
G = a
 
for i in range(2,int(sqrt(G))+1):
    if G%i==0:
        L.append(i)
        while G%i==0:
            G/=i

if G!=1:
    L.append(G)

print(len(L)+1)
N = int(input())
a = list(map(int, input().split()))
color = set()
rainbow = 0

for n in range(N):
  if 1 <= a[n] < 400:
    color.add("gray")
  elif 400 <= a[n] < 800:
    color.add("brown")
  elif 800 <= a[n] < 1200:
    color.add("green")
  elif 1200<= a[n] < 1600:
    color.add("water")
  elif 1600 <= a[n] < 2000:
    color.add("blue")
  elif 2000 <= a[n] < 2400:
    color.add('yellow')
  elif 2400 <= a[n] < 2800:
    color.add('orange')
  elif 2800 <= a[n] < 3200:
    color.add('red')
  else:
    rainbow += 1

if color_min > rainbow:
  color_min = len(color)
else:
  color_min = rainbow
  
color_max = color_min + rainbow

    
print(f'{color_min} {color_max}')


### FIXED CODE ###

N = int(input())
a = list(map(int, input().split()))
color = set()
rainbow = 0

for n in range(N):
  if 1 <= a[n] < 400:
    color.add("gray")
  elif 400 <= a[n] < 800:
    color.add("brown")
  elif 800 <= a[n] < 1200:
    color.add("green")
  elif 1200<= a[n] < 1600:
    color.add("water")
  elif 1600 <= a[n] < 2000:
    color.add("blue")
  elif 2000 <= a[n] < 2400:
    color.add('yellow')
  elif 2400 <= a[n] < 2800:
    color.add('orange')
  elif 2800 <= a[n] < 3200:
    color.add('red')
  else:
    rainbow += 1

if len(color) == 0:
	color_min = 1 
	color_max = rainbow
else:
  color_min = len(color)
  color_max = color_min + rainbow

    
print(f'{color_min} {color_max}')
import ipdb
from itertools import combinations
N,K = map(int,input().split())
A = list(map(int,input().split()))
cmin = 10**12
for x in combinations(range(1,N),K-1):
    C = A[:]
    B = [0]
    B += x
    B = sorted(B)
    cnt = 0
    for i in range(1,K):
        j0 = B[i-1]
        j1 = B[i]
        h = 0
        for j in range(j0,j1):
            h = max(h,C[j])
        if C[j1]<=h:
            cnt += h+1-C[j1]
            C[j1] = h+1
    cmin = min(cmin,cnt)
print(cmin)

### FIXED CODE ###

from itertools import combinations
N,K = map(int,input().split())
A = list(map(int,input().split()))
cmin = 10**12
for x in combinations(range(1,N),K-1):
    C = A[:]
    B = [0]
    B += x
    B = sorted(B)
    cnt = 0
    for i in range(1,K):
        j0 = B[i-1]
        j1 = B[i]
        h = 0
        for j in range(j0,j1):
            h = max(h,C[j])
        if C[j1]<=h:
            cnt += h+1-C[j1]
            C[j1] = h+1
    cmin = min(cmin,cnt)
print(cmin)
if N < 10:
    print(N)
elif 10 <= N < 100:
    print(9)
elif 100 <= N < 1000:
    print(N - 90)
elif 1000 <= N < 10000:
    print(909)
elif 10000 <= N < 100000:
    print(N-9090)
else:
    print(90909)

### FIXED CODE ###

N = int(input())

ans = 0

for i in range(1, N + 1):
    if len(str(i)) % 2 == 1:
        ans += 1
print(ans)