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

import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=100*51
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()


### FIXED CODE ###

import sys
input = sys.stdin.readline
def main():
  n,m,s=map(int,input().split())
  uvab=[list(map(int,input().split())) for _ in range(m)]
  cd=[list(map(int,input().split())) for _ in range(n)]
  g=[[]for _ in range(n)]
  for u,v,a,b in uvab:
    g[u-1].append((v-1,a,b))
    g[v-1].append((u-1,a,b))
  import heapq
  inf=pow(10,21)
  max_s=50*50
  dp=[[inf]*(max_s+1)for _ in range(n)]
  kakutei=[[0]*(max_s+1)for _ in range(n)]
  dp[0][min(s,max_s)]=0
  todo=[[0,0,min(s,max_s)]] # [dp[v][i],v,i]
  heapq.heapify(todo)
  flgs=[0]*n
  flg=0
  ans=[inf]*n
  while flg<n:
    _,v,i=heapq.heappop(todo)
    if kakutei[v][i]==1:
      continue
    kakutei[v][i]=1
    if flgs[v]==0:
      flg+=1
      flgs[v]=1
    c,d=cd[v]
    ans[v]=min(ans[v],_)
    # 両替
    j=min(max_s,i+c)
    if kakutei[v][j]==0:
      dp[v][j]=min(dp[v][j],dp[v][i]+d)
      heapq.heappush(todo,[dp[v][j],v,j])
    # 鉄道
    l=g[v]
    for u,a,b in l:
      if i-a>=0 and kakutei[u][i-a]==0:
        dp[u][i-a]=min(dp[u][i-a],dp[v][i]+b)
        heapq.heappush(todo,[dp[u][i-a],u,i-a])
  print(*ans[1:],sep='\n')
if __name__=='__main__':
  main()
### BUGGY CODE ###

from collections import Counter
from math import factorial
n = int(input())
print(n)
a = [int(i) for i in input().split()]
twice = Counter(a).most_common(1)[0][0]
x,y = (i for i,j in enumerate(a) if j == twice)
num,y = n+1,n-y
X,Y = factorial(x),factorial(y)
for i in range(2,x+y+2):
	num = num*(n+2-i)//i
	ans,numx,numy = num,1,1
	for j in range(max(0,i-y-1),min(i,x+1)):
		if j==0: ans -= Y//(factorial(i-1)*factorial(y-i+1))
		elif j==i-1: ans -= X//(factorial(j)*factorial(x-j))
		else: ans -= (X//(factorial(j)*factorial(x-j)))*(Y//(factorial(i-j-1)*factorial(y-i+j+1)))
	print(ans%(10**9+7))
for i in range(x+y+2,n+2):
	num = num*(n+2-i)//i
	print(num%(10**9+7))

### FIXED CODE ###

def comb(n,k):
	if n<k or n==0: return 0
	elif k==0: return 1
	else: return f[n]*p[k]*p[n-k]%(10**9+7)
from collections import Counter
n = int(input())
print(n)
a = [int(i) for i in input().split()]
twice = Counter(a).most_common(1)[0][0]
x,y = (i for i,j in enumerate(a) if j == twice)
num,y,f,p = 1,n-y,[1],[1]
for i in range(1,n+2):
	f.append(f[-1]*i%(10**9+7))
	p.append(pow(f[-1],10**9+5,10**9+7))
for i in range(2,x+y+2): print((comb(n+1,i)-comb(x+y,i-1))%(10**9+7))
for i in range(x+y+2,n+2): print(comb(n+1,i))
### BUGGY CODE ###

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

### FIXED CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
ans = 1 
if 0 in a:
    print(0)
    sys.exit(0)
for i in a:
    ans *= i
    if ans > 10**18:
        print(-1)
        sys.exit(0)
print(ans)
### BUGGY CODE ###

import heapq

INF = float('inf')
yen = 10**15

def pcc(src, adj):
	global n
	pq = [(0,src)]
	heapq.heapify(pq)
	dist = [INF]*(n+1)
	dist[src] = 0
	while pq:
		d,u = heapq.heappop(pq)
		for w, v in adj[u]:
			if dist[v] > dist[u] + w:
				dist[v] = dist[u] + w
				heapq.heappush(pq, (dist[v], v))
	return dist

n,m,s,t = (int(i) for i in input().split())
adjs = []
adjt = []
for i in range(n+1):
	adjs += [[]]
	adjt += [[]]
for i in range(m):
	u,v,a,b = (int(i) for i in input().split())
	adjs[u].append([a,v])
	adjs[v].append([a,u])
	adjt[u].append([b,v])
	adjt[v].append([b,u])

dist_s = pcc(s,adjs)
dist_t = pcc(t,adjt)



ans = [0]*(n+1)
ans[n] = dist_s[n] + dist_t[n]
for i in range(n-1,0,-1):
	ans[i] = min(ans[i+1], dist_s[i] + dist_t[i])
for i in range(1,n+1):
	print(yen-ans[i])


### FIXED CODE ###

import heapq
def dijkstra(s, neighbor):
	dist = [float('inf')] * N
	dist[s] = 0
	que = [(0, s)]
	heapq.heapify(que)
	while que:
		d, v = heapq.heappop(que)
		if d > dist[v]:
			continue
		for u, l in neighbor[v]:
			tmp_d = d + l
			if tmp_d < dist[u]:
				dist[u] = tmp_d
				heapq.heappush(que, (tmp_d, u))
	return dist
 
N, M, s, t = map(int, input().split())
yen = [[] for _ in range(N)]
snuuk = [[] for _ in range(N)]
for _ in range(M):
	u, v, a, b = map(int, input().split())
	yen[u-1].append((v-1, a))
	yen[v-1].append((u-1, a))
	snuuk[u-1].append((v-1, b))
	snuuk[v-1].append((u-1, b))
 
dist_s = dijkstra(s-1, yen)
dist_t = dijkstra(t-1, snuuk)
ans = [-1] * N
tmp = float('inf')
for i in range(N-1, -1, -1):
	if dist_s[i] + dist_t[i] < tmp:
		tmp = dist_s[i] + dist_t[i]
	ans[i] = 10 ** 15 - tmp
print(*ans, sep='\n')
### BUGGY CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
A.sort()
C = Counter(A)
ans = N
l = 1
r = 10**5
while l != r or (l == r and C[l] > 1):
    while C[l] <= 1:
        l += 1
    while C[r] <= 1:
        r -= 1
    C[l] -= 1
    C[r] -= 1
    ans -= 2
print(ans)


### FIXED CODE ###

from collections import Counter

N = int(input())
A = list(map(int, input().split()))
C = Counter(A)
ans = len(C)
if (N-ans) % 2 == 1:
    ans -= 1
print(ans)
### BUGGY CODE ###

H,W,M=map(int,input().split())
L=[0 for _ in range(H)]
C=[0 for _ in range(W)]
B=[list(map(int,input().split())) for _ in range(M)]

for i in range(M):
    L[B[i][0]-1]+=1
    C[B[i][1]-1]+=1

LM=max(L)
CM=max(C)

l=[]
c=[]
for j in range(H):
    if L[j]==LM:
        l.append(j)

for k in range(W):
    if C[k]==CM:
        c.append(k)

ans=LM+CM-1
for a in l:
    for b in c:
        if [a+1,b+1] not in B:
            ans=LM+CM
            break
    if ans==LM+CM:
        break
print(ans)

### FIXED CODE ###

H,W,M=map(int,input().split())
L=[0 for _ in range(H)]
C=[0 for _ in range(W)]
B={}
for _ in range(M):
    a,b=map(int,input().split())
    B[str(a)+","+str(b)]=0
    L[a-1]+=1
    C[b-1]+=1

LM=max(L)
CM=max(C)

l=[]
c=[]
for j in range(H):
    if L[j]==LM:
        l.append(j)

for k in range(W):
    if C[k]==CM:
        c.append(k)

ans=LM+CM-1

for a in l:
    for b in c:
        if str(a+1)+","+str(b+1) not in B:
            ans=LM+CM
            break
    if ans==LM+CM:
        break
print(ans)
### BUGGY CODE ###

import math
a,b,n=map(int,input().split())
li=[]
for i in range(n+1):
    c=math.floor((a*i)/b)-(a*math.floor(i/b))
    li.append(c)
print(max(li))

### FIXED CODE ###

import math
a,b,n=map(int,input().split())
d=min(n,b-1)
c=math.floor((a*d)/b)-(a*math.floor(d/b))
print(c)
### BUGGY CODE ###

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

### FIXED CODE ###

n,k = (int(x) for x in input().split())
list = list(map(int, input().split()))
max=0
list2=[0]
for i in range(n):
	list2.append(list2[i]+list[i])
for i in range(n-k+1):
	if max < list2[i+k] - list2[i]:
		max=list2[i+k]-list2[i]
print((max+k)/2)
### BUGGY CODE ###

N, M = map(int, input().split())

result=1
for i in range(M//N):
  A = M//N-i
  if(M%A == 0) :
    result=A
    break
    
print(result)

### FIXED CODE ###

N, M = map(int, input().split())

def make_yakusuu(n):
  yakusuu=[]
  for i in range(1,int(n**0.5)+1):
    if n%i == 0:
      yakusuu.append(i)
      if i != n//i:
        yakusuu.append(n//i)      
  yakusuu.sort(reverse = True)
  return yakusuu

list=make_yakusuu(M)
A=list[0]
result=1
i=0
while(A>1):
  if (N<=M/A):
    result=A
    break
  else:
    i+=1
    A=list[i]
    
print(result)
### BUGGY CODE ###

import itertools
K, S = map(int, input().split())
cnt = 0
for i in itertools.product(range(K+1), repeat=3):
    cnt += sum(i) == S
print(cnt)

### FIXED CODE ###

K, S = list(map(int, input().split()))
K += 1
cnt = 0
for i in range(K):
    if i+K*2<=S : continue
    if i>S : continue
    for j in range(min(K, S-i+1)):
        if i+j+K<=S : continue
        if i+j>S : break
        cnt += 1
print(cnt)
### BUGGY CODE ###

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


dices = list(map(int, input().split()))

ans_index = 0
max_sum = 0
for i in range(len(dices) - K + 1):
    # summation = 0
    # for j in range(K):
    #     summation += dices[i + j]
    summation = sum(dices[i:i + K])
    if max_sum < summation:
        max_sum = summation
        ans_index = i

ans = 0
for dice in dices[ans_index:ans_index + K]:
    ans += sum(list(range(1, dice + 1))) / dice
print(ans)

### FIXED CODE ###

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

dices = list(map(int, input().split()))

# 期待値は(1+P)/2 https://rikeilabo.com/sum-formula-of-numerical-sequence
# 累積和を求めておく．隣接するK個の和はS_{j+K} - S_j
# 期待値の前計算→累積和の計算→隣接するK項の和の計算 (１乗オーダー)
E_list = []
for dice in dices:
    E_list.append((1 + dice) * 0.5)

S_list = []  # i番目までのサイコロの期待値の累積和
for i in range(len(dices)):
    # S_list.append(sum(E_list[:i + 1]))  # アホ
    S_list.append(E_list[0] if i == 0 else S_list[i - 1] + E_list[i])

print(max(list(S_list[j + K] - S_list[j] for j in range(len(dices) - K))) if len(dices) != K else S_list[-1])
### BUGGY CODE ###

n = int(input())
a = []
count = 0
for _ in range(n):
    s = input()
    if s not in a:
        a.append(s)
        count += 1
print(count)

### FIXED CODE ###

n = int(input())
str_list = []
count = 1
for _ in range(n):
    s = input()
    str_list.append(s)
str_list.sort()
for i in range(n-1):
    if str_list[i] != str_list[i+1]:
        count += 1
print(count)
### BUGGY CODE ###

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

m = 0
import numpy as np
p = np.array(p)
for i in range(n-k+1):
  m = max(m, sum(p[i:i+k]))
print((m + k)/2)

### FIXED CODE ###

import itertools

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

pa = list(itertools.accumulate([0] + p))

m = 0
for i in range(n-k+1):
  s = pa[i+k] - pa[i]
  if s > m:
    m = s
print((m+k)/2)
### BUGGY CODE ###

import numpy as np


def main():
    s = input()

    b = np.array([])
    cnt = 0
    for i, e in enumerate(s):
        if e == "B":
            b = np.append(b, i)
            cnt += 1

    b_fin = np.arange(len(s) - cnt, len(s))

    ans = int(np.sum(b_fin - b))

    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import numpy as np


def main():
    s = input()

    b = []
    cnt = 0
    for i, e in enumerate(s):
        if e == "B":
            b.append(i)
            cnt += 1

    b = np.array(b)
    b_fin = np.arange(len(s) - cnt, len(s))

    ans = int(np.sum(b_fin - b))

    print(ans)


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

s = input()
s = s.replace("BC", "D")
result = 0
for i in range(len(s)-1):
    if s[i]=="A":
        x = 0
        for j in range(i, len(s)):
            if s[j]=="A":
                continue
            elif s[j]=="D":
                x += 1
            else:
                break
        result += x
print(result)

### FIXED CODE ###

s = input()
s = s.replace("BC", "D")
result = 0
i = 0
while i < len(s)-1:
    if s[i]=="A":
        y = 1
        for j in range(i+1, len(s)):
            i += 1
            if s[j]=="A":
                y += 1
            elif s[j]=="D":
                result += y
            else:
                break
    else:
        i += 1
print(result)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

N,M = list(map(int,input().split()))
A = sorted(list(map(int,input().split())))
Amin = min(A)
tmp = []
for _ in range(M):
    a,b= list(map(int,input().split()))
    if b>=Amin:
        tmp.append([a,b])

tmp = sorted(tmp,key = lambda x:-x[1])
cnt = 0
t = []
if tmp != []:
    for i in range(M):
        t=t+[tmp[i][1]]*tmp[i][0]
        cnt+= tmp[i][0]
        if cnt >=N:
            break
        if cnt<N and tmp[i][1] <= A[cnt-1]:
            break
for i in range(min(N,len(t))):
    if A[i] < t[i]:
        A[i] = t[i]
print(sum(A))



### FIXED CODE ###

import sys
input = sys.stdin.readline

def sol():
    N,M = list(map(int,input().split()))
    A = list(map(int,input().split()))
    tmp = sorted([list(map(int,input().split())) for _ in range(M)],key = lambda x:-x[1])

    t = []
    for a,b in tmp:
        t+=[b]*a
        
        if len(t) >=N:
            break

    A += t
    A.sort(reverse = 1)
    print(sum(A[:N]))

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

from collections import deque


def bfs(yx, H, W, S):
    dirs = (1, W+2, -1, -W-2)
    visited = [0] * ((H+2) * (W+2))
    q = deque()
    q.append((yx, 0))
    max_depth = 0
    while q:
        yx, depth = q.popleft()
        visited[yx] = 1
        max_depth = max(max_depth, depth)
        for dyx in dirs:
            nyx = yx + dyx
            if S[nyx] == '.' and visited[nyx] == 0:
                q.append((nyx, depth+1))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = deque()
    S.append('#' * (W+2))
    for h in range(H):
        buf = input()
        S.append('#' + buf + '#')
    S.append('#' * (W+2))
    S = ''.join(S)

    dist_max = 0
    for yx in range((H+2) * (W+2)):
        if S[yx] == '.':
            d = bfs(yx, H, W, S)
            dist_max = max(d, dist_max)
    print(dist_max)


if __name__ == '__main__':
    solve()


### FIXED CODE ###

from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


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

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

ans = 0

for i in range(1,N):
    ans += A[i-1] * sum(A[i:])
    ans = ans % 1000000007

print(ans)


### FIXED CODE ###

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

ans = 0
sum = sum(A)

for i in range(1,N):
    sum -= A[i-1]
    ans += A[i-1] * sum
    ans = ans % 1000000007

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

N, A = map(int, input().split())
lst = [int(x) for x in input().split()]
ret = 0
for i in range(2 ** N):
    n = 0
    cnt = 0
    for j in range(N):
        if i >> j & 1:
            n += lst[j]
            cnt += 1
    if cnt > 0 and n / cnt == A:
        ret += 1
print(ret)


### FIXED CODE ###

N, A = map(int, input().split())
lst = [int(x) - A for x in input().split()]
dp = [[0] * (100 * N + 1) for _ in range(N + 1)]
dp[0][50 * N] = 1
for i in range(N):
    for j in range(50, 100 * N + 1 - 50):
        dp[i + 1][j] = dp[i][j] + dp[i][j - lst[i]]
print(dp[N][50 * N] - 1)
### BUGGY CODE ###

a=list(map(int,input().split()))
ans=0
for i in range(a[0]+1):
    for j in range(a[0]+1):
        for k in range(a[0]+1):
            if i+j+k==a[1]:
                ans+=1
print(str(ans))

### FIXED CODE ###

a=list(map(int,input().split()))
ans=0
for i in range(a[0]+1):
    for j in range(a[0]+1):
        if a[1]-i-j <= a[0] and a[1]-i-j >= 0:
            ans+=1
print(str(ans))
### BUGGY CODE ###

N,M=map(int,input().split())
l,r=map(int,input().split())
s={i for i in range(l,r+1)}
for _ in range(M-1):
    l, r = map(int, input().split())
    t = {i for i in range(l, r + 1)}
    s = s & t
    if len(s) == 0:
        print(0)
        exit(0)
print(len(s))

### FIXED CODE ###

N,M=map(int,input().split())
lmax=0
rmin=9999999
for i in range(M):
    l,r=map(int,input().split())
    lmax=max(lmax,l)
    rmin=min(rmin,r)

print(max(rmin-lmax+1,0))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
dp = [0] * (n + 1)
mod = 10 ** 9 + 7

dp[0] = 1
if not 1 in a:
    dp[1] = 1
for i in range(1, n):
    if i + 1 in a:
        dp[i + 1] = 0
    else:
        dp[i + 1] = (dp[i] + dp[i - 1]) % mod
print(dp[n])

### FIXED CODE ###

n, m = map(int, input().split())
dp = [0] * (n + 1)
a = []
for i in range(m):
    aa = int(input())
    dp[aa] = -1
    a.append(aa)
for i in range(m - 1):
    if a[i] + 1 == a[i + 1]:
        print(0)
        exit()
mod = 10 ** 9 + 7

dp[0] = 1
if 1 in a:
    dp[1] = 0
else:
    dp[1] = 1
for i in range(1, n):
    if dp[i + 1] == -1:
        dp[i + 1] = 0
    else:
        dp[i + 1] = (dp[i] + dp[i - 1]) % mod
print(dp[n])
### BUGGY CODE ###

N,Q = map(int,input().split(" "))
A = []

B = [0 for j in range(N)]
for i in range(N-1):
    A.append(list(map(int,input().split(" "))))
    
A = sorted(A)
for j in range(Q):
    tmp = list(map(int,input().split(" ")))
    B[tmp[0]-1] += tmp[1]


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

for i in range(N):
        print(B[i],end=" ")

### FIXED CODE ###

N,Q = map(int,input().split(" "))
A = [0]*N

B = [0 for j in range(N)]
for i in range(N-1):
    a,b = map(int,input().split(" "))
    A[b-1] = a-1
    
for j in range(Q):
    tmp = list(map(int,input().split(" ")))
    B[tmp[0]-1] += tmp[1]

for i in range(1,N):
        B[i] += B[A[i]]
for i in range(N):
        print(B[i],end=" ")
### BUGGY CODE ###

from itertools import combinations
class UnionFind():
  def __init__(self, x):
    self.x=x
    self.root=[-1]*(N+1)
    self.rnk=[0]*(N+1)
  
  def Find_root(self, x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.Find_root(self.root[x])
      return self.root[x]
    
  def Unite(self, x, y):
    x = self.Find_root(x)
    y = self.Find_root(y)
    if x==y:
      return
    elif self.rnk[x]>self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x]==self.rnk[y]:
        self.rnk[y]+=1
  
  def isSameGroup(self, x, y):
    return self.Find_root(x)==self.Find_root(y)
  
  def Count(self, x):
    return -self.root[self.Find_root(x)]
N,K,L=map(int,input().split())
u1=UnionFind(N)
u2=UnionFind(N)
for _ in range(K):
  x,y=map(int,input().split())
  u1.Unite(x,y)
for _ in range(L):
  x,y=map(int,input().split())
  u2.Unite(x,y)

l=[1]*N
for i,j in combinations(range(N),2):
  if u1.isSameGroup(i+1,j+1) and u2.isSameGroup(i+1,j+1):
    l[i]+=1
    l[j]+=1
  else:
    continue
l=[str(n) for n in l]
print(' '.join(l))
    

### FIXED CODE ###

from itertools import combinations
from collections import Counter
class UnionFind():
  def __init__(self, x):
    self.x=x
    self.root=[-1]*(N+1)
    self.rnk=[0]*(N+1)
  
  def Find_root(self, x):
    if self.root[x]<0:
      return x
    else:
      self.root[x]=self.Find_root(self.root[x])
      return self.root[x]
    
  def Unite(self, x, y):
    x = self.Find_root(x)
    y = self.Find_root(y)
    if x==y:
      return
    elif self.rnk[x]>self.rnk[y]:
      self.root[x] += self.root[y]
      self.root[y] = x
    else:
      self.root[y] += self.root[x]
      self.root[x] = y
      if self.rnk[x]==self.rnk[y]:
        self.rnk[y]+=1
  
  def isSameGroup(self, x, y):
    return self.Find_root(x)==self.Find_root(y)
  
  def Count(self, x):
    return -self.root[self.Find_root(x)]
N,K,L=map(int,input().split())
u1=UnionFind(N)
u2=UnionFind(N)
for _ in range(K):
  x,y=map(int,input().split())
  u1.Unite(x-1,y-1)
for _ in range(L):
  x,y=map(int,input().split())
  u2.Unite(x-1,y-1)
l=[]
for i in range(N):
  l.append((u1.Find_root(i), u2.Find_root(i)))
c = Counter(l)
ans = []
for i in range(N):
  ans.append(c[(u1.Find_root(i), u2.Find_root(i))])
print(*ans)
### BUGGY CODE ###


# -*- coding: utf-8 -*-
# 整数の入力
# a = int(input())
s = input()
# s = '11011010001011'
# スペース区切りの整数の入力
# a, b, k = map(int, input().split())

counter = 0
while s.find('01') != -1 or s.find('10') != -1:
    if s.find('01') != -1:
        s = s.replace('01', '', 1)
        counter += 2
    if s.find('10') != -1:
        s = s.replace('10', '', 1)
        counter += 2

# 出力
print("{}".format(int(counter)))

### FIXED CODE ###

s = input()
counter = 0
length = len(s)
count0 = s.count('0')
count1 = s.count('1')

print("{}".format(int(length - abs(count0 - count1))))
### BUGGY CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LI()
 
i = 10**18
ans = 1
if 0 in set(A):
    print(0)
else:
    for a in A:
        ans *= a
    if ans > i:
        print(-1)
    else:
        print(ans)

### FIXED CODE ###

import bisect,collections,copy,heapq,itertools,math,numpy,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())

N = I()
A = LI()
#print(A)
i = 10**18
ans = 1
if min(A) == 0:
    ans = 0
else:
    for a in A:
        ans *= a
        if ans > i:
            ans = -1
            break
print(ans)
### BUGGY CODE ###

#

import sys
from math import ceil
input=sys.stdin.readline

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    K_i=[int(A[i]/sum(A)*(K+N)-1) for i in range(N)]
    dA=[A[i]/(K_i[i]+1) for i in range(N)]
    res=K-sum(K_i)
    b=[]
    for i in range(N):
        b.append([dA[i],i])
    b.sort(reverse=True)
    now=0
    for i in range(res):
        K_i[b[now][1]]+=1
        dA[b[now][1]]=A[b[now][1]]/(K_i[b[now][1]]+1)
        if dA[b[now][1]]<b[now+1][0]:
            now+=1
    
    maxi=dA.index(max(dA))
    print(ceil(A[maxi]/(K_i[maxi]+1)))
    
    
    
if __name__=="__main__":
    main()


### FIXED CODE ###

#

import sys
from math import ceil
input=sys.stdin.readline

def main():
    N,K=map(int,input().split())
    A=list(map(int,input().split()))
    aveA=sum(A)/N
    d=K/N
    K_i=[int(A[i]/aveA*d) for i in range(N)]
    dA=[A[i]/(K_i[i]+1) for i in range(N)]
    res=K-sum(K_i)
    b=[]
    for i in range(N):
        b.append([dA[i],i])
    b.sort(reverse=True)
    now=0
    for i in range(res):
        K_i[b[now][1]]+=1
        dA[b[now][1]]=A[b[now][1]]/(K_i[b[now][1]]+1)
        if dA[b[now][1]]<b[now+1][0]:
            now+=1
    
    maxi=dA.index(max(dA))
    print(ceil(A[maxi]/(K_i[maxi]+1)))
    
    
    
if __name__=="__main__":
    main()