Harryxun/stf_run huggingface dataset:
if N ==100000:
    ans=90909
elif N > 9999:  
    ans=N-9999 +909
elif N > 999:
    ans=909
elif N > 99:
    ans=N-99 +9
elif N > 9:
    ans= 9
else :
    ans=N
print(ans)   

### FIXED CODE ###

N = int(input())

if N ==100000:
    ans=90909
elif N > 9999:  
    ans=N-9999 +909
elif N > 999:
    ans=909
elif N > 99:
    ans=N-99 +9
elif N > 9:
    ans= 9
else :
    ans=N
print(ans)
N,M=list(map(int,input().split()))
H=list(map(int,input().split()))
A=[list(map(int,input().split())) for i in range(M)]

B=[0]*N
for i in A:
    if H[i[0]]>H[i[1]]:
        B[i[0]]=1
    if H[i[0]]<H[i[1]]:
        B[i[1]]=1
print(B.count(0))

### FIXED CODE ###

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

B=[0]*N
# from functools import lru_cache
# @lru_cache(maxsize=1000)
# def yapoos()
for i in A:
    if H[i[0]-1]>H[i[1]-1]:
        B[i[1]-1]=1
    elif H[i[0]-1]<H[i[1]-1]:
        B[i[0]-1]=1
    else:
        B[i[0]-1]=1
        B[i[1]-1]=1
print(B.count(0))
def clc(a, b, c, p, t):
    if c == 0:
        b = a[0]
        return clc(a, b, c + 1, True, t) + clc(a, b, c + 1, False, t)
    elif c == len(a)-1:
        if p:
            return t + int(b) + int(a[c])
        else:
            return t + int(b + a[c])
    else:
        if p:
            t += int(b)
            b = a[c]
        else:
            b += a[c]
        return clc(a, b, c + 1, True, t) + clc(a, b, c + 1, False, t)


s = input()
print(clc(s, "", 0, True, 0))


### FIXED CODE ###

def f(a, b, le, tf):
    b[le] = tf
    if le == len(b)-1:
        t = ""
        s1 = 0
        for i in range(len(b)):
            t += a[i]
            if b[i] == 1:
                s1 += int(t)
                t = ""
        t += a[len(b)]
        s1 += int(t)
        return s1
    else:
        return f(a, b, le+1, 0) + f(a, b, le+1, 1)


aa = input()
bb = [0] * (len(aa)-1)
if len(aa) == 1:
    print(aa)
else:
    print(f(aa, bb, 0, 0) + f(aa, bb, 0, 1))
from sys import exit
if __name__ == "__main__":
    n, m = map(int, input().split())
    jobs = []
    for i in range(n):
        job = tuple(map(int, input().split()))
        if job[0] <= m:
            jobs.append(job)
    jobs.sort(key=lambda tup: tup[1], reverse=True)
    income = 0
    daysUsed = -1
    if m == 1:
        print(jobs[0][1])
        exit()
        
    for job in jobs:
        daysLeft = (m - daysUsed) - job[0]
        if daysLeft > 0:
            income += job[1]
            daysUsed += 1
        else:
            income += job[1]
            break
    print(income)


### FIXED CODE ###

from sys import exit
from collections import deque
import heapq
if __name__ == "__main__":
    n, m = map(int, input().split())
    jobs = []
    for i in range(n):
        job = tuple(map(int, input().split()))
        if job[0] <= m:
            jobs.append(job)
    jobs.sort(key=lambda tup: tup[0])
    income = 0
    jobs = deque(jobs)
    hp = []
    for day in range(m):
        while len(jobs) != 0 and jobs[0][0] <= day + 1:
            job = jobs[0]
            heapq.heappush(hp, - job[1])
            jobs.popleft()
        if hp != []:
            income -= heapq.heappop(hp)
    
    print(income)
n, q = map(int, input().split())

to = [[] for i in range(n)]


for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)

score = [0]*n

for i in range(q):
    p, x = map(int, input().split())
    score[p-1] += x


def down_tree(index, parent=-1):
    global score
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)
    return


down_tree(0)

print(*score)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(200005)
n, q = map(int, input().split())

to = [[] for i in range(n+1)]


for i in range(n-1):
    a, b = map(int, input().split())
    to[a].append(b)
    to[b].append(a)

score = [0]*(n+1)
for i in range(q):
    p, x = map(int, input().split())
    score[p] += x


def down_tree(index, parent):
    for i in to[index]:
        if i == parent:
            continue
        score[i] += score[index]
        down_tree(i, index)



down_tree(1, 1)

print(' '.join(map(str, score[1:])))
n,m=map(int, input().split())
a=[]
for i in range(m):
  a.append(int(input()))

mod=1000000007

dp=[0]*(n+1)
dp[0]=1
dp[1]=1

a_i2=0
a_i1=0
a_i=0

for i in range(n-1):
  if i+2 == a[a_i2]:
      a_i2 += 1
      if a_i2 == m:
        a_i2 -= 1
  else:
    if i+1 == a[a_i1]:
      if i == a[a_i]:
        dp[i+2]=0
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i]
      a_i1 += 1
      if a_i1 == m:
        a_i1 -= 1
    else:
      if i == a[a_i]:
        dp[i+2]=dp[i+1]
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i+1]+dp[i]

  dp[i+2] = dp[i+2] % mod
  #print(dp)

print(dp[n])



### FIXED CODE ###

n,m=map(int, input().split())
a=[]
for i in range(m):
  a.append(int(input()))
  

mod=1000000007

dp=[0]*(n+1)
dp[0]=1


if n==1:
  print(1)
  exit()

if m==0:
  dp[1]=1
  for i in range(n-1):
    dp[i+2]=dp[i+1]+dp[i]
  dp[i+2] = dp[i+2] % mod
  print(dp[n])
  exit()

if a[0]==1:
  dp[1]=0
else:
  dp[1]=1



a_i2=0
a_i1=0
a_i=0

for i in range(n-1):
  if i+2 == a[a_i2]:
      a_i2 += 1
      if a_i2 == m:
        a_i2 -= 1
  else:
    if i+1 == a[a_i1]:
      if i == a[a_i]:
        dp[i+2]=0
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i]
      a_i1 += 1
      if a_i1 == m:
        a_i1 -= 1
    else:
      if i == a[a_i]:
        dp[i+2]=dp[i+1]
        a_i += 1
        if a_i == m:
          a_i -= 1
      else:
        dp[i+2]=dp[i+1]+dp[i]

  dp[i+2] = dp[i+2] % mod
  #print(dp)

print(dp[n])
from collections import deque
import sys
import functools
sys.setrecursionlimit(10000000000)
@functools.lru_cache(maxsize=None)
def stairs(n):
  if n==1:
    return 1
  if n==2:
    return 2
  return stairs(n-1)+stairs(n-2)
N,M=map(int,input().split())
A=deque()
for _ in range(M):
  A.append(int(input()))
pos=0
ans=0
while A:
  x=A.popleft()-1
  if len(A)!=0:
    if x+2==A[0]:
      print(0)
      exit()
  ans+=(stairs(x-pos)-1)
  ans%=1000000007
  pos=x+2
ans+=stairs(N-pos)
print(ans+1)

### FIXED CODE ###

N,M=map(int,input().split())
broken=[0]*N
for _ in range(M):
  a=int(input())
  broken[a]=1
dp=[0]*(N+2)
dp[N]=1
for i in range(N-1,-1,-1):
  if broken[i]==1:
    dp[i]=0
  else:
    dp[i]=(dp[i+1]+dp[i+2])%1000000007
print(dp[0])
n = int(input())
s = list(input())

if n % 2 == 1:
    print('No')
    exit()

print('Yes') if s[:n/2] == s[n/2:] else print('No')

### FIXED CODE ###

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

if n % 2 == 1:
    print('No')
    exit()

l = int(n/2)
print('Yes') if s[:l] == s[l:] else print('No')
n, q = map(int, input().split())
l = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    l[a - 1].append(b - 1)
    l[b - 1].append(a - 1)
r = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    r[p - 1] += x
def dfs(v, p = -1):
    for to in l[v]:
        if to == p:
            continue
        r[to] += r[v]
        dfs(to, v)
dfs(0)
for t_r in r:
    print(t_r)

### FIXED CODE ###

n, q = map(int, input().split())
l = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    l[a - 1].append(b - 1)
    l[b - 1].append(a - 1)
r = [0] * n
for i in range(q):
    p, x = map(int, input().split())
    r[p - 1] += x
stack = [0]
used = [False] * n    
while stack:
    i = stack.pop()
    used[i] = True
    for to in l[i]:
        if not used[to]:
            stack.append(to)
            r[to] += r[i]
for t_r in r:
    print(t_r)
N,K,Q = map(int, input().split())

A = [K for _ in range(N)]

for _ in range(N):
    A[int(input())-1] += 1
for i in range(N):
    print("Yes" if A[i] > Q else "No")


### FIXED CODE ###

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

A = [K for _ in range(N)]

for _ in range(Q):
    A[int(input())-1] += 1
for i in range(N):
    print("Yes" if A[i] > Q else "No")
N, K = map(int, input().split())
l = []
for i in range(N):
    l.append(int(input()))

l.sort(reverse=True)

print(sum(l[:K]))

### FIXED CODE ###

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

l.sort(reverse=True)

print(sum(l[:K]))
import sys
sys.setrecursionlimit(100000)
N,M=map(int,input().split())
S=list(input())
T=list(input())

def gcd(x,y):
  if x==0:
    return y
  else:
    return gcd(y%x,x)

k=N*M//gcd(N,M)
X=[0]*k
for i,s in enumerate(S):
  X[i*k//N]=s
  
for i,t in enumerate(T):
  if X[i*k//M]==t or X[i*k//M]==0:
    pass
  else:
    print(-1)
    exit()
    
print(k)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10000)
N,M=map(int,input().split())
S=list(input())
T=list(input())

def gcd(x,y):
  if x==0:
    return y
  else:
    return gcd(y%x,x)

k=N*M//gcd(N,M)
X=[0]*N
for i,s in enumerate(S):
  X[i]=s
  
for i,t in enumerate(T):
  if (i*k//M)%(k//N)!=0:
    pass
  elif (i*k//M)%(k//N)==0 and X[(i*k//M)//(k//N)]==t:
    pass
  else:
    print(-1)
    exit()
    
print(k)
S = input()


for i in range(2**3):
    formula = ""

    for j in range(4):
        formula += S[j]
        if (i >> j) & 1:
            formula += "+"
        else:
            formula += "-"

    if eval(formula) == 7:
        print(formula + "=7")
        break

### FIXED CODE ###

S = input()


for i in range(2**3):
    formula = ""

    for j in range(3):
        formula += S[j]
        if (i >> j) & 1:
            formula += "+"
        else:
            formula += "-"
    formula += S[-1]

    if eval(formula) == 7:
        print(formula + "=7")
        break
A, B, C, K = input().split()
# A=1 B=0 C=-1 K
ans = 0

for a in range(int(K)):
    if int(A) == int(K):
        ans = A
        break
    elif int(A) <= int(K):
        ans = A

    elif int(B) <= int(K):
        ans = A

    elif int(C) <= int(K):
        ans = (-1 * C)
        break
if int(A) == int(K):
    print(K)
else:
    print(int(A) + int(B) - int(C))

### FIXED CODE ###

S = input()
T = input()

if S == T[0:-1] and len(S) + 1 == len(T):
    print("Yes")
else:
    print("No")
n,m=map(int,input().split())
a=[int(i) for i in input().split()]
count=0
 
A=sum(a)//(4*m)
for i in a:
  if a[i]>=A:
    count+=1
if count>=m:
  print("Yes")
else:
  print("No")

### FIXED CODE ###

n,m=map(int,input().split())
a=[int(i) for i in input().split()]
count=0
 
A=sum(a)/(4*m)
for i in a:
  if i>=A:
    count+=1
if count>=m:
  print("Yes")
else:
  print("No")
n,k = map(int, input().split())
ans = [0,1][n%k]
print(ans)

### FIXED CODE ###

n,k = map(int, input().split())
ans = 1 if n%k else 0
print(ans)
k = int(input())

if k = 1:
    print("ACL")
if k = 2:
    print("ACLACL")
if k = 3:
    print("ACLACLACL")
if k = 4:
    print("ACLACLACLACL")
if k = 5:
    print("ACLACLACLACLACL")

### FIXED CODE ###

k = int(input())

if k == 1:
    print("ACL")
if k == 2:
    print("ACLACL")
if k == 3:
    print("ACLACLACL")
if k == 4:
    print("ACLACLACLACL")
if k == 5:
    print("ACLACLACLACLACL")
S = input()
days = ["SUN","MON","TUE","WED","THU","FRI","SAT"]

for i in days:
    if S == days[i]:
        t = i
        break
    else:
        i =+ 1

print(days[t + 1])

### FIXED CODE ###

from sys import stdin

S = stdin.readline().rstrip()
days  = ["MON","TUE","WED","THU","FRI","SAT","SUN"]

if S == "SUN":
    print(7)
else:
    i = days.index(S)
    print(6 - i)
n = int(input())
nums = [int(i) for i in input().split()]
ans = 0

while True:
  if [i for i in nums if i % 2 == 1]
  	break
  nums = [i//2 for i in nums]
  ans += 1 
  
print(ans)

### FIXED CODE ###

n = int(input())
nums = [int(i) for i in input().split()]
ans = 0
while True:
    if [i for i in nums if i % 2 == 1]:
        break
    nums = [i//2 for i in nums]
    ans += 1
print(ans)
s = input()
k = int(input())
n = len(s)
s1 = s[0]
cnt1 = 0
s2 = s[0]
cnt2 = 0
for i in range(1,n):
    if i%2 == 1:
        s1 += s[i]
        continue
    elif s[i-1] == s[i] or s[i] == s[i + 1]:
        s1 += '0'
        cnt1 += 1
    else:
        s1 += s[i]

for i in range(1,n):
    if i%2 == 0:
        s2 += s[i]
        continue
    elif s[i-1] == s[i] or (i < n-1 and s[i] == s[i + 1]):
        s2 += '0'
        cnt2 += 1
    else:
        s2 += s[i]
s1 += s1
s2 += s2
jdg = [True,True]
for i in range(1,2*n):
    if s1[i] == s1[i-1]:
        jdg[0] = False
    if s2[i] == s2[i-1]:
        jdg[1] = False
if jdg[0] and jdg[1]:
    print(min(cnt1,cnt2)*k)
elif jdg[0]:
    print(cnt1*k)
else:
    print(cnt2*k)

### FIXED CODE ###

s = input()
k = int(input())
n = len(s)
if len(set(s)) == 1:
    print((n*k)//2)
else:
    arr = []
    cnt = 0
    last = s[0]
    for i in s + '0':
        if i != last:
            arr.append(cnt)
            cnt = 1
            last = i
        else:
            cnt += 1
    ans = 0
    if s[0] == s[-1]:
        ans += (arr[0] + arr[-1])//2*(k-1) + arr[0]//2 + arr[-1]//2
        for i in arr[1:-1]:
            ans += (i//2)*k
    else:
        for i in arr:
            ans += (i//2)*k
    print(ans)
A, B, N = list(map(int,input().split()))
MAX = float('inf')*(-1)
a = int(A/B)
b = B
if N < B:
    MAX = (A * N // B) - A * (N // B)
else:
    MAX = (A * (B-1) // B) - A * ((B-1) // B)
print(MAX)

### FIXED CODE ###

K = int(input())
A,B = list(map(int,input().split()))
a = A // K
b = B // K
flag = 0
for i in range(a,b+1):
    if A <= K * i and K * i <= B:
        flag += 1
if flag != 0:
    print('OK')
else:
    print('NG')
a, b, c=map(int, input().split(/))
if a>=2020:
  print("TBD")
elif a==2019 and b>=5:
  print("TBD")
else:
  print("Heisei")

### FIXED CODE ###

a, b, c=map(int, input().split("/"))
if a>=2020:
  print("TBD")
elif a==2019 and b>=5:
  print("TBD")
else:
  print("Heisei")
# import numpy as np

bingo = np.zeros((3,3))
bin_bingo = np.zeros((3,3))


for i in range(3):
    bingo[i] = list(map(int, input().split()))

N = int(input())

for _ in range(N):
    num = int(input())
    bin_bingo = np.logical_or(bin_bingo, bingo == num)

# find bingo
lin1 = np.array([[True, True, True], [False, False, False], [False, False, False]])
lin2 = np.array([[False, False, False],[True, True, True], [False, False, False]])
lin3 = np.array([[False, False, False], [False, False, False], [True, True, True]])
col1 = lin1.T
col2 = lin2.T
col3 = lin3.T

sla1 = np.array([[True, False, False], [False, True, False], [False, False, True]])
sla2 = np.array([[False, False, True], [False, True, False], [True, False, False]])

def is_bingo(src, tmp):
    return (np.logical_and(bin_bingo, sla1) == sla1).all()

flg = False
if is_bingo(bin_bingo, lin1):
    flg = True
elif is_bingo(bin_bingo, lin2):
    flg = True
    
elif is_bingo(bin_bingo, lin3):
    flg = True

elif is_bingo(bin_bingo, col1):
    flg = True
elif is_bingo(bin_bingo, col2):
    flg = True
elif is_bingo(bin_bingo, col3):
    flg = True
elif is_bingo(bin_bingo, sla1):
    flg = True
elif is_bingo(bin_bingo, sla2):
    flg = True

if flg:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

import numpy as np

bingo = np.zeros((3,3))
bin_bingo = np.zeros((3,3))

for i in range(3):
    bingo[i] = list(map(int, input().split()))



N = int(input())

for _ in range(N):
    num = int(input())
    bin_bingo = np.logical_or(bin_bingo, bingo == num)

# find bingo
lin1 = np.array([[True, True, True], [False, False, False], [False, False, False]])
lin2 = np.array([[False, False, False],[True, True, True], [False, False, False]])
lin3 = np.array([[False, False, False], [False, False, False], [True, True, True]])
col1 = lin1.T
col2 = lin2.T
col3 = lin3.T

sla1 = np.array([[True, False, False], [False, True, False], [False, False, True]])
sla2 = np.array([[False, False, True], [False, True, False], [True, False, False]])

def is_bingo(src, tmp):
    return (np.logical_and(src, tmp) == tmp).all()

flg = False
if is_bingo(bin_bingo, lin1):
    flg = True
elif is_bingo(bin_bingo, lin2):
    flg = True
elif is_bingo(bin_bingo, lin3):
    flg = True
elif is_bingo(bin_bingo, col1):
    flg = True
elif is_bingo(bin_bingo, col2):
    flg = True
elif is_bingo(bin_bingo, col3):
    flg = True
elif is_bingo(bin_bingo, sla1):
    flg = True
elif is_bingo(bin_bingo, sla2):
    flg = True

if flg:
    print('Yes')
else:
    print('No')
N = int(input())
S = int(input())

if N == S:
    print(N + 1)
    exit()

if S == 1:
    print(N)
    exit()

if S > N:
    print(-1)
    exit()

def f(b, n):
    if n < b:
        return n
    return f(b, n // b) + n % b

ans = float('inf')

for b in range(2, int(N**0.5) + 10):
    if f(b, N) == S:
        ans = min(ans, b)

    q = S - b
    b = (N - q) // b
    if f(b, N) == S:
        ans = min(ans, b)

if ans == float('inf'):
    print(-1)
else:
    print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(10 ** 7)

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

if N == S:
    print(N + 1)
    exit()

def f(b, n):
    if n < b:
        return n
    return f(b, n // b) + n % b

ans = float('inf')

for b in range(1, int(N**0.5) + 100):
    if b > 1 and f(b, N) == S:
        ans = min(ans, b)

    q = S - b
    b = (N - q) // b
    if b > 1 and f(b, N) == S:
        ans = min(ans, b)

if ans == float('inf'):
    print(-1)
else:
    print(ans)
X, K, D = map(int, input().split())

ans_list = []

if X+K*D <= 0:
    ans = abs(X+K*D)
else:
    if D>0:
        a = int((X+K*D)/(2*D))
            ans = abs(X+(K-(a+i))*D - (a+i)*D)
print(ans)

### FIXED CODE ###

X, K, D = map(int, input().split())
ans_list = []

if X+K*D <= 0:
    ans = abs(X+K*D)
else:
    a = (X+K*D)//(2*D)
    if a >= K:
        a = K
        ans = abs(X-K*D)
    else:
        ans_1 = abs(X+K*D-2*a*D)
        ans_2 = abs(X+K*D-2*(a+1)*D)
        ans = min(ans_1, ans_2)
print(ans)
N = int(input())
raw = list(map(int, input().split()))

cnt = 0

for i in raw:
    cnt = 0
    while i % 2 == 0:
        i //= 2
        cnt += 1
print(cnt)

### FIXED CODE ###

a = input()
num = [int(i) for i in a]
print(sum(num))
import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    # gori~~~
    if time.time() - start_time > 1.8:
        break
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')

### FIXED CODE ###

import sys,time
sys.setrecursionlimit(10**7)

start_time = time.time()
N,M = map(int,input().split())
S = input()
src = [tuple(map(lambda x:int(x)-1,sys.stdin.readline().split())) for i in range(M)]

outdeg = [set() for i in range(2*N)]
for x,y in src:
    if S[x] == S[y]:
        #A0->A1, B0->B1
        outdeg[x].add(y+N)
        outdeg[y].add(x+N)
    else:
        #A1->B0, B1->A0
        outdeg[x+N].add(y)
        outdeg[y+N].add(x)

mem = [0] * (2*N)
def visit(v):
    if time.time() - start_time > 1.8:
        # gori~~~
        print('No')
        exit()
    if mem[v] == 1:
        print('Yes')
        exit()
    if mem[v] == 0:
        mem[v] = 1
        for to in outdeg[v]:
            visit(to)
        mem[v] = 2

for i in range(2*N):
    visit(i)

print('No')
import numpy as np
import itertools

N, A, B = list(map(int, input().split()))
V = np.array(list(map(int, input().split())))
V.sort()
V[:] = V[::-1]

def nCr(n, r):
    return(len(list(itertools.combinations(np.arange(n), p))))

d = V[A-1]
# unless all equal, we only need A
if d == V.max():
    # count how many d
    d_eq_cnt = np.count_nonzero(V == d)
    res = nCr(d_eq_cnt, A)
    res_sum = res
    for k in range(1, min(B, d_eq_cnt) + 1 - A):
        res = res * (d_eq_cnt - (A+k-1)) // (A+k)
        res_sum += res
    print(V[:A].mean())
    print(res_sum)
    
    
else:
    # count how many d
    d_eq_cnt = np.count_nonzero(V == d)
    d_lq_cnt = np.count_nonzero(V > d)
    print(V[:A].mean())
    print(nCr(d_eq_cnt, A - d_lq_cnt))



### FIXED CODE ###

import numpy as np

N, A, B = list(map(int, input().split()))
V = np.array(list(map(int, input().split())))
V.sort()
V[:] = V[::-1]

def fac(n):
    return 1 if n<=1 else n*fac(n-1)
        
def nCr(n, r):
    return fac(n) // fac(n-r) // fac(r)

d = V[A-1]
# unless all equal, we only need A
if d == V.max():
    # count how many d
    d_eq_cnt = np.count_nonzero(V == d)
    res = nCr(d_eq_cnt, A)
    res_sum = res
    for k in range(1, min(B, d_eq_cnt) + 1 - A):
        res = res * (d_eq_cnt - (A+k-1)) // (A+k)
        res_sum += res
    print(V[:A].mean())
    print(res_sum)
    
    
else:
    # count how many d
    d_eq_cnt = np.count_nonzero(V == d)
    d_lq_cnt = np.count_nonzero(V > d)
    print(V[:A].mean())
    print(nCr(d_eq_cnt, A - d_lq_cnt))
A,B,C,D = list(map(int,input().split()))

if B <= C and D <= A:
    print(0)
else :
    ans_tmp1 = abs(B - C)
    ans_tmp2 = abs(D - C)
    if ans_tmp1 >= ans_tmp2:
        print(ans_tmp2)
    else:
        print(ans_tmp1))

### FIXED CODE ###

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

if B - C > 0 and D - A > 0:
    start = max(A,C)
    stop = min(B,D)
    print(stop - start)
else:
    print(0)
from functools import reduce
def gcd(a, b):
  if (b == 0):
    return a;

  return gcd(b, a % b)


def lcm(a, b):
  return a * b / gcd(a, b);

n = int(input())
li = []
for i in range(n):
  li.append(int(input()))

ans = int(reduce((lambda x, y: lcm(x, y)), li))

print(ans)

### FIXED CODE ###

from functools import reduce

# def gcd(a, b):
#   if (b == 0):
#     return a
#   return gcd(b, a % b)

# def lcm(a, b):
#   return a * b / gcd(a, b)

def lcm(a, b): 
    def gcd(a, b):  # a >= b
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    return a * b // gcd(a, b)

def main():
  n = int(input())
  li = []
  for i in range(n):
    inp = int(input())
    li.append(inp)

  ans = int(reduce((lambda x, y: lcm(x, y)), li))
  if ans > 1000000000000000000:
    ans = 1000000000000000000
  print(ans)

if __name__ == "__main__":
  main()
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

for i in range(N-1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    n_list[a].append([b,i])
    n_list[b].append([a,i])
    d[a] += 1
    d[b] += 1


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

    
try:
    paint(tmp[0][0], -1)
except RecursionError:
    print(0)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])

### FIXED CODE ###

import sys
N = int(input().strip())

n_list = [[] for i in range(N)]
d = [0] * N

for i in range(N-1):
    a, b = map(int, input().strip().split())
    a -= 1
    b -= 1
    n_list[a].append([b,i])
    n_list[b].append([a,i])
    d[a] += 1
    d[b] += 1


#print(n_list)
#print(d)

d_dict = {}
for i in range(N):
    d_dict[i] = d[i]
tmp = sorted(d_dict.items(), key = lambda x:x[1], reverse = True)

colors = [0] * (N)

root = tmp[0][0]

def paint(node, parent_edge_id):
    #print(node, parent_edge_id)
    tmp_color = 1
    for edge in n_list[node]:
        #print("ege:", edge)
        if edge[1] != parent_edge_id:
            if parent_edge_id != -1 and tmp_color == colors[parent_edge_id]:
                tmp_color += 1
            colors[edge[1]] = tmp_color
            paint(edge[0], edge[1])
            tmp_color += 1

    
sys.setrecursionlimit(10**7)
paint(tmp[0][0], -1)
print(tmp[0][1]) # color num 
for i in range(N-1):
    print(colors[i])