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

start_x, start_y, goal_x, goal_y = map(int, input().split())
n = int(input())
info = [(start_x, start_y, 0)] \
       + [tuple(map(int, input().split())) for i in range(n)] \
       + [(goal_x, goal_y, 0)]

#i番目のバリアからj番目のバリアまでの移動について、
#受ける光線量を辺の重みとしてグラフを構築する(O(N^2))
graph = [[] for i in range(n+2)]
for i in range(n+2):
    for j in range(i,n+2):
        diff_x = info[i][0] - info[j][0]
        diff_y = info[i][1] - info[j][1]
        sum_radius = info[i][2] + info[j][2]
        cost = max(0, ((diff_x)**2 + (diff_y)**2 )**(0.5) - sum_radius) 
        graph[i].append((j, cost))
        if i != j:
            graph[j].append((i, cost))

#ダイクストラ法でstartからgoalまでの最短距離を求める

import heapq
distance = [float("inf")]*(n+2)
q = []
q.append((0, 0))
distance[0] = 0
while q:
    here, c = heapq.heappop(q)
    if distance[here] < c:
        continue
    for t, cost in graph[here]:
        if distance[here] + cost < distance[t]:
            distance[t] = distance[here] + cost
            heapq.heappush(q, (t, distance[t]))
            
print(distance[n+1])

### FIXED CODE ###

start_x, start_y, goal_x, goal_y = map(int, input().split())
n = int(input())
info = [(start_x, start_y, 0)] \
       + [tuple(map(int, input().split())) for i in range(n)] \
       + [(goal_x, goal_y, 0)]

#i番目のバリアからj番目のバリアまでの移動について、
#受ける光線量を辺の重みとしてグラフを構築する(O(N^2))
graph = [[0]*(n+2) for i in range(n+2)]
for i in range(n+2):
    for j in range(i,n+2):
        diff_x = info[i][0] - info[j][0]
        diff_y = info[i][1] - info[j][1]
        sum_radius = info[i][2] + info[j][2]
        cost = max(0, ((diff_x)**2 + (diff_y)**2)**(0.5) - sum_radius)
        graph[i][j] = cost
        graph[j][i] = cost
        graph = tuple(graph)

#ダイクストラ法でstartからgoalまでの最短距離を求める

import heapq
distance = [float("inf")]*(n+2)
used = [False]*(n+2)
distance[0] = 0

while True:
    v = -1
    for u in range(n+2):
        if not used[u] and (v == -1 or distance[u] < distance[v]):
            v = u
    if v == -1:
        break
    used[v] = True
    for u in range(n+2):
        distance[u] = min(distance[u], distance[v] + graph[v][u])
            
print(distance[n+1])
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
e=[]
for j in range(n-1):
    if s[j:j+2]=="AC":
        e.append(1)
    else :
        e.append(0)

for i in range(q):
    l,r=map(int,input().split())
    print(sum(e[l-1:r-1]))


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
t=[0]*(n+1)
for i in range(n):
    t[i+1]=t[i]+(1 if s[i:i+2]=="AC" else 0)

for i in range(q):
    l,r=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N = int(input())
abc = [[int(j) for j in input().split()] for _ in range(N-1)]
Q,K = map(int, input().split())
xy = [ [int(j) for j in input().split()] for _ in range(Q)]

inf = float("inf")
con = [ [] for _ in range(N+1)]
cost = [ [inf] * (N+1) for _ in range(N+1)]

for i in range(N-1):
    a,b,c = abc[i]
    con[a].append(b)
    con[b].append(a)
    cost[a][b] = c
    cost[b][a] = c

def dfs(a,b, par):
    if cost[a][b] != inf :
        return cost[a][b]

    if len(list(filter(lambda x: x!=par, con[a]))) == 0:
        return inf

    cst = inf
    idx= -1
    for e,ch in enumerate(con[a]):
        if ch == par:
            continue
        if cst > cost[a][ch] + dfs(ch,b,a):
            cst = cost[a][ch] + dfs(ch,b,a)
            
            idx = e
    if idx != -1:
        cost[a][b] = cst
    return cst

for i in range(Q):
    x,y = xy[i]
    _ = dfs(K,x,None)
    _ = dfs(y,K, None)
    print(dfs(x,K,None) + dfs(K,y,None))
    


### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
abc = [[int(j) for j in input().split()] for _ in range(N-1)]
Q,K = map(int, input().split())
xy = [ [int(j) for j in input().split()] for _ in range(Q)]

inf = float("inf")
con = [ [] for _ in range(N+1)]
# cost = [ [inf] * (N+1) for _ in range(N+1)]
# cost = {}
from collections import defaultdict
# cost =  defaultdict(  )

for i in range(N-1):
    a,b,c = abc[i]
    con[a].append((b, c))
    con[b].append((a, c))

q = [(K,0)]
visited = [False] * (N+1)
visited[K] = True
costmap = [inf] * (N+1)
costmap[K] = 0
while q:
    n,cst = q.pop()
    for ch,chcst in con[n]:
        if visited[ch]:
            continue
        q.append( (ch, cst+chcst))
        visited[ch] = True
        costmap[ch]  = cst+ chcst
    
# def dfs(a,b, par):
#     if cost[a][b] != inf :
#         return cost[a][b]
# 
#     if len(list(filter(lambda x: x!=par, con[a]))) == 0:
#         return inf
# 
#     cst = inf
#     idx= -1
#     for e,ch in enumerate(con[a]):
#         if ch == par:
#             continue
#         if cst > cost[a][ch] + dfs(ch,b,a):
#             cst = cost[a][ch] + dfs(ch,b,a)
#             
#             idx = e
#     if idx != -1:
#         cost[a][b] = cst
#         cost[b][a] = cst
#     return cst
# 
for i in range(Q):
    x,y = xy[i]
    print( costmap[x] + costmap[y])
# for i in range(Q):
#     x,y = xy[i]
#     # _ = dfs(K,x,None)
#     # _ = dfs(y,K, None)
#     print(dfs(x,K,None) + dfs(K,y,None))
### BUGGY CODE ###

A, B, K = map(int, input().split())

for i in range(A, B+1):
    if i < A+K or i > B-K:
        print(i)


### FIXED CODE ###

A, B, K = map(int, input().split())
ret = set(range(A, min(A + K, B)))
ret.update(range(max(A, B - K + 1), B + 1))

for r in sorted(ret):
    print(r)
### BUGGY CODE ###

N=int(input())
S=input()
ans=0
for i in range(1000):
    one=str(i//100)
    two=str((i%100)//10)
    three=str(i%10)
    f1,f2,f3=False,False,False
    ptr=0
    for j in range(ptr,N-2):
        if S[j]==one:
            f1=True
            ptr=j+1
            break
    if f1:
        for j in range(ptr,N-1):
            if S[j]==two:
                f2=True
                ptr=j+1
                break
        if f2:
            for j in range(ptr,N):
                if S[j]==three:
                    f3=True
                    ans+=1
                    break
print(ans)

### FIXED CODE ###

N=int(input())
S=input()
ans=0
for i in range(1000):
    one=str(i//100)
    two=str((i%100)//10)
    three=str(i%10)
    f1,f2,f3=False,False,False
    ptr=0
    for j in range(ptr,N-2):
        if S[j]==one:
            f1=True
            ptr=j+1
            break
    if f1:
        for j in range(ptr,N-1):
            if S[j]==two:
                f2=True
                ptr=j+1
                break
        if f2:
            for j in range(ptr,N):
                if S[j]==three:
                    f3=True
                    ans+=1
                    break
print(ans)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
A = [list(map(int, input().split())) for _ in range(q)]
for l,r in A:
    print(s[l-1:r].count("AC"))


### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
a=[0]*N
for i in range(N-1):
  a[i+1]=a[i]+(1 if S[i:i+2]=="AC" else 0)
for i in range(Q):
  l,r=map(int,input().split())
  print(a[r-1]-a[l-1])
### BUGGY CODE ###

n,*a=map(int,open(0).read().split())

for i in range(n):
    temp=a[i]
    b=sorted(a)[::-1]
    if temp!=b[0]:
        print(b[0])
    else:
        print(b[1])


### FIXED CODE ###

n,*a=map(int,open(0).read().split())

b=sorted(a)[::-1]
for i in range(n):
    if a[i]!=b[0]:
        print(b[0])
    else:
        print(b[1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**8)
input=sys.stdin.readline
n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
flag=[[[0]*(n+1) for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if flag[n1][n2][n3]:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0
    flag[n1][n2][n3]=1
    ret=1/(1-(n-n1-n2-n3)/n)
    if n1>0:
        ret+=f(n1-1,n2,n3)*(n1/n)/(1-(n-n1-n2-n3)/n)
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*(n2/n)/(1-(n-n1-n2-n3)/n)
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*(n3/n)/(1-(n-n1-n2-n3)/n)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
num1,num2,num3=0,0,0
for i in range(n):
    if a[i]==1:
        num1+=1
    elif a[i]==2:
        num2+=1
    else:
        num3+=1
dp=[[[-1.0 for k in range(n+1)] for i in range(n+1)] for j in range(n+1)]
def f(n1,n2,n3):
    if dp[n1][n2][n3]>=0.0:
        return dp[n1][n2][n3]
    if n1==n2==n3==0:
        return 0.0
    ret=n
    if n1>0:
        ret+=f(n1-1,n2,n3)*n1
    if n2>0:
        ret+=f(n1+1,n2-1,n3)*n2
    if n3>0:
        ret+=f(n1,n2+1,n3-1)*n3
    ret*=1.0/(n1+n2+n3)
    dp[n1][n2][n3]=ret
    return dp[n1][n2][n3]
print(f(num1,num2,num3))
### BUGGY CODE ###

H,W = map(int,input().split())   
queue = []
cost = [[-1]*W for i in range(H)]
for i in range(H):
  s = input()
  for j in range(W):
    if s[j] == '#':
      queue.append([i,j])
      cost[i][j] = 0
while queue:
  i,j = queue.pop(0)
  if i+1 < H and cost[i+1][j] < 0:
    queue.append([i+1,j])
    cost[i+1][j] = cost[i][j] + 1
  if i-1 >= 0 and cost[i-1][j] < 0:
    queue.append([i-1,j])
    cost[i-1][j] = cost[i][j] + 1
  if j+1 < W and cost[i][j+1] < 0:
    queue.append([i,j+1])
    cost[i][j+1] = cost[i][j] + 1
  if j-1 >= 0 and cost[i][j-1] < 0:
    queue.append([i,j-1])
    cost[i][j-1] = cost[i][j] + 1
flat = []
for i in range(H):
  flat.extend(cost[i])
print(max(flat))

### FIXED CODE ###

from collections import deque

H,W = map(int,input().split()) 
A = [[0]*W for _ in range(H)]
M = 0
queue = deque()
for i in range(H):
  s = input()
  for j in range(W):
    if s[j]== '#':
      queue.append([i,j,0])
      A[i][j] = '#'
while queue:
  i,j,cost = queue.popleft()
  M=max(M,cost)
  if i+1 < H and A[i+1][j] != '#':
    queue.append([i+1,j,cost+1])
    A[i+1][j] = '#'
  if i-1 >= 0 and A[i-1][j] != '#':
    queue.append([i-1,j,cost+1])
    A[i-1][j] = '#'
  if j+1 < W and A[i][j+1] != '#':
    queue.append([i,j+1,cost+1])
    A[i][j+1] = '#'
  if j-1 >= 0 and A[i][j-1] != '#':
    queue.append([i,j-1,cost+1])
    A[i][j-1] = '#'
print(M)
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()
    q = int(input())
    k = list(map(int, input().split()))
    for ki in k:
        D=M=DM=C=0
        for i, c in enumerate(s):
            if c == "D":
                D += 1
            elif c == "M":
                M += 1
                DM += D
            if i >= ki:
                j = i-ki
                if s[j] == "D":
                    D -= 1
                    DM -= M
                elif s[j] == "M":
                    M -= 1
            if c == "C":
                C += DM
        print(C)

if __name__ == "__main__":
    main()

### FIXED CODE ###

# コピペ https://atcoder.jp/contests/dwacon5th-prelims/submissions/7670569
# 自分の https://atcoder.jp/contests/dwacon5th-prelims/submissions/7822126
# とほぼ変わらないのに自分のものはTLEするので検証
n=int(input())
s=input()
q=int(input())
for i in list(map(int,input().split())):
    a=0
    v=[0,0,0]
    for j in range(n):
        if s[j]=="D":
            v[0]+=1
        elif s[j]=="M":
            v[1]+=1
            v[2]+=v[0]
        if j>=i:
            if s[j-i]=="D":
                v[0]-=1
                v[2]-=v[1]
            elif s[j-i]=="M":
                v[1]-=1
        if s[j]=="C":
            a+=v[2]
    print(a)
### BUGGY CODE ###

import math


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

A.sort()

frac = []

for k in range(A[-1]+1):
    if k == 0:
        frac.append(1)
    else:
        frac.append(frac[-1] * (k+1))

R = 0
M = []

if len(A) == 2:
    print(A[1], A[0])
else:
    for i in range(n):
        a = A[n-1-i]
        k = a / 2
        B = []
        C = []
        frac_a = frac[a]
        if R > frac_a // (frac[a-math.ceil(a/2)] ** 2):
            break
        for j in range(n):
            if A[j] < k:
                B.append(A[j])
            else:
                C.append(A[j])
                break
        b = B[-1]
        c = C[0]
        r_b = frac_a // (frac[a-b] * frac[b])
        r_c = frac_a // (frac[a-c] * frac[c])
        if r_b >= r_c and r_b > R:
            M = [a, b]
            R = r_b
        elif r_c >= r_b and r_c > R:
            M = [a, c]
            R = r_c

    print(M[0], M[1])


### FIXED CODE ###

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

A.sort()

if len(A) == 2:
    print(A[1], A[0])
else:
    a = A[-1]
    k = a / 2
    B = [a for a in A if a <  k]
    C = [a for a in A if a >= k]

    if k - B[-1] > C[0] - k:
        print(a, C[0])
    else:
        print(a, B[-1])
### BUGGY CODE ###

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

for B, C in BC:
  B -= 1
  while A[B] > C and B >= 0:
    B -= 1
  if B == 0:
    A = [C] + A[1:]
  else:
    A = [C]*len(A[:B+1]) + A[B+1:]
  A.sort()
print(sum(A))

### FIXED CODE ###

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

for B, C in BC:
  A.extend([C]*B)
  if len(A) > N*2:
    break
A.sort(reverse = True)
print(sum(A[:N]))
### BUGGY CODE ###

from collections import deque

n = int(input())

a = list(map(int, input().split()))
a.sort()
a = deque(a)

ans = []
double = []

s = 0
while len(a) > 0:
    ans.append(a.popleft())
    if len(a) > 0 and ans[s] == a[0]:
        double.append(ans[s])
    a = deque([i for i in a if i % ans[s] != 0])
    s += 1

for k in double:
    if k in ans:
        ans.remove(k)
print(len(ans))


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
a.sort()

b = [True for i in range(a[-1]+1)]

ans = 0

for i, j in enumerate(a):
    if b[j]:
        t = 1
        while j*t < len(b):
            b[j*t] = False
            t += 1
        
        if i == n-1:
            ans += 1
        elif j != a[i+1]:
            ans += 1
        
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

import heapq

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input()+'#') for _ in range(h)]+[['#']*(w+2)]
costs=[[10**18]*(w+1) for _ in range(h+1)]
costs[sy][sx]=0
q=[]
heapq.heappush(q,(0,sy,sx))
while len(q)!=0:
  cost,y,x=heapq.heappop(q)
  for dy,dx in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and costs[y+dy][x+dx]>costs[y][x]:
      costs[y+dy][x+dx]=costs[y][x]
      heapq.heappush(q,(cost,y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dy==0 and dx==0:
        continue
      if 1<=y+dy<=h and 1<=x+dx<=w and board[y+dy][x+dx]=='.' and costs[y+dy][x+dx]>costs[y][x]+1:
        costs[y+dy][x+dx]=costs[y][x]+1
        heapq.heappush(q,(cost+1,y+dy,x+dx))
if costs[gy][gx]==10**18:
  print(-1)
else:
  print(costs[gy][gx])

### FIXED CODE ###

#!/usr/bin/env python3

import collections
import sys
input=sys.stdin.readline

h,w=map(int,input().split())
sy,sx=map(int,input().split())
gy,gx=map(int,input().split())
board=[['#']*(w+2)]+[list('#'+input().replace('\n','')+'#') for _ in range(h)]+[['#']*(w+2)]
scores=[[10**18]*(w+2) for _ in range(h+2)]
scores[sy][sx]=0
q=collections.deque()
q.append((sy,sx))
count=0
while len(q)!=0:
  y,x=q.popleft()
  for dx,dy in [[-1,0],[1,0],[0,-1],[0,1]]:
    if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]:
      scores[y+dy][x+dx]=scores[y][x]
      q.appendleft((y+dy,x+dx))
  for dy in range(-2,3):
    for dx in range(-2,3):
      if dx==0 and dy==0:
        continue
      if 1<=x+dx<=w and 1<=y+dy<=h and board[y+dy][x+dx]!='#' and scores[y+dy][x+dx]>scores[y][x]+1:
        scores[y+dy][x+dx]=scores[y][x]+1
        q.append((y+dy,x+dx))
if scores[gy][gx]==10**18:
    print(-1)
else:
    print(scores[gy][gx])
### BUGGY CODE ###

def main():
    n,k = map(int, input().split())
    a = list(map(int, input().split()))

    a = [i for i in a if i <k]
    a.sort()
    n = len(a)

    DP1 = [[False]*(k+1)]
    DP1[0][0] = True
    DP2 = [[False]*(k+1)]
    DP2[0][0] = True
    b = a[::-1]

    for i in range(n):
        DP1.append(DP1[i][:])
        DP2.append(DP2[i][:])
        for j in range(k+1):
            if DP1[i][j] and a[i]+j <= k:
                DP1[i+1][a[i]+j] = True
            if DP2[i][j] and b[i]+j <= k:
                DP2[i+1][b[i]+j] = True

    for i in range(n+1):
        q = [0]
        for j in range(k+1):
            q.append(q[-1]+int(DP2[i][j]))
        DP2[i] = q

    ans = 0
    for i in range(n):
        use = False
        for j in range(k+1):
            if not DP1[i][j]:
                continue
            left = max(0, k-a[i]-j)
            right = k-j
            if DP2[n-i-1][right] - DP2[n-i-1][left]:
                use = True
                break
        if not use:
            ans += 1

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import numpy as np

def main():
    def check(m):
        DP = np.full(k+1, False)
        DP[0] = True
        for i in range(n):
            if i == m:
                continue
            DP[a[i]:] = np.logical_or(DP[a[i]:], DP[:k+1-a[i]])
        return any(DP[i] for i in range(k-a[m], k))

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

    a = [i for i in a if i <k]
    a.sort()
    n = len(a)

    left = -1
    right = n

    while right-left > 1:
        mid = (right+left)//2
        if check(mid):
            right = mid
        else:
            left = mid

    print(right)

main()
### BUGGY CODE ###

def main(A,B,N):
    A=sorted(A)
    B=sorted(B)[::-1]
    K=len(B)
    R=min(N,K)
    for i in range(R):
        if A[i]>B[i]:
            return sum(B[:i]+A[i:])
    return sum(B[:R]+A[R:])

N,M=map(int,input().split())
A=list(map(int,input().split()))
B=[]
for m in range(M):
    b,c=map(int,input().split())
    B+=[c]*b

print(main(A,B,N))

### FIXED CODE ###

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

BC=[]
for m in range(M):
    b,c=map(int,input().split())
    BC.append([b,c])

A.sort()
BC.sort(key=lambda x:x[1],reverse=True)

D=[]
for [b,c] in BC:
    D+=[c]*b
    if len(D)>N:
        break

if len(D)<N:
    D+=[0]*(N-len(D))

AD=[max(A[i],D[i]) for i in range(N)]
 
print(sum(AD))
### BUGGY CODE ###

import sys
import math
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
Yes = lambda boolean: print('Yes') if boolean else print('No')
YES = lambda boolean: print('YES') if boolean else print('NO')
aint = lambda: int(input())
ints = lambda: list(map(int, input().split()))
is_even = lambda x: True if x%2==0 else False
 
n = aint()
get = []
for i in range(n):
  s = input()
  if s not in get:
    get.append(s)
print(len(get))

### FIXED CODE ###

import sys
import math
from collections import deque
input = lambda: sys.stdin.readline().rstrip()
Yes = lambda boolean: print('Yes') if boolean else print('No')
YES = lambda boolean: print('YES') if boolean else print('NO')
aint = lambda: int(input())
ints = lambda: list(map(int, input().split()))
is_even = lambda x: True if x%2==0 else False

n = aint()
get = []
for i in range(n):
    s = input()
    get.append(s)
ss = set(get)
print(len(ss))
### BUGGY CODE ###

number = list(map(int,input().split()))
line = list(map(int,input().split()))
 
num = number[0]
K = number[1]
dp = [0, abs(line[1] - line[0])]
for i in range(2, num):
  line2 = []
  for k in range(1, min(i + 1 , K + 1)):
    a = dp[-k] + abs(line[i] - line[i - k])
    line2.append(a)
  dp += [min(line2)]
print(dp[-1])


### FIXED CODE ###

def ans():
    n, k, *h = map(int, open(0).read().split())
    dp = [float("inf")] * n
    dp[0] = 0
    for i in range(1, n):
        min_j = max(0, i-k)
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(min_j , i)])
    print(dp[n-1])
 
ans()
### BUGGY CODE ###

# import sys 
# input = sys.stdin.readline
 
 
n = int(input())
 
a= list(map(int,input().split())) 
 

if 0 in a:
    print(0)
    quit()
 
ans = 1
for i in a:
    ans *= i 
    
    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())) 
 
def main(a):
    if 0 in a:
        print(0)
        return
     
    ans = 1
    for i in a:
        ans *= i 
        
        if ans > 1000000000000000000:
            print(-1)
            return
    
    print(ans)
    
main(a)
### BUGGY CODE ###

def main():
    import math
    
    N = int(input())

    for n in range(1, N + 1):
        max_itr = min(101, int(math.sqrt(n)) + 1)
        ans = 0

        for x in range(1, max_itr):
            for y in range(1, max_itr):
                for z in range(1, max_itr):

                    # left_eq = x * x + y * y + z * z + x * y + y * z + z * x
                    left_eq=x**2+y**2+z**2+x*y+y*z+z*x
                    if (left_eq == n):
                        ans += 1
        
        
        print(ans)


if __name__ == '__main__':
    main()




### FIXED CODE ###

def main():
    import math

    N = int(input())
    
    ans_list = [0 for i in range(N)]
    
    for x in range(1, 101):
        for y in range(1, 101):
            for z in range(1, 101):

                left_eq = x * x + y * y + z * z + x * y + y * z + z * x
                if (left_eq <= N):
                    ans_list[left_eq - 1] += 1
    
    for i in range(N):
        print(ans_list[i])

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

n=int(input())
a=list(input().split())

for i in range(1,n+1):
    print(a.count(str(i)))

### FIXED CODE ###

n=int(input())
a=list(input().split())

l = [0 for _ in range(n+1)]
for i in a:
    l[int(i)]+=1

for j in range(1,n+1):
    print(l[j])
### BUGGY CODE ###

from itertools import combinations

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

total = 0
for pat in combinations(range(n), 2):
    total += a[pat[0]] ^ a[pat[1]]
print(total % (10**9 + 7))


### FIXED CODE ###

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

mod = 10**9 + 7

ans = 0
for i in range(61):
    zero = 0
    one = 0
    for ai in a:
        if ai>>i & 1:
            one += 1
        else:
            zero += 1
    ans += zero * one * 2**i
    ans %= mod

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

N,K = list(map(int,input().split()))
S = [int(i) for i in list(input())]
S.append(2)

S2 = []
cnt = 1
for i in range(N):
    if S[i] != S[i+1]:
        S2.append([S[i],cnt])
        cnt = 1
    else:
        cnt += 1

if S2[0][0] == 0:
    S2 = [[1,0]] + S2
if S2[-1][0] == 0:
    S2.append([1,0])    

S3 = [S2[0][1]]
K2 = min((len(S2)-1)//2,K)
for i in range(0,len(S2)-2*K2,2):
    SUM = 0
    for j in range(2*K2 + 1):
        SUM += S2[i+j][1]
    S3.append(SUM)
print(max(S3))

### FIXED CODE ###

N,K = list(map(int,input().split()))
S = [int(i) for i in list(input())]
S.append(2)

S2 = []
cnt = 1
for i in range(N):
    if S[i] != S[i+1]:
        S2.append([S[i],cnt])
        cnt = 1
    else:
        cnt += 1

if S2[0][0] == 0:
    S2 = [[1,0]] + S2
if S2[-1][0] == 0:
    S2.append([1,0])    
    
SUM = [0]
for i in range(len(S2)):
    SUM.append(SUM[i] + S2[i][1])
T = []
for i in range(0,max(1,len(SUM)//2-K),1):
    T.append(SUM[min(len(SUM)-1,2*(K+i)+1)]-SUM[2*i])
print(max(T))
### BUGGY CODE ###

N = input()
num = len(N)
mod_sum = [0]*2019
mod_sum[0] = 1
ans = 0
a = 0
for i in range(num):
  a += (int(N[-i-1])*10**i)%2019
  mod = a%2019
  mod_sum[mod] += 1
for i in mod_sum:
  ans += i*(i-1)//2
print(ans)

### FIXED CODE ###

N = input()
num = len(N)
mod_sum = [0]*2019
mod_sum[0] = 1
ans = 0
a = 0
d = 1
for i in range(num):
  a = (a + int(N[-i-1])*d)%2019
  d = (d*10)%2019
  mod_sum[a] += 1
for i in mod_sum:
  ans += i*(i-1)//2
print(ans)