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

import collections
import sys

readline = sys.stdin.buffer.readline


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    C = 10**9 + 7

    d = collections.defaultdict(list)

    for a in A:
        B = factorization(a)
        for b in B:
            d[b[0]].append(b[1])
    e = 1
    for k, v in d.items():
        e *= k**max(v)

    ans = 0
    for a in A:
        ans += (e // a)
        ans %= C
    print(ans)


main()


### FIXED CODE ###

import collections
import sys

readline = sys.stdin.buffer.readline


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr


def main():
    N = int(readline())
    A = list(map(int, readline().split()))
    C = 10**9 + 7

    d = collections.defaultdict(list)

    for a in A:
        B = factorization(a)
        for b in B:
            d[b[0]].append(b[1])
    e = 1
    for k, v in d.items():
        e *= k**max(v)

    ans = 0
    for a in A:
        ans += (e // a)
    print(ans % C)


main()
### BUGGY CODE ###

X , Y , Z , K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
temp_sum = []
for i in range(X):
	for j in range(Y):
		for k in range(Z):
			temp_sum.append(A[i] + B[j] + C[k])

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    # ここで分割を行う
    left = arr[:mid]
    right = arr[mid:]

    # 再帰的に分割を行う
    left = merge_sort(left)
    right = merge_sort(right)

    # returnが返ってきたら、結合を行い、結合したものを次に渡す
    return merge(left, right)


def merge(left, right):
    merged = []
    l_i, r_i = 0, 0

    # ソート済み配列をマージするため、それぞれ左から見ていくだけで良い
    while l_i < len(left) and r_i < len(right):
        # ここで=をつけることで安定性を保っている
        if left[l_i] <= right[r_i]:
            merged.append(left[l_i])
            l_i += 1
        else:
            merged.append(right[r_i])
            r_i += 1

    # 上のwhile文のどちらかがFalseになった場合終了するため、あまりをextendする
    if l_i < len(left):
        merged.extend(left[l_i:])
    if r_i < len(right):
        merged.extend(right[r_i:])
    return merged

ans = merge_sort(temp_sum)

for i in range(K):
	print(ans[len(ans) - 1 - i])

### FIXED CODE ###

X , Y , Z , K = map(int,input().split())
A = list(map(int,input().split()))
B = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = []
A.sort()
A.reverse()
B.sort()
B.reverse()
C.sort()
C.reverse()
for i in range(min(K,len(A))):
	if K // (i+1) > 0:
		for j in range(min(K // (i+1),len(B))):
			if K // ((i+1) * (j+1)) > 0:
				for l in range(min(K // ((i+1) * (j+1)),len(C))):
					ans.append(A[i] + B[j] + C[l])

ans.sort()
ans.reverse()
for i in range(K):
	print(ans[i])
### BUGGY CODE ###

#!python3

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


def main():
    P = [(A[i], i + 1) for i in range(N)]
    P.sort(reverse=True)

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for n, p in zip(range(1, N + 1), P):
        for i in range(n):
            j = n - 1 - i

            left = dp[i][j] + p[0] * abs(p[1] - (i + 1))
            dp[i + 1][j] = max(dp[i + 1][j], left)
            
            right = dp[i][j] + p[0] * abs(p[1] - (N - j))
            dp[i][j + 1] = max(dp[i][j + 1], right)

    ans = max([dp[i][N - i] for i in range(N)])
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!python3

# input
N = int(input())
A = list(map(int, input().split()))
# N = 2000
# A = [i for i in range(1, N + 1)]


def main():
    P = [(A[i], i + 1) for i in range(N)]
    P.sort(reverse=True)

    dp = [[0] * (N + 1) for _ in range(N + 1)]
    for n, p in zip(range(1, N + 1), P):
        x, y = p
        for i in range(n):
            j = n - 1 - i
            left = dp[i][j] + x * abs(y - (i + 1))
            dp[i + 1][j] = max(dp[i + 1][j], left)
            right = dp[i][j] + x * abs(y - (N - j))
            dp[i][j + 1] = max(dp[i][j + 1], right)

    ans = max([dp[i][N - i] for i in range(N)])
    print(ans)


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

import collections

N = int(input())

Tree = collections.defaultdict(list)

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

q, k = map(int, input().split())

def bfs(tree, s, distance):
    queue = [s]
    visit = [s]
    distance[s] = 0

    while queue:
        v = queue.pop(0)
        for child in tree[v]:
            if child[0] not in visit:
                distance[child[0]] = distance[v] + child[1]
                visit.append(child[0])
                queue.append(child[0])

distance = {}
bfs(Tree, k, distance)

for i in range(q):
    x, y = map(int, input().split())
    print(distance[x] + distance[y])


### FIXED CODE ###

import sys
import collections

sys.setrecursionlimit(int(1e7))

def dfs(node, parent, distance):
    depth[node] = distance
    for next_node, cost in Tree[node]:
        if next_node != parent:
            dfs(next_node, node, distance + cost)

N = int(input())

Tree = collections.defaultdict(list)

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

q, k = map(int, input().split())

depth = {}
dfs(k, -1, 0)

for i in range(q):
    x, y = map(int, input().split())
    print(depth[x] + depth[y])
### BUGGY CODE ###

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

cnt = 0
for i in range(a, b + 1):
    if i % x == 0:
        cnt += 1

print(cnt)


### FIXED CODE ###

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

if a % x == 0:
    ans = (b // x) - (a // x) + 1
else:
    ans = (b // x) - (a // x)


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

# coding: utf-8


def bpow(x, y, z):
    a = 1
    for b in format(y, 'b'):
        a = (a*a) % z
        if b == '1':
            a = (a*x) % z
        y >>= 1
    return a


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    ret = m*bpow(m-1, n-1, mod) % mod
    ncr = 1
    for i in range(1, k+1):
        ncr = ncr*(n-i)//i
        ret += m*bpow(m-1, n-1-i, mod)*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def bpow(x, y, z):
    a = 1
    for b in format(y, 'b'):
        a = (a*a) % z
        if b == '1':
            a = (a*x) % z
    return a


def solve(*args: str) -> str:
    n, m, k = map(int, args[0].split())
    mod = 998244353

    if m == 1 and n-1 == k:
        return str(1)

    ncr = 1
    p = m*bpow(m-1, n-1, mod) % mod
    ret = p
    inv = bpow(m-1, mod-2, mod)
    for i in range(1, k+1):
        ncr = (ncr * (n-i)*bpow(i, mod-2, mod)) % mod
        p = (p*inv) % mod
        ret += p*ncr % mod

    return str(ret % mod)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

N = int(input())
S = input()
Q = int(input())
K = [int(_) for _ in input().split()]

D = [0] * (N+10)
M = [0] * (N+10)
C = []
DM = [0] * (N+10)
DMC = [0] * (N+10)

for i in range(N):
    if S[i] == 'D':
        D[i] += 1
    elif S[i] == 'M':
        M[i] += 1
        DM[i] += D[i-1]
    elif S[i] == 'C':
        C += [i]
    D[i+1] = D[i]
    M[i+1] = M[i]
    DM[i+1] = DM[i]

for k in K:
    ans = 0
    for c in C:
        ans += DM[c-1]
        if c-k+1 > 0:
            ans -= D[c-k]*(M[c-1]-M[c-k])+DM[c-k]
    print(ans)


### FIXED CODE ###

N = int(input())
S = input()
Q = int(input())
K = [int(_) for _ in input().split()]

D = [0] * (N+10)
M = [0] * (N+10)
C = []
DM = [0] * (N+10)
DMC = [0] * (N+10)

for i in range(N):
    if S[i] == 'D':
        D[i] += 1
    elif S[i] == 'M':
        M[i] += 1
        DM[i] += D[i-1]
    elif S[i] == 'C':
        C += [i]
    D[i+1] = D[i]
    M[i+1] = M[i]
    DM[i+1] = DM[i]

for k in K:
    ans = 0
    for c in C:
        ans += DM[c-1]
        if c-k+1 > 0:
            ans -= D[c-k]*(M[c-1]-M[c-k])+DM[c-k]
    print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
b = 1
c = 10**18
for i in a:
  if i % 1 == 0:
    b *= i 
if b > c :
	 print(-1)
else :
	print(b)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
b = 1
if 0 in a :
  print(0)
  exit()
for i in range(len(a)):
  b = b * a[i]
  if b > 10**18:
    b = -1
    break
print(b)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
MAX_N = 2 * 10**6 + 1
 
# Construct factorial table
fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD
 
fac_inv = [1] + [0] * MAX_N
# Femrmat's little theorem says a**(p-1) mod p == 1
# then, a * a**(p-2) mod p == 1
# it means that a**(p-2) is the inverse element
# Here, Get 1 / n! first
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD
 
def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD
 
def get_rect_sum(r, c):
    total = 0
    for i in range(1, c+2):
        total += mod_nCr(r + i, r)
        total %= MOD
    return total
 
r1, c1, r2, c2 = [int(item) for item in input().split()]
ans = get_rect_sum(r2, c2)
ans += get_rect_sum(r1 - 1, c1 - 1)
ans -= get_rect_sum(r2, c1 - 1)
ans -= get_rect_sum(r1 - 1, c2)
ans %= MOD
print(ans)

### FIXED CODE ###

#!/usr/bin/env python3
import sys
input = sys.stdin.readline
MOD = 10**9 + 7
MAX_N = 2 * 10**6 + 1

# Construct factorial table
fac = [1] + [0] * MAX_N
for i in range(1, MAX_N+1):
    fac[i] = fac[i-1] * (i) % MOD

fac_inv = [1] + [0] * MAX_N
# Femrmat's little theorem says a**(p-1) mod p == 1
# then, a * a**(p-2) mod p == 1
# it means that a**(p-2) is the inverse element
# Here, Get 1 / n! first
fac_inv[MAX_N] = pow(fac[MAX_N], MOD-2, MOD)
for i in range(MAX_N, 1, -1):
    fac_inv[i-1] = fac_inv[i] * i % MOD

def mod_nCr(n, r):
    if n < r or n < 0 or r < 0:
        return 0
    tmp = fac_inv[n-r] * fac_inv[r] % MOD
    return tmp * fac[n] % MOD

def get_rect_sum(r, c):
    total = 0
    for i in range(1, c+2):
        total += mod_nCr(r + i, r)
    return total

r1, c1, r2, c2 = [int(item) for item in input().split()]
ans = get_rect_sum(r2, c2)
ans += get_rect_sum(r1 - 1, c1 - 1)
ans -= get_rect_sum(r2, c1 - 1)
ans -= get_rect_sum(r1 - 1, c2)
ans %= MOD
print(ans)
### BUGGY CODE ###

# ARC097C - K-th Substring
def substring_getter(a: str, x: int) -> set:
    length = len(a)
    ret = set()
    for i in range(length - x + 1):
        ret.add(a[i : i + x])
    return ret


def main():
    s = input()
    k = int(input())
    ans = set()
    for i in range(1, len(s) + 1):
        ans = ans | substring_getter(s, i)
    print(sorted(ans)[k - 1])


if __name__ == "__main__":
    main()

### FIXED CODE ###

# ARC097C - K-th Substring
def substring_getter(a: str, x: int) -> set:
    length = len(a)
    ret = set()
    for i in range(length - x + 1):
        ret.add(a[i : i + x])
    return ret


def main():
    s = input()
    k = int(input())
    ans = set()
    for i in range(1, k + 1):
        ans = ans | substring_getter(s, i)
    print(sorted(ans)[k - 1])


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

n=int(input())
s=[]
for i in range(n):
    s.append("".join(sorted(input())))

S=set(s)

import math

def cmb(n,r):
    return math.factorial(n) // (math.factorial(n-r)*math.factorial(r))


ans=0
for x in S:
    a=s.count(x)
    if a<2:
        continue
    else:
        ans+=cmb(a,2)
print(ans)


### FIXED CODE ###

n=int(input())
s=[]
for i in range(n):
    s.append("".join(sorted(input())))

S=set(s)

from operator import mul
from functools import reduce

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

from collections import Counter

ans=0
l=Counter(s)
for x in S:
    a=l[x]
    if a<2:
        continue
    else:
        ans+=cmb(a,2)
print(ans)
### BUGGY CODE ###

n = int(input())
s = [input() for i in range(n)]
s_ = list(set(s))
co = [0 for i in range(len(s_))]
for i in range(len(s_)):
    co[i] = s.count(s_[i])
ma = max(co)
arg = [i for i in range(len(s_)) if co[i]==ma]
ans = [s_[i] for i in arg]
print("\n".join(sorted(ans)))

### FIXED CODE ###

n = int(input())
s = sorted([input() for i in range(n)])
s_ = sorted(list(set(s)))
if len(s_) != n:
    s.append(0)
    co = [1] + [0 for i in range(len(s_)-1)]
    ind = 0
    for i in range(1, n):
        if s[i-1] == s[i]:
            co[ind] += 1
        else:
            ind += 1
            co[ind] += 1
    ma = max(co)
    arg = [i for i in range(len(s_)) if co[i]==ma]
    ans = [s_[i] for i in arg]
    print("\n".join(sorted(ans)))
    
else:
    print("\n".join(s))
### BUGGY CODE ###

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

R = [None] * S.count("R")
G = [None] * S.count("G")
B = [None] * S.count("B")

ri = 0
gi = 0
bi = 0
for i in range(N):
    if S[i] == "R":
        R[ri] = i+1
        ri+=1
    elif S[i] == "G":
        G[gi] = i+1
        gi += 1
    else:
        B[bi] = i+1
        bi += 1

c = 0
for r in R:
    for g in G:
        for d in [(r + g) / 2, 2 * r - g, 2 * g - r]:
            if d in B:
                c += 1

ans = len(R) * len(G) * len(B) - c
print(ans)

### FIXED CODE ###

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

R = [None] * S.count("R")
G = [None] * S.count("G")
B = [None] * S.count("B")

ri = 0
gi = 0
bi = 0
for i in range(N):
    if S[i] == "R":
        R[ri] = i+1
        ri+=1
    elif S[i] == "G":
        G[gi] = i+1
        gi += 1
    else:
        B[bi] = i+1
        bi += 1
R = set(R)
G = set(G)
B = set(B)

c = 0
for r in R:
    for g in G:
        for d in [(r + g) / 2, 2 * r - g, 2 * g - r]:
            if d in B:
                c += 1

ans = len(R) * len(G) * len(B) - c
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int,input().split()))
ans = 0

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

a.sort(reverse=True)

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

print(ans)

### FIXED CODE ###

from operator import itemgetter

n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]


BC.sort(reverse=True, key=itemgetter(1))
cnt = 0
for b, c in BC:
    if cnt + b > n:
        b = n-cnt
    for _ in range(b):
        A.append(c)
    cnt += b
    if cnt == n:
        break

A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

n = int(input())
ans = n%1
for i in range(2,n+1):
    ans += (i-1)%i
    # print(i-1,i,ans)
print(ans)

### FIXED CODE ###

n = int(input())
print(n*(n-1)//2)
### BUGGY CODE ###

N,W = map(int,input().split())
w = []
v = []
for _ in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)
dp = [[10000000000000 for _ in range(100 * W + 10)] for _ in range(110) ]
ans = 0
for i in range(N):
    dp[i][0] = 0
for i in range(N):
    for j in range(N * 100):
        dp[i + 1][j + v[i]] = min(dp[i+1][j+v[i]],dp[i][j]+w[i])
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
for i in range(N * 100 + 1):
    if dp[N][i] <= W:
        ans = max(ans,i)
print(ans)


### FIXED CODE ###

N,W = map(int,input().split())
w = []
v = []
for _ in range(N):
    x,y = map(int,input().split())
    w.append(x)
    v.append(y)
dp = [[10000000000000 for _ in range(2001 * N + 10)] for _ in range(N + 2) ]
ans = 0
for i in range(N):
    dp[i][0] = 0
for i in range(N):
    for j in range(N * 1000):
      	
        dp[i + 1][j + v[i]] = min(dp[i+1][j+v[i]],dp[i][j]+w[i])
        dp[i+1][j] = min(dp[i+1][j],dp[i][j])
for i in range(N * 1000 + 1):
    if dp[N][i] <= W:
        ans = max(ans,i)
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
m=0
for i in range(n-k+1):
  if sum(p[i:i+k])>m:
    m=sum(p[i:i+k])
print((m+k)/2)
    


### FIXED CODE ###

n,k=map(int,input().split())
p=list(map(int,input().split()))
a=[0]*n
a[0]=p[0]
for i in range(n-1):
  a[i+1]=a[i]+p[i+1]
m=a[k-1]
for j in range(n-k):
  if a[j+k]-a[j]>m:
    m=a[j+k]-a[j]
print((m+k)/2)
### BUGGY CODE ###

import sys
import math
import itertools
import collections
from collections import deque

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()

NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()

def get_sieve_of_eratosthenes(n):
    if not isinstance(n, int):
        raise TypeError('n is int type.')
    if n < 2:
        raise ValueError('n is more than 2')
    prime = []
    limit = math.sqrt(n)
    data = [i + 1 for i in range(1, n)]
    while True:
        p = data[0]
        if limit <= p:
            return prime + data
        prime.append(p)
        data = [e for e in data if e % p != 0]

def main():
    A, B = NMI()
    GCD = math.gcd(A, B)
    
    if A == 1 or B == 1:
      print(1)
    else:
      
      cnt = 0
      for n in get_sieve_of_eratosthenes(GCD):

          if GCD % n == 0:
              cnt += 1

              while GCD % n == 0:
                  GCD = GCD//n
          if GCD == 1:
              print(cnt+1)
              sys.exit()
    


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
import math
import itertools
import collections
from collections import deque
 
sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
 
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()
 
def main():
    A, B = NMI()
    GCD = math.gcd(A, B)
    N=GCD
    
    cnt = 0
    
    ls=[]
    
    for n in range(2,int(N**0.5)+2):
 
        if GCD % n == 0:
            cnt += 1
 
            while GCD % n == 0:
                GCD = GCD//n
                ls.append(n)
        
    if GCD == 1:
        print(cnt+1)
    else:
        print(cnt+2) 

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

def main():
    import sys
    readline = sys.stdin.readline

    inf = 10 ** 9

    n, k = map(int, readline().split())
    *h, = map(int, readline().split())
    h = [inf] + h + [inf] * (k - 1)  # 1-indexed化

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

    for i in range(1, n):  # ジャンプ元,1-indexed
        for j in range(1, k + 1):
            dp[i + j] = min(
                dp[i + j],
                dp[i] + abs(h[i + j] - h[i]))

    print(dp[n])


if __name__ == '__main__':
    main()


### FIXED CODE ###

INF = 10 ** 10

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

dp = [INF for _ in range(N)]
dp[0] = 0
# 0-indexed

for i in range(1, N):
    for k in range(1, K + 1):
        if i - k >= 0:
            dp[i] = min(dp[i], dp[i - k] + abs(h[i] - h[i - k]))

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

# -*- coding: utf-8 -*-
import sys
N,M,K=map(int, sys.stdin.readline().split())

par=[ i for i in range(N+1) ]
size=[ 1 for i in range(N+1) ]

def root(x):
    x=par[x]
    while par[x]!=x:
        x=par[x]
    return x

def same(x,y):
	return root(x)==root(y)

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y: return
    par[x]=y
    size[y]+=size[x]

def getsize(x):
	return size[root(x)]

al_ok=[ 0 for i in range(N+1) ]	#隣接で友達関係のカウント

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)
    al_ok[a]+=1
    al_ok[b]+=1

al_ng=[ 0 for i in range(N+1) ]	#隣接でブロックしている人のカウント
for _ in range(K):
    c,d=map(int, sys.stdin.readline().split())
    if same(c,d):
        al_ng[c]+=1
        al_ng[d]+=1

for i in range(1,N+1):
    print getsize(i)-1-al_ok[i]-al_ng[i],


### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
N,M,K=map(int, sys.stdin.readline().split())

par=[ i for i in range(N+1) ]
size=[ 1 for i in range(N+1) ]

def root(x):
    while par[x]!=x:
        x=par[x]
    return x

def same(x,y):
	return root(x)==root(y)

def unite(x,y):
    x=root(x)
    y=root(y)
    if x==y: return
    if size[x]<size[y]: x,y=y,x  #xの要素数が大きいように
    size[x]+=size[y]
    par[y]=x


def getsize(x):
	return size[root(x)]

al_ok=[ 0 for i in range(N+1) ]	#隣接で友達関係のカウント

for _ in range(M):
    a,b=map(int, sys.stdin.readline().split())
    unite(a,b)
    al_ok[a]+=1
    al_ok[b]+=1

al_ng=[ 0 for i in range(N+1) ]	#隣接でブロックしている人のカウント
for _ in range(K):
    c,d=map(int, sys.stdin.readline().split())
    if same(c,d):
        al_ng[c]+=1
        al_ng[d]+=1

for i in range(1,N+1):
    print getsize(i)-1-al_ok[i]-al_ng[i],
### BUGGY CODE ###

N, K = map(int, input().split())
mod = 10 ** 9 + 7
for i in range(1, K+1):
    if i > N - K + 1:
        print(0)
    else:
        ans = 1
        for j in range(K - i):
            ans = ans * (K - 1 - j )% mod
            ans = ans * pow(K - i - j, mod-2, mod) % mod
        for k in range(N - K - i + 1):
            ans = ans * (N - K + 1 - k) % mod
            ans = ans * pow(N - K - i + 1 - k, mod - 2, mod) % mod
        print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
mod = 10 ** 9 + 7
for i in range(1, K+1):
    if i > N - K + 1:
        print(0)
    else:
        ans = 1
        tmp = 1
        for j in range(K - i):
            ans = ans * (K - 1 - j )% mod
            tmp = tmp * (K - i - j) % mod
        for k in range(N - K - i + 1):
            ans = ans * (N - K + 1 - k) % mod
            tmp = tmp * (N - K - i + 1 - k) % mod
        ans = ans % mod * pow(tmp, mod - 2, mod) % mod
        print(ans)
### BUGGY CODE ###

S = input()
K = int(input())

D=5000000000000000

tmp=0
for s in S:
  t=1
  for _ in range(D):
    t=t*int(s)
    if tmp+t>=K:
      print(s)
      break
  else:
    continue
  break

### FIXED CODE ###

S = input()
K = int(input())

D=5000000000000000

tmp=0
for s in S:
  if s=='1':
    tmp+=1
    if tmp>=K:
      print(s)
      break
    continue
    
  t=1
  for _ in range(D):
    t=t*int(s)
    if tmp+t>=K:
      print(s)
      break
  else:
    tmp+=t
    continue
  break
### BUGGY CODE ###

A, B , C , D = map(int, input().split())
count= 0
for i in range(A, B+1):
    if i % C != 0 :
        if i % D != 0:
            count += 1
print(count)


### FIXED CODE ###

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

bc = B // C 
bd = B // D
bcd = B // (C*D//fractions.gcd(C, D))
ans = B- (bc + bd - bcd)
ac = (A-1) // C
ad = (A-1) // D
acd = (A-1) //(C*D//fractions.gcd(C, D))
ans2=  A-1 - (ac + ad - acd)
ans = ans - ans2
print(ans)
### BUGGY CODE ###

n,x = map(int,input().split())
lis = list(map(int,input().split()))
ans = 0
magic = 0
for i in range(n):
    cou = lis[i]
    for m in range(1,n):
        if i + m >= n:
            co = i + m - n
        else:
            co = i + m
        cou = min(cou,lis[co]+x * max(m-magic,0))
        if cou == lis[co] + x * max(m-magic,0):
            magic = max(m,magic)
    ans += cou
print(ans)

### FIXED CODE ###

N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
s_cost = a.copy()
cost = sum(s_cost)
for k in range(1,N):
    for i in range(N):
        if s_cost[i] > a[(i-k)%N] :
            s_cost[i] = a[(i-k)%N]
    if cost > k*x + sum(s_cost):
        cost = k*x + sum(s_cost)
    else:
        break

print(cost)