Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def com(n,m):
    if(n-m < m):
        m=n-m
    result=1
    mylist=[i for i in range(1,m+1)]
    j=1
    for i in range(1,m+1):
        result*=(n+1-i)
        if(j<m):
            while(result%mylist[j]==0):
                result//=mylist[j]
                j+=1
                if(j>=m):
                    break
    return result

def yakusuu(i,m):
    _i=i
    while(i*2<=m):
        if(m%i==0):
            return i
        else:
            i+=1
    for j in range(_i-1,0,-1):
        if(m%j==0):
            break
    return m//j
    

N,M=map(int,input().split())
soinsuubunkai={}
tmp=2
i=2
_M=M
while(tmp <=M):
    tmp=yakusuu(tmp,M)

    if(tmp in soinsuubunkai):
        soinsuubunkai[tmp]+=1
    else:
        soinsuubunkai[tmp]=1
    M//=tmp
    if(M==1):
        break


tmp=1
for k in list(soinsuubunkai.values()):
    tmp*=com(k+N-1,k)
    tmp%=10**9+7
print(tmp)

### FIXED CODE ###

def com(n,m):
    if(n-m < m):
        m=n-m
    result=1
    mylist=[i for i in range(1,m+1)]
    j=1
    for i in range(1,m+1):
        result*=(n+1-i)
        if(j<m):
            while(result%mylist[j]==0):
                result//=mylist[j]
                j+=1
                if(j>=m):
                    break
    return result

def yakusuu(i,m):
    _i=i
    while(i**2<=m):
        if(m%i==0):
            return i
        else:
            i+=1
    for j in range(_i-1,0,-1):
        if(m%j==0):
            break
    return m//j
    

N,M=map(int,input().split())
soinsuubunkai={}
tmp=2
i=2
_M=M
while(tmp <=M):
    tmp=yakusuu(tmp,M)

    if(tmp in soinsuubunkai):
        soinsuubunkai[tmp]+=1
    else:
        soinsuubunkai[tmp]=1
    M//=tmp
    if(M==1):
        break


tmp=1
for k in list(soinsuubunkai.values()):
    tmp*=com(k+N-1,k)
    tmp%=10**9+7
print(tmp)
### BUGGY CODE ###

import sys
import math

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def gcd(a, b):
    if b == 0:
        return a
    if a == 0:
        return b
    elif a > b:
        return gcd(b, a % b)
    else:
        return gcd(a, b % a)


def gcd_m(*args):
    if len(args) == 0:
        return 0
    if len(args) == 1:
        return args[0]
    if len(args) >= 2:
        ret = gcd(args[0], args[1])

    for value in args[2:]:
        ret = gcd(ret, value)
    return ret


def solve(inputs):
    [N] = string_to_int(inputs[0])
    A = [0] + (string_to_int(inputs[1])) + [0]
    # A = string_to_int(inputs[1])

    if N == 2:
        return max(A)

    left_gcd_memo = [0]

    max_num = 0
    for i in range(1, len(A)):
        right = A[i+1:]

        left_gcd = gcd_m(left_gcd_memo[-1], A[i-1])
        left_gcd_memo.append(left_gcd)
        right_gcd = gcd_m(*right)

        g = gcd(left_gcd, right_gcd)
        if g > max_num:
            max_num = g

    return max_num


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(2))
    print(ret)

### FIXED CODE ###

import sys
import math
from collections import deque

sys.setrecursionlimit(4100000)


def inputs(num_of_input):
    ins = [input() for i in range(num_of_input)]
    return ins


def gcd(a, b):
    if b == 0:
        return a
    if a == 0:
        return b
    elif a > b:
        return gcd(b, a % b)
    else:
        return gcd(a, b % a)


def gcd_m(*args):
    if len(args) == 0:
        return 0
    if len(args) == 1:
        return args[0]
    if len(args) >= 2:
        ret = gcd(args[0], args[1])

    for value in args[2:]:
        ret = gcd(ret, value)
    return ret


def solve(inputs):
    [N] = string_to_int(inputs[0])
    # A = [0] + (string_to_int(inputs[1])) + [0]
    A = string_to_int(inputs[1])

    if N == 2:
        return max(A)

    left_gcd_memo = deque([0])
    right_gcd_memo = deque([0])

    for v in A:
        left_gcd_memo.append(gcd(left_gcd_memo[-1], v))
    left_gcd_memo.append(0)
    for v in reversed(A):
        right_gcd_memo.appendleft(gcd(right_gcd_memo[0], v))
    right_gcd_memo.appendleft(0)

    max_gcd = 0
    for i in range(0, len(A)):
        left = left_gcd_memo[i]
        right = right_gcd_memo[i+2]
        g = gcd(left_gcd_memo[i], right_gcd_memo[i+2])
        max_gcd = g if g > max_gcd else max_gcd

    return max_gcd


def string_to_int(string):
    return list(map(lambda x: int(x), string.split()))


if __name__ == "__main__":
    ret = solve(inputs(2))
    print(ret)
### BUGGY CODE ###

N = int(input())
funcionarios = list(map(int,input().split()))
for x in range(1,N+1):
    print(funcionarios.count(x))


### FIXED CODE ###

N = int(input())
funcionarios = list(map(int,input().split()))
frequencia = [0 for i in range(N)]

for i in funcionarios:
    frequencia[i-1] += 1

for i in frequencia:
    print(i)
### BUGGY CODE ###

N = int(input())
A = list(input().split())
B = [int(a) for a in A]
x = 10**9+7
summation = sum((B[i] * (sum(B[j] for j in range(i+1,N)) % x)) % x for i in range(N-1)) % x
print(summation)

### FIXED CODE ###

N = int(input())
A = list(input().split())
B = [int(a) for a in A]
x = 10**9+7
summation1 = sum(B) ** 2
summation2 = sum(b ** 2 for b in B)
summation = ((summation1 - summation2) // 2) % x
print(summation)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(20000*20000)

S = str(input())
ans = set()

def dfs(i, j):
    if int(S[i:j+1])%2019 == 0:
        ans.add((i, j))
    if j == len(S)-1:
        return

    dfs(i, j+1)
    dfs(i+1, j+1)

if len(S) < 4:
    print(0)

else:
    dfs(0, 3)
    print(len(ans))

### FIXED CODE ###

s=input()
n=len(s)
mod=2019
d=0
p=1
ml=[0]*mod
for i in range(1,n+1):
  k=int(s[-i])
  d+=p*k
  d%=mod
  ml[d]+=1
  p*=10
  p%=mod
ans=0
for i in ml:
  ans+=i*(i-1)//2
print(ans+ml[0])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)

n,m,k=map(int,input().split())
fr=[0 for _ in range(n)]
frl=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    fr[a-1]=fr[a-1]+1
    fr[b-1]=fr[b-1]+1
    frl[a-1].append(b)
    frl[b-1].append(a)

treelist=[]
hitobito=set()

def saiki(c):
    global treelist
    global hitobito
    global frl
    global bll
    global tmpset

    if frl[c-1] == []:
        hitobito.add(c)
        tmpset.add(c)
    
    for tsugi in frl[c-1]:
        if not tsugi in hitobito:
            hitobito.add(tsugi)
            tmpset.add(tsugi)
            saiki(tsugi)

for i in range(n):
    tmpset=set()
    saiki(i+1)
    if not tmpset == set():
        treelist.append(tmpset)


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

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


output=[]
for i in range(n):
    for tree in treelist:
        if i+1 in tree:
            tmpsum=0
            for aaa in frl[i]:
                if aaa in tree:
                    tmpsum+=1
            for bbb in bll[i]:
                if bbb in tree:
                    tmpsum+=1 
            output.extend([str(len(tree)-tmpsum-1)," "])

print("".join(output))    




### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

n,m,k=map(int,input().split())
fr=[0 for _ in range(n)]
frl=[[] for i in range(n)]
frlist=[]
for i in range(m):
    a,b=map(int,input().split())
    frl[a-1].append(b)
    frl[b-1].append(a)
    frlist.append([a,b])

treelist=[]
hitobito=set()

def saiki(c,tmpi):
    global hitobito
    global tmpset
    global trbl
    
    if frl[c-1] == []:
        hitobito.add(c)
        tmpset.add(c)
        trbl[c-1]=tmpi
    
    for tsugi in frl[c-1]:
        if not tsugi in hitobito:
            hitobito.add(tsugi)
            tmpset.add(tsugi)
            trbl[tsugi-1]=tmpi
            saiki(tsugi,tmpi)

index=0
trbl=[None for _ in range(n)]
for i in range(n):
    tmpset=set()
    saiki(i+1,index)
    if not tmpset == set():
        treelist.append(tmpset)
        index+=1

bl=[0 for _ in range(n)]
bll=[[] for i in range(n)]
bllist=[]
for i in range(k):
    a,b=map(int,input().split())
    bll[a-1].append(b)
    bll[b-1].append(a)
    bllist.append([a,b])

for fre in frlist:
    if trbl[fre[0]-1] == trbl[fre[1]-1]:
        fr[fre[0]-1]=fr[fre[0]-1]+1
        fr[fre[1]-1]=fr[fre[1]-1]+1

for blo in bllist:
    if trbl[blo[0]-1] == trbl[blo[1]-1]:
        bl[blo[0]-1]=bl[blo[0]-1]+1
        bl[blo[1]-1]=bl[blo[1]-1]+1

output=[]
for i in range(n):
    tmpsum=fr[i]+bl[i]
    output.extend([str(len(treelist[trbl[i]])-tmpsum-1)," "])

print("".join(output))
### BUGGY CODE ###

from fractions import gcd
from functools import reduce
import sys
input = sys.stdin.readline

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


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

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


n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
ans=0
m=int(10**9+7)
g=1
l=1
'''
for x in a:
  if l%x!=0:
    g=gcd(l,x)
    l=l*x//g
'''
l=lcm(*a)

for x in a:
  ans+=(l//x)%m

print(ans%m)

### FIXED CODE ###

from fractions import gcd
from functools import reduce
import sys
input = sys.stdin.readline

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


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

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


n=int(input())
a=list(map(int,input().split()))
a.sort(reverse=1)
ans=0
m=int(10**9+7)
g=1
l=1
'''
for x in a:
  if l%x!=0:
    g=gcd(l,x)
    l=l*x//g
'''
l=lcm(*a)

for x in a:
  ans+=l//x

print(ans%m)
### BUGGY CODE ###

def solve():
  n,p = (int(i) for i in input().split())
  upper = round(p**(1/n))
  for i in range(upper+1,0,-1):
    if p%(i**n) == 0:
      print(i)
      break
  
solve()

### FIXED CODE ###

from collections import Counter
import sys
sys.setrecursionlimit(1000000)

def solve():
  n,p = (int(i) for i in input().split())
  ans = 1
  if n == 1:
    print(p)
    exit()
  p_dummy = p
  for i in range(2,int(p_dummy**0.5)+4):
    ct = 0
    while p_dummy%i == 0:
      ct += 1
      p_dummy //= i
      if ct >= n:
        ans *= i
        ct -= n
  

  print(ans)
  
solve()
### BUGGY CODE ###

from collections import deque
from collections import defaultdict

N, Q = list(map(int, input().split()))
T = defaultdict(list)
for _ in range(N-1):
    a, b = list(map(int, input().split()))
    T[a].append(b)

P = defaultdict(int)
for _ in range(Q):
    p, x = list(map(int, input().split()))
    P[p] += x

q = deque()
ans = [0] * (N+1)
ans[1] = P[1]

for t in T[1]:
    q.append([1, t])
while q:
    a, b = q.popleft()
    ans[b] += ans[a] + P[b]
    for t in T[b]:
        q.append([b, t])

print(*ans[1:])


### FIXED CODE ###

from collections import deque
from collections import defaultdict
import sys
readline = sys.stdin.readline

N, Q = list(map(int, readline().split()))
T = defaultdict(list)
for _ in range(N-1):
    a, b = list(map(int, readline().split()))
    T[a].append(b)

P = defaultdict(int)
for _ in range(Q):
    p, x = list(map(int, readline().split()))
    P[p] += x

q = deque()
ans = [0] * (N+1)
ans[1] = P[1]

for t in T[1]:
    q.append([1, t])
while q:
    a, b = q.popleft()
    ans[b] += ans[a] + P[b]
    for c in T[b]:
        q.append([b, c])

print(*ans[1:])
### BUGGY CODE ###

N = int(input())
edge_idx = {}
edge_color = {i: None for i in range(N-1)}
E = {v: [] for v in range(1, N+1)}
for i in range(N-1):
    a, b = map(int, input().split())
    edge_idx[(a, b)] = i
    E[a].append(b)
    E[b].append(a)
degs = {v: 0 for v in range(1, N+1)}
for v in range(1, N + 1):
    E[v].sort()
    degs[v] = len(E[v])
K = max(degs.values())
print(K)
for v in range(1, N):
    available = {c: True for c in range(1, K+1)}
    c = 1
    for u in E[v]:
        if v > u:
            e_idx = edge_idx[(u, v)]
            available[edge_color[e_idx]] = False
            continue
        e_idx = edge_idx[(v, u)]
        while not available[c]: c = (c + 1) % K if c + 1 != K else K
        edge_color[e_idx] = c
        c += 1
for i in range(N-1):
    print(edge_color[i])

### FIXED CODE ###

from collections import deque

N = int(input())
edge_idx = {}
edge_color = {i: None for i in range(N-1)}
E = {v: [] for v in range(1, N+1)}
for i in range(N-1):
    a, b = map(int, input().split())
    edge_idx[(a, b)] = i
    E[a].append(b)
    E[b].append(a)
degs = {v: 0 for v in range(1, N+1)}
for v in range(1, N + 1):
    degs[v] = len(E[v])
K = max(degs.values())
print(K)
q = deque([(-1, 1)])
visited = {i: False for i in range(1, N+1)}
while q:
    p, v = q.popleft()
    visited[v] = True
    if p == -1:
        used = -1
    else:
        used = edge_color[edge_idx[(p, v)]] if p < v else edge_color[edge_idx[(v, p)]]
    c = 1
    for u in E[v]:
        if visited[u]: continue
        q.append((v, u))
        if c == used: c += 1
        if u < v:
            edge_color[edge_idx[(u, v)]] = c
        else:
            edge_color[edge_idx[(v, u)]] = c
        c += 1
for i in range(N-1):
    print(edge_color[i])
### BUGGY CODE ###

N=int(input())
# a=int(input())
# a,b=map(int,input().split(" "))
A=[int(_) for _ in input().split(" ")]

if A[0] == 0:
    ans=0
    print(ans)
    exit()
else:
    ans=A[0]

for i in range(1,N):
    if A[i] == 0:
        ans=0
        break
    ans *= A[i]

if ans > 10**18:
    ans = -1
print(ans)


### FIXED CODE ###

N=int(input())
# a=int(input())
# a,b=map(int,input().split(" "))
A=[int(_) for _ in input().split(" ")]

if A[0] == 0:
    ans=0
    print(ans)
    exit()
else:
    ans=A[0]

for i in range(1,N):
    if A[i] == 0:
        ans=0
        break
    elif ans < 0:
        ans = -1
    elif A[i] == 10**18:
        ans = -1
    else:
        ans *= A[i]
        if ans > 10**18:
            ans = -1

print(ans)
### BUGGY CODE ###

n, m = list(map(int, input().split(' ')))

bads = []
for i in range(m):
    bads.append(int(input()))

dp = [1, 1]
for i in range(2, n+1):
    dp.append(0)
    if i-1 not in bads:
        dp[i] += dp[i-1]
    if i-2 not in bads:
        dp[i] += dp[i-2]
    dp[i] %= 1000000007

print(dp[-1])


### FIXED CODE ###

n, m = list(map(int, input().split(' ')))

bads = {}
for i in range(m):
    bads[int(input())] = None

dp = [1]
if 1 not in bads:
    dp.append(1)
else:
    dp.append(0)
for i in range(2, n+1):
    dp.append(0)
    if i-1 not in bads:
        dp[i] += dp[i-1]
    if i-2 not in bads:
        dp[i] += dp[i-2]
    dp[i] %= 1000000007

print(dp[-1])
### BUGGY CODE ###

L, R = map(int, input().split())
saidai = float("inf")
for i in range(L, R):
    for j in range(L+1, R+1):
        saidai = min(saidai, i*j%2019)
print(saidai)

### FIXED CODE ###

L, R = map(int, input().split())
if R-L >= 2019:
    print(0)
else:
    saidai = float("inf")
    for i in range(L, R):
        for j in range(L+1, R+1):
            saidai = min(saidai, i*j%2019)
    print(saidai)
### BUGGY CODE ###

import fractions

n = int(input())
As = list(map(int, input().split(" ")))
maxa = max(As)
largest = 1

for i in range(n):
  gcd = 0
  for idx, j in enumerate(As):
    if idx == i:
      continue
    gcd = j if gcd==0 else fractions.gcd(gcd, j)
    if gcd <= largest:
      break
  if gcd > largest:
    largest = gcd
    if largest == maxa:
      break

print(largest)



### FIXED CODE ###

def gcd(a, b):
  l = max(a, b)
  s = min(a, b)
  if s == 0:
    return l
  else:
    return gcd(s, l%s)

n = int(input())
A = [0] + list(map(int, input().split())) + [0]
largest = 0
L = [0 for _ in range(n+2)]
R = [0 for _ in range(n+2)]
for i in range(1, n+2):
  L[i] = gcd(A[i], L[i-1])
  R[n-i+1] = gcd(R[n-i+2], A[n-i+1])

print(max(gcd(L[i-1],R[i+1]) for i in range(1, n+1)))
### BUGGY CODE ###

def main():
    n, a, b = map(int, input().split())
    mod = 10**9+7
    p = []
    pa = p.append
    for i in range(200001):
        pa(pow(i, mod-2, mod))
    nn, aa, bb = n, a, b
    ans1 = 1
    for a in range(aa, 0, -1):
        ans1 = ans1*n*p[a] % mod
        n -= 1
    ans2 = 1
    n = nn
    for b in range(bb, 0, -1):
        ans2 = ans2*n*p[b] % mod
        n -= 1
    print((pow(2, nn)-ans1-ans2-1) % mod)


main()

### FIXED CODE ###

def main():
    n, a, b = map(int, input().split())
    mod = 10**9+7

    nn = n
    ans1 = 1
    while a > 0:
        ans1 = (ans1 * n * pow(a, mod-2, mod)) % mod
        n -= 1
        a -= 1

    ans2 = 1
    n = nn
    while b > 0:
        ans2 = (ans2 * n * pow(b, mod-2, mod)) % mod
        n -= 1
        b -= 1

    print((pow(2, nn)-ans1-ans2-1) % mod)


main()
### BUGGY CODE ###

S=input()
keta=len(S)
import numpy as np
dp=np.zeros((keta,26),dtype=int)
DIV=10**9+7

if S[-1]=="?":
  for i in range(10):
    dp[0][i]=1
else:
  dp[0][int(S[-1])]=1
  
dig=1
for i in range(1,keta):
  dig*=10
  if S[keta-1-i]=="?":
    for k in range(10):
      d=k*dig%13
      dp[i][d:d+13]+=dp[i-1][:13]
      dp[i][:13]+=dp[i][13:]
      dp[i][13:]*=0
      dp[i]%=DIV
  else:
    ch=int(S[keta-1-i])
    d=ch*dig%13
    dp[i][d:d+13]+=dp[i-1][:13]
    dp[i][:13]+=dp[i][13:]
    dp[i][13:]*=0
  dp[i]%=DIV

print(dp[len(dp)-1][5])

### FIXED CODE ###

# 各桁についての13で割ったあまりを足し合わせると5になる
# "??"の場合、
# 1桁目が"3"だと、13で割ったあまりは3
# 2桁目が"8"だと、13で割ったあまりは2
# 従い83を13で割ったあまりは5
# 下から数えてN桁目までに、あまりの合計がP(0〜12)になっている数がそれぞれいくつあるかをDPする
# dp[i桁目(下から数える)][あまりの合計]

S = input()
N = len(S)
S = S[::-1] # 逆順にしたほうがやりやすい
dp = [[0] * 13 for i in range(N)]
if S[0] != "?":
  dp[0][int(S[0])] = 1 # 指定の数をとりあえずカウント
else:
  for i in range(10):
    dp[0][i] = 1 # 1桁目は、あまり0〜9になる数が一つずつある
     
# あまりリストの管理 桁数が一つ増えるごとに、各数に対しての13で割ったあまりを計算する
amari = [i for i in range(10)]
amarimap = {1:10,10:9,9:12,12:3,3:4,4:1,2:7,7:5,5:11,11:6,6:8,8:2,0:0}

DIV = 10 ** 9 + 7

# 各桁のあまりの数を更新する
# これにより、桁が増えたときに更新すべきあまりの種類（あまり13種類に対して
# ひと桁は10種類しかない）を管理できる
def update_amari():
  for i in range(len(amari)):
    amari[i] = amarimap[amari[i]]

# 2桁目以降をDP
for i in range(1,N):
  update_amari() # 各桁のあまりをアップデート
  if S[i] == "?":
    # あらゆる数が入る
    # i-1桁目の各数のループと、i桁目のあまりの各数のループ
    for j in range(len(dp[i-1])):
      # 前の桁であまりがjだったとき
      for k in amari:
        dp[i][(j + k) % 13] += dp[i-1][j]
        dp[i][(j + k) % 13] %= DIV
  else:
    # 数が決まっている
    for j in range(len(dp[i-1])):
      # あまりが決まっている
      am = amari[int(S[i])]
      dp[i][(j + am) % 13] += dp[i-1][j]
      dp[i][(j + am) % 13] %= DIV
        
# 最終桁までいったときにあまりが5になる数が必要なので、dp[N-1][5]が答え
print(dp[N-1][5])
### BUGGY CODE ###


n,m = list(map(int,input().split()))
d = [0]*m
ma = 0
mi = 0
for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = ((1<<a)-1) ^ ((1<<b)-1)
    ma = max(ma,a,b)
    mi = min(mi,a,b)
s = ((1<<ma)-1) | ((1<<mi)-1) 
for bit in range(1<<n):
    if bit & s:
      spr = [True]*m
      for k in range(m):
        if (d[k] & bit) > 0:
          spr[k] = False
      if sum(spr) == 0:
        print(sum([1 for i in range(n) if bit & 1<<i]))
        exit()


### FIXED CODE ###


n,m = list(map(int,input().split()))
d = [0]*m
spr = [True]*m
ma = 0
mi = 0
for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = [a,b]

d = sorted(d)
pre = d[0][1]
ans = 1
for i,(a,b) in enumerate(d):
  if a < pre:
    if b < pre:
      pre = b
  else:
    ans += 1
    pre = b

print(ans)
### BUGGY CODE ###

import collections
import heapq

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

c = collections.Counter(A)
x = [-i for i in c.values()]
#print(c)
#print(x)

# K = 1
print(N)

for K in range(2, N+1):
  if len(x) < K:
    print(0)
    continue
  cnt = 0
  q = x[:]
  heapq.heapify(q)
  while len(q) >= K:
    eat = []
    for k in range(K):
      eat.append(heapq.heappop(q))
    for e in eat:
      if e < -1:
        heapq.heappush(q, e + 1)
    cnt += 1
  print(cnt)
  


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int, input().split()))

    # C[x]: 書かれている整数がxであるカードの枚数
    C = [0] * (N + 1)
    D = [0] * (N + 1)
    for a in A:
        C[a] += 1
        D[C[a]] += 1

    # AからK(1<=K<=N)枚ずつカードを抜いてったときに、
    # x回以上抜くことができるか判定する。
    # 抜くことができると判定されたxの最大値が答えになる。

    # 例えば、A = [1 1 1 1 1 2 2 3] とする。
    # -> C = [5 2 1 0 0 0 0 0]
    # ここから2枚ずつカードを抜ける回数を考えるとき、
    # 「3回抜く」とすると、数字の1は、どうやっても2個は絶対余る
    # そこで、絶対余る部分を捨ててCを作り直す(=Eとする)と、
    # E = [3 2 1 0 0 0 0 0]
    # ここから2枚ずつ3回抜けるか判定するなら、
    # sum(E) >= 2 * 3 = 6
    # であるか見ればよい。今回の場合ちょうど6なので、2枚ずつ3回は抜ける。
    
    # 3枚ずつ2回ぬけるか調べる場合、
    # E = [2 2 1] となり、sum(E) = 5 < 3 * 2 = 6 なので、抜けないことが分かる

    # よって、
    # sum(min(C[i], x)) >= K * x であれば抜くことができる
    # S(x) = sum(min(C[i], x)) とすると、
    # S(x) = S(x-1) + [Cの中でC[i] >= x であるものの個数]
    # となることから、Cの中でC[i] >= x であるものの個数 = D(x) とすると、
    # S(x) = sum_(1~x) D(i) となる。
    # つまり、S(x)は、D(x) を最初に全部計算しておいて、累積和をとることで高速に計算できる。

    # S(x) >= K * x となるxの最大値を、kを1からNまで動かして見つければよい。
    # ここで、xを左辺にもっていって、
    # S(x) / x >= Kとなるxの最大値を見つけるようにする。
    # また、S(x) / x = f(x) とおく。

    # 最大値を見つけるために2分探索してもいいが、
    # Kが増えると、答えは以前の値以下になるはずなので、
    # K+1のとき、Kでの答えの位置から0へと探索していけば、O(N)で答えが見つかる
    S = [0] * (N + 1)
    f = [0] * (N + 1)
    for x in range(1, N+1):
        S[x] = S[x-1] + D[x]
        f[x] = S[x] // x

    ans = []
    prev_ans = N
    for K in range(1, N+1):
        a = prev_ans
        while True:
            if f[a] >= K or a == 0:
                break
            a -= 1
        ans.append(a)
        prev_ans = a

    print(*ans, sep='\n')

if __name__ == '__main__':
    main()
### BUGGY CODE ###

N,M,S = map(int,input().split())
edges = [[] for _ in range(2500*50 + 100)]
def indexer(city,coin):
    return 50*coin + city

for _ in range(M):
    u,v,a,b = map(int,input().split())
    u -= 1
    v -= 1
    for scoin in range(a,2501):
        edges[indexer(u,scoin)].append([b,indexer(v,scoin-a)])
        edges[indexer(v,scoin)].append([b,indexer(u,scoin-a)])
## 両替
for i in range(N):
    c,d = map(int,input().split())
    for scoin in range(c,2501):
        edges[indexer(i,scoin-c)].append([d,indexer(i,scoin)])


def dijkstra(s,n,edges):
    import heapq
    dist = [float('inf')] * n
    fixed = [False]*n
    dist[s] = 0
    fixed[s] = True
    priority_que = []
    for e in edges[s]:
        heapq.heappush(priority_que,e)

    while len(priority_que):
        edge = heapq.heappop(priority_que)
        if fixed[edge[1]]:
            continue
        v = edge[1]
        dist[v] = edge[0]
        fixed[v] = True
        for ne in edges[v]:
            heapq.heappush(priority_que,[ne[0]+dist[v], ne[1]])
    return dist

d=dijkstra(indexer(0,min(2500,S)),2500*50 + 100,edges)
for i in range(1,N):
    ans = float('inf')
    for j in range(2501):
        ans = min(ans,d[indexer(i,j)])
    print(ans)

### FIXED CODE ###

N,M,S = map(int,input().split())
edges = [[] for _ in range(2500*50 + 100)]
def indexer(city,coin):
    return 50*coin + city

for _ in range(M):
    u,v,a,b = map(int,input().split())
    u -= 1
    v -= 1
    for scoin in range(a,2501):
        edges[indexer(u,scoin)].append((b,indexer(v,scoin-a)))
        edges[indexer(v,scoin)].append((b,indexer(u,scoin-a)))
## 両替
for i in range(N):
    c,d = map(int,input().split())
    for scoin in range(c,2501):
        edges[indexer(i,scoin-c)].append((d,indexer(i,scoin)))


def dijkstra(s,n,edges):
    import heapq
    dist = [float('inf')] * n
    fixed = [False]*n
    dist[s] = 0
    fixed[s] = True
    priority_que = []
    for e in edges[s]:
        heapq.heappush(priority_que,e)

    while len(priority_que):
        edge = heapq.heappop(priority_que)
        if fixed[edge[1]]:
            continue
        v = edge[1]
        dist[v] = edge[0]
        fixed[v] = True
        for ne in edges[v]:
            heapq.heappush(priority_que,(ne[0]+dist[v], ne[1]))
    return dist

d=dijkstra(indexer(0,min(2500,S)),2500*50 + 100,edges)
for i in range(1,N):
    ans = float('inf')
    for j in range(2501):
        ans = min(ans,d[indexer(i,j)])
    print(ans)
### BUGGY CODE ###

n = int(input())
ans = 10
for i in range(1, n+1):
    if n % i == 0:
        if len(str(max(i, n/i))) <= ans:
            ans = len(str(max(i, n/i)))
print(ans)

### FIXED CODE ###

n = int(input())
ans = 11
for i in range(1, int(n**0.5)+1):
    if n % i != 0:
        continue
    b = n // i
    ans = min(ans, max(len(str(i)),len(str(b))))
print(ans)