Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python3

import sys
import math
import itertools

def required_visit_time(t, shop):
    a, b = shop
    return int((t - b) / (a + 1)) - 1

# shops はソート済み
def calc_dp_time(T, shops):
    t = T
    for s in shops:
        t = required_visit_time(t, s)
    return t

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = list(tuple(map(int, sys.stdin.readline().split())) for _ in range(N))

    shops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    dpmemo = None

    def dp(i, t):
        assert i >= 0
        assert t >= 0

        if i == 0:
            return 0

        if (i, t) in dpmemo:
            return dpmemo[i, t]

        h = i - 1
        r = required_visit_time(t, shops[h])
        n = max(dp(h, r) + 1, dp(h, t)) if r >= 0 else dp(h, t)
        dpmemo[i, t] = n
        return n

    dpmax = sum(1 for _ in itertools.takewhile(lambda x: x[0] > 0, shops))

    # dp(dpmax, t) | t = T と同じ値を得られる最小の t を二分探索
    dpmemo = {}
    ans = dp(dpmax, T)
    l = 0
    r = T + 1
    while l + 1 < r:
        m = int((l + r) / 2)
        dpmemo = {}
        n = dp(dpmax, m)
        if n < ans:
            l = m
        else:
            r = m

    t = r
    for i in range(dpmax, N):
        _, b = shops[i]
        t += 1 + b
        if t > T:
            break
        ans += 1

    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env pypy3

import sys
import math
import itertools
import bisect

INF = int(1e18)
T_MAX = int(1e9)

def main():
    N, T = map(int, sys.stdin.readline().split())
    shops = [tuple(map(int, sys.stdin.readline().split())) for _ in range(N)]

    nzshops = [(a, b) for a, b in shops if a > 0]
    zshops  = [(a, b) for a, b in shops if a == 0]

    nzshops.sort(key=lambda x: x[0] / (x[0] + x[1] + 1), reverse=True)
    zshops.sort()

    dp = [[0] + [INF] * int(math.log(T_MAX, 2)) for _ in range(len(nzshops) + 1)]
    for i in range(1, len(dp)):
        for c in range(1, len(dp[i])):
            a, b = nzshops[i - 1]
            t = dp[i - 1][c - 1] + 1
            dp[i][c] = min(dp[i - 1][c], t + t * a + b)

    rs = list(itertools.accumulate(1 + b for _, b in zshops))
    ans = max(c + bisect.bisect(rs, T - dp[-1][c])
            for c in range(len(dp[-1])) if dp[-1][c] <= T)

    print(ans)

if __name__ == '__main__':
    main()
n = int(input())
a = []
for i in range(n):
  ai, bi = list(map(int, input()))
  a.append((ai, bi, ai+bi))
a.sort(key = lambda x: x[2], reverse=True)
tak = 0
aok = 0
for i in range(n):
  if i%2 == 0:
    tak += a[i][0]
  else:
    aok += a[i][1]
print(tak - aok)
  

### FIXED CODE ###

n = int(input())
a = []
for i in range(n):
  ai, bi = list(map(int, input().split()))
  a.append((ai, bi, ai+bi))
a.sort(key = lambda x: x[2], reverse=True)
tak = 0
aok = 0
for i in range(n):
  if i%2 == 0:
    tak += a[i][0]
  else:
    aok += a[i][1]
print(tak - aok)
n, m, k = list(map(int, input().split()))
ns = list(map(int, input().split()))
ms = list(map(int, input().split()))

nss = [0]
for i, v in enumerate(ns): nss.append(nss[i] + ns[i])
mss = [0]
for i, v in enumerate(ms): mss.append(mss[i] + ms[i])

from bisect import bisect_left

mx = 0
for i in range(n + 1):
    if nss[i] > k:
        break

    v = k - nss[i]
    j = bisect_left(mss, v)
    print(i, nss, j, mss, k)
    if j < m and mss[j] != v:
        j -= 1

    mx = max(mx, i + j)

print(mx)


### FIXED CODE ###

n, m, k = list(map(int, input().split()))
ns = list(map(int, input().split()))
ms = list(map(int, input().split()))

nss = [0]
for i, v in enumerate(ns):
    nss.append(nss[i] + ns[i])

mss = [0]
for i, v in enumerate(ms):
    mss.append(mss[i] + ms[i])

mx = 0
j = m
for i in range(n + 1):
    if nss[i] > k:
        break

    while mss[j] > k - nss[i]:
        j -= 1
    
    mx = max(mx, i + j)

print(mx)
import math, sys
def lcm(a,b):
    return int(a*b/math.gcd(a,b))

if __name__ == '__main__':
    for line in sys.stdin:
        a,b = map(int,line.split())
        print(math.gcd(a,b),lcm(a,b))

### FIXED CODE ###

import sys
import fractions
def lcm(a,b):
    return int(a*b/fractions.gcd(a,b))

if __name__ == '__main__':
    for line in sys.stdin:
        a,b = map(int,line.split())
        print(int(fractions.gcd(a,b)),lcm(a,b))
a, b, c, d = map(int, input().split())
ans = max(0, min(b, d)) - max(a, c))
print(ans)

### FIXED CODE ###

a, b, c, d = map(int, input().split())
ans = max(0, min(b, d) - max(a, c))
print(ans)
n = int(input())
l = list(map(int, input().split()))

sum = 0

for i in range(i):
  sum += 1/l[i]
print(1/sum)

### FIXED CODE ###

n = int(input())
l = list(map(int, input().split()))

sum = 0

for i in range(n):
  sum += 1/l[i]
print(1/sum)
x = sort(list(map(int, input().split())))
ans = 0
if x[0]%2==x[1]%2:
    ans += (x[1] - x[0])//2
    ans += (x[2] - x[1])
else:
    ans += 1
    ans += (x[1] - x[0] + 1)//2
    ans += (x[2] - x[1])
print(ans)

### FIXED CODE ###

x = sorted(list(map(int, input().split())))
ans = 0
if x[0]%2==x[1]%2:
    ans += (x[1] - x[0])//2
    ans += (x[2] - x[1])
else:
    ans += 1
    ans += (x[1] - x[0] + 1)//2
    ans += (x[2] - x[1])
print(ans)
n = int(input())
table = [input() for i in range(n)]
print("{} {} {}".format(min(table),max(table),sum(table)))


### FIXED CODE ###

n = input()
table = list(map(int,input().split()))
print("{} {} {}".format(min(table),max(table),sum(table)))
def main():
  ## IMPORT MODULE
  #import sys
  from collections import Counter

  #sys.setrecursionlimit(100000)
  #input=lambda :sys.stdin.readline().rstrip()

  #f_inf=float("inf")
  #MOD=10**9+7
  
  if 'get_ipython' in globals(): 
    ## SAMPLE INPUT
    n = 64

  else:
    ##INPUT 
    n = input()
    #a, b = map(int, input().split())

  ## SUBMITION CODES HERE
  def prime_fact(n):
    P= []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            P.append(i)
            n //= i
    if n != 1:
        P.append(n)
    return P

  cnt = Counter(prime_fact(n))

  ans = 0
  for c in cnt.values():
    tmp = 1
    while c >= tmp:
      c -= tmp
      ans += 1
      tmp += 1
    
  print(ans)
    
main()

### FIXED CODE ###

from collections import Counter

def prime_fact(n):
    P= []
    for i in range(2, int(n ** 0.5) + 1):
        while n % i == 0:
            P.append(i)
            n //= i
    if n != 1:
        P.append(n)
    return P

n = int(input())
cnt = Counter(prime_fact(n))

ans = 0
for c in cnt.values():
  tmp = 1
  while c >= tmp:
    c -= tmp
    ans += 1
    tmp += 1
print(ans)
n, m = map(int, input())
ab = [tuple(map(int, input().split(" "))) for i in range(m)]

from_one, to_n = set(), set()
for ab_i in ab:
	if ab_i[0] == 1:
		from_one.add(ab_i[1])
	elif ab_i[0] == n:
		from_one.add(ab_i[1])
	
print("POSSIBLE" if from_one | to_n else "IMPOSSIBLE")

### FIXED CODE ###

n, m = map(int, input().split(" "))
ab = [tuple(map(int, input().split(" "))) for i in range(m)]

from_one, to_n = set(), set()
for ab_i in ab:
	if ab_i[0] == 1:
		from_one.add(ab_i[1])
	elif ab_i[1] == n:
		to_n.add(ab_i[0])
	
print("POSSIBLE" if from_one & to_n else "IMPOSSIBLE")
#!/usr/bin/env python
# coding: utf-8

# In[13]:


import sys
input = sys.stdin.readline


# In[26]:


NK = list(map(int, input()))
A = list(map(int, input()))
N = NK[0]
K = NK[1]


# In[16]:


def main():
    x0 = 1
    for i in range(K):
        x0 *= A[i]
    x = x0
    for j in range(K,N):
        score = x*A[j]//A[j-K]
        if score > x:
            print("Yes")
        else:
            print("No")
        x = score


# In[17]:


if __name__ == '__main__':
    main()


# In[ ]:






### FIXED CODE ###

#!/usr/bin/env python
# coding: utf-8

# In[2]:


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


# In[9]:


def main():
    for j in range(K,N):
        if A[j] > A[j-K]:
            print("Yes")
        else:
            print("No")


# In[10]:


if __name__ == '__main__':
    main()


# In[ ]:
x=int(input())
t=int(input())
print(max(0,x-t))

### FIXED CODE ###

x,t=map(int,input().split())
print(max(0,x-t))
count = {} #a~zの出現回数を記録
for i in range(26):
    count[(i)] = 0

while True:
    try:
        text = raw_input()
    except EOFError:
        break
    for i in range(len(text)):
        if(ord(text[i]) >= ord('a') and ord(text[i]) <= ord('z')):
            count[(ord(text[i]))-ord('a')] += 1
        if(ord(text[i]) >= ord('A') and ord(text[i]) <= ord('Z')):
            count[(ord(text[i]))-ord('A')] += 1

#出現回数の表示
for i in range(26):
    print '%s : %d' %(unichr(i+ord('a')), count[(i)])

### FIXED CODE ###

count = {}
for i in range(26):
    count[(i)] = 0

while True:
    try:
        x = raw_input()
    except:
        break
    for i in range(len(x)):
        if(ord('a') <= ord(x[i]) and ord(x[i]) <= ord('z')):
            count[(ord(x[i])-ord('a'))] += 1
        elif(ord('A') <= ord(x[i]) and ord(x[i]) <= ord('Z')):
            count[(ord(x[i])-ord('A'))] += 1

for i in range(26):
    print '%s : %d' %(chr(i+ord('a')), count[(i)])
exit(0)
s = input()
print(s[0]+(len(s)-2)+s[-1])

### FIXED CODE ###

s = input()
len = len(s)-2
print(s[0]+str(len)+s[-1])
S=input()
T=input()
tlen = len(T)


for i in range(tlen, 1):
    for k in range(0, tlen+1-i):
        Tinclude = T[k:i]
        print(tlen-i)
        break

### FIXED CODE ###

D,T,S = map(int,input().split())

if D/S > T:
    print("No")
else:
    print("Yes")
import math

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

S = a * b * math.sin(C) * 0.5

c2 = a ** 2 + b ** 2 - 2 * a * b * math.cos(C)

c = sqrt(c2)

L = a + b + c

h = 2 * S / a

print(S)
print(L)
print(h)

### FIXED CODE ###

import math

a, b, Cd = map(int, input().split())
Cr = math.radians(Cd)

S = a * b * math.sin(Cr) * 0.5

c2 = a ** 2 + b ** 2 - 2 * a * b * math.cos(Cr)

c = math.sqrt(c2)

L = a + b + c

h = 2 * S / a

print(S)
print(L)
print(h)
i = input().split()
h = int(i[0])
w = int(i[1])

if h == 1 or w == 1:
    print(1)

if (h * w % 2 == 0):
    print(h * w // 2)
else:
    print(h * w // 2 + 1)

### FIXED CODE ###

a = [1, 1, 1, 2, 1, 2, 1, 5, 2, 2, 1, 5, 1, 2, 1, 14, 1, 5, 1, 5, 2, 2, 1, 15, 2, 2, 5, 4, 1, 4, 1, 51]

k = int(input()) -1

print(a[k])
s = input()

count = 0

for i in (len(s)):
  if s[i] == '1':
    count = count + 1

print(count)

### FIXED CODE ###

n = str(input())
count = 0
for i in range(len(n)):
  if n[i] == '1':
    count += 1
  else:
    count += 0
print(count)
n,m = map(int, input().split())
while (n != 0 or m != 0):
    nlist = [0]
    mlist = [0]
    for i in range(n):
        nlist += [nlist[-1] + int(input())]
    for i in range(m):
        mlist += [mlist[-1] + int(input())]
    nsum = []
    msum = []
    
    for i in range(n):
        for k in range(i+1,n+1):
            c = nlist[k] - nlist[i]
            nsum.append(c)
    for i in range(m):
        for k in range(i+1,m+1):
            c = mlist[k] - mlist[i]
            msum.append(c)
    count = 0
    for i in nsum:
        count += msum.count(i)
    print(count) 
    n,m = map(int, input().split())


### FIXED CODE ###

while True:
    n,m = map(int, input().split())
    if n == 0 and m == 0:
        break
    nlist = [0]
    mlist = [0]
    for i in range(n):
        nlist += [nlist[-1] + int(input())]
    for i in range(m):
        mlist += [mlist[-1] + int(input())]

    l = [0for i in range(1000*1501)]
    for i in range(n):
        t = 0
        for k in range(i+1,n+1):
            t = nlist[k] - nlist[i]
            l[t] += 1
    count = 0
    for i in range(m):
        for k in range(i+1,m+1):
            t = mlist[k] - mlist[i]
            count += l[t]
    
    print(count)
N=int(input())
K=int(input())

d=len(str(N)) #桁数
a=int(str(N)[0]) #最上位桁の数
if K==1:
  print(9*(d-1)+a)
  
if K==2:
  l=9**2*(d-1)*(d-2)/2 #最上位0
  m=(a-1)*9*(d-1) #最上位1~a-1 
  for i in range(1,d):
    if int(str(N)[i])!=0:
      n=(int(str(N)[i]))+9*(d-i-1)
      break
  print(l+m+n)
  
if K==3:
  l=9**3*(d-1)*(d-2)*(d-3)/6
  m=(a-1)*9**2*(d-1)*(d-2)/2
  for i in range(1,d):
    if int(str(N)[i])!=0:
      n=(int(str(N)[i]))*9*(d-i-1)+9**2*(d-i-1)*(d-i-2)/2
      break
  print(l+m+n)  

### FIXED CODE ###

N=input()
K=int(input())

dpsm=[[0]*(K+1) for _ in range(len(N))] #dpsm[i][k]
dp=[[0]*(K+1) for _ in range(len(N))]

dpsm[0][0]=1
dpsm[0][1]=int(N[0])-1
dp[0][1]=1

for i in range(1,len(N)):
    for k in range(K-1,-1,-1):
        dpsm[i][k+1]+=dpsm[i-1][k]*9

    
    if N[i]=="0":
        for k in range(K,-1,-1):
            dpsm[i][k]+=dpsm[i-1][k]
            dp[i][k]+=dp[i-1][k]
    else:
        for k in range(K-1,-1,-1):
            dpsm[i][k+1]+=dp[i-1][k]*(int(N[i])-1)
            dp[i][k+1]+=dp[i-1][k]

        for k in range(K,-1,-1):
            dpsm[i][k]+=dpsm[i-1][k]
            dpsm[i][k]+=dp[i-1][k]
          
print(dp[-1][-1]+dpsm[-1][-1])
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:
        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))
from heapq import heappop, heappush
inputs = open(0).readlines()

from heapq import heappop, heappush
inputs = open(0).readlines()

n, m = map(int, inputs[0].split())
*A, = map(int, inputs[1].split())
BC = [tuple(map(int, bc.split())) for bc in inputs[2:]]

D = []
for a in A:
    heappush(D, a)
for b, c in BC:
    for _ in range(b):
        if c > D[0]:
            heappush(D, max(heappop(D), c))
print(sum(D))

### FIXED CODE ###

from heapq import heapify, heappushpop
from operator import itemgetter
inputs = open(0).readlines()

n, m = map(int, inputs[0].split())
*A, = map(int, inputs[1].split())
heapify(A)
BC = [tuple(map(int, bc.split())) for bc in inputs[2:]]
BC.sort(key=itemgetter(1), reverse=True)

for b, c in BC:
    for _ in range(b):
        if c > A[0]:
            _ = heappushpop(A, c)
        else:
            break
print(sum(A))
# -*- coding: utf-8 -*-

n = int(raw_input())
for i in range(n):
    A = map(int, raw_input().split())
    B = []
    C = []
    flag = True
    for i in range(5):
        B.append(A[2*i])
        C.append(A[2*i+1])
    for i in range(4):
        for j in range(i+1, 4)
            if B[j] > B[i]:
                flag = False
                break
            if C[ij > C[i]:
                flag = False
                break
    if flag:
        print "YES"
    else:
        print "NO"

### FIXED CODE ###

# -*- coding: utf-8 -*-

n = int(raw_input())
for i in range(n):
    A, B, C = [], [0], [0]
    A = map(int, raw_input().split())
    for i in range(10):
        if A[i] > B[0]:
            B.insert(0, A[i])
        elif A[i] > C[0]:
            C.insert(0, A[i])
        else:
            break
    if len(B) + len(C) == 12:
        print "YES"
    else:
        print "NO"
n = int(input())
K = 0
for i in range(n-2):
    if P[i]<P[i+1]<P[i+2] or P[i+2]<P[i+1]<P[i]:
        K += 1
        
print(K)

### FIXED CODE ###

#ABC132 B

n = int(input())
P = list(map(int,input().split()))
K = 0
for i in range(n-2):
    if (P[i] < P[i+1] and P[i+1] < P[i+2]) or (P[i+2] < P[i+1] and P[i+1] < P[i]):
        K += 1
        
print(K)
import sys
a,v=list(map(int,input().split()))
b,w=list(map(int,input().split()))
t=int(input())
if v-w==0:
  if a==b:
    print("YES")
  else:
    print("NO")
  sys.exit()
temp=(b-a)/(v-w)
if temp<0 or temp>t:
  print("NO")
else:
  print("YES")

### FIXED CODE ###

s=input()
print(s[0:3])
import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N = int(input())
    dams = list(map(int, input().split()))
    smallest_idx = 0
    for i in range(1,N):
        if dams[i] < dams[smallest_idx]:
            smallest_idx = i
    dams = dams[smallest_idx:] + dams[:smallest_idx]

    for i in range(0, dams[0]*2+1, 2):
        mts = [0]*N
        mts[0] = i
        for j in range(1,N):
            mts[j] = (dams[j-1]-mts[j-1]//2)*2
            if mts[j] < 0:
                break
        else:
            if mts[0]//2 + mts[N-1]//2 == dams[N-1]:
                mts = mts[N-smallest_idx:] + mts[:N-smallest_idx]
                print(*mts)
                return 0

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
import numpy as np

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N = int(input())
    dams = list(map(int, input().split()))
    S = sum(dams)
    res = [0]*N
    res[0] = S - 2*sum(dams[1:N:2])
    for i in range(1,N):
        res[i] = 2*dams[i-1]-res[i-1]
    print(*res)

if __name__ == '__main__':
    main()
N, M = list(map(int,input().split()))
A = []
B = []
for i in range(M):
    A1,B1=[int(i) for i in input().split()]
    A.append(A1)
    B.append(B1)
A.reverse()
B.reverse()

uf = UnionFind(N)
anses = []
ans = int(N * (N-1) / 2)
anses.append(ans)

for k in range(len(A)-1):
    if uf.is_same(A[k], B[k]):
        anses.append(anses[k])
        print(anses)
    else:
        N1 = uf.get_size(A[k])
        N2 = uf.get_size(B[k])
        ans = anses[k] - (N1 * N2)
        if ans < 0:
            ans = 0
        uf.union(A[k], B[k])
        anses.append(ans)
        
for ans in reversed(anses):
        print(ans)

### FIXED CODE ###

N, M = list(map(int,input().split()))
A = []
B = []
for i in range(M):
    A1,B1=[int(i) for i in input().split()]
    A.append(A1)
    B.append(B1)
A.reverse()
B.reverse()

class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n+1)]
        self.rank = [0 for _ in range(n+1)]
        self.size = [1 for _ in range(n+1)]
    
    def find(self, x):
        """
        x が属するグループを探索
        """
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        """
        x と y のグループを結合
        """
        x = self.find(x)
        y = self.find(y)
        if x != y:
            x_size = self.size[x]
            y_size = self.size[y]
            sum_size = x_size + y_size
            self.size[x] = sum_size
            self.size[y] = sum_size
            
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

    def is_same(self, x, y):
        """
        x と y が同じグループか否か
        """
        return self.find(x) == self.find(y)
    
    def get_size(self, a):
        x = self.find(a)
        return self.size[x]

uf = UnionFind(N)
anses = []
ans = int(N * (N-1) / 2)
anses.append(ans)

for k in range(len(A)-1):
    if uf.is_same(A[k], B[k]):
        anses.append(anses[k])
    else:
        N1 = uf.get_size(A[k])
        N2 = uf.get_size(B[k])
        ans = anses[k] - (N1 * N2)
        if ans < 0:
            ans = 0
        uf.union(A[k], B[k])
        anses.append(ans)
        
for ans in reversed(anses):
        print(ans)
n=int(input())
a_list=list(map(int,input().split()))
print(1/sum(1/a for a in range(a_list)))

### FIXED CODE ###

n=int(input())
a_list=list(map(int,input().split()))
print(1/sum(1/a for a in a_list))
ref=[63,6,91,79,102,109,125,39,127,111]
while 1:
	n=int(raw_input())
	if n==0:break
	e=0
	for i in range(n):
		a=ref[int(raw_input())]
		print "{:07b}".format(a^e)
		e=a

### FIXED CODE ###

ref=[63,6,91,79,102,109,125,39,127,111]
while 1:
	try:
		n=input()
		if n==-1:break
		e=0
		for i in range(n):
			a=ref[input()]
			print "{:07b}".format(a^e)
			e=a
	except:
		pass
N = input()
S = input()
K = input()

char = S[int(K)-1]

#print(char)

ans = []

for j in range(len(S)):
  #print(S[j])
  if char != S[j]:
    #print(S[j])
    S_t =S.replace(S[j], "*")
    #print(S_t)
    #print("!=") 
    S = S_t 
  else:
    #ans.append(char)
    continue

#print(" ".join(ans))
print(S_t)



### FIXED CODE ###

N = input()
S = input()
K = input()

char = S[int(K)-1]

#print(char)

ans = []

for j in range(len(S)):
  #print(S[j])
  if char != S[j]:
    ans.append("*")
    #print("!=")   
  else:
    ans.append(char)
    continue

print("".join(ans))
n,y = map(int,input().split())
s=[-1,-1,-1]
if n*10000<y:
    pass
elif n*10000==y:
    s=[n,0,0]
else:
    m=1
    x=n*10000
    while m<=n:
        for i in range(m+1):
            x= x-9000*(m-i)-4000*i
            if x == y:
                s=[n-m,i,m-i]
                break
        if x==y:
            break
    m=m+1
print(*l)

### FIXED CODE ###

n,y = map(int,input().split())
s=[-1,-1,-1]
if n*10000<y:
    pass
elif n*10000==y:
    s=[n,0,0]
else:
    m=1
    x_0=n*10000
    while m<=n:
        for i in range(m+1):
            x= x_0-9000*(m-i)-5000*i
            if x == y:
                s=[n-m,i,m-i]
                break
        if x==y:
            break
        m=m+1
print(*s)