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

import sys
sys.setrecursionlimit(1000000)
N=int(input())
A=list(map(int,input().split()))
def f(i):
  if i==0:
    return 1
  else:
    return f(i-1)*A[i-1]
a=f(N)
print(a if a<=10**(18) else -1)






### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
a=1
k=0
if 0 in A:
  print(0)
else:
  for i in range(N):
    a*=A[i]
    if a>10**(18):
      k=1
      break
  if k==1:
    print(-1)
  else:
    print(a)
### BUGGY CODE ###

import collections
import sys
input=sys.stdin.readline

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_all=[[] for _ in range(n+1)]
for i in range(n):
  val=arr[i]
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=0
  pos_all[val].append(i+1)
for i in range(n+1):
  pos_all[i].append(-1)
cnt=collections.Counter(arr)
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if cnt[val]!=1:
      bit.add(pos_all[val][pos_now[val]],-1)
      if pos_all[val][pos_now[val]+1]!=-1:
        pos_now[val]+=1
        bit.add(pos_all[val][pos_now[val]],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)

### FIXED CODE ###

import sys
input=sys.stdin.readline

class BIT:
  def __init__(self,n):
    self.n=n+1
    self.BIT=[0]*self.n
  def add(self,i,x):
    idx=i
    while idx<self.n:
      self.BIT[idx]+=x
      idx+=(idx&-idx)
  def _sum(self,i):
    ret=0
    idx=i
    while idx>0:
      ret+=self.BIT[idx]
      idx-=(idx&-idx)
    return ret
  def sum(self,l,r):
    return self._sum(r)-self._sum(l-1)
  def value(self,i):
    return self._sum(i)-self._sum(i-1)

n,q=map(int,input().split())
arr=list(map(int,input().split()))
query=[]
for i in range(q):
  l,r=map(int,input().split())
  query.append((l,r,i))
query=sorted(query,key=lambda x:x[0])
ans=[0]*q
bit=BIT(n)
pos_now=[-1]*(n+1)
pos_prev=[-1]*(n+1)
dic={}
for i in range(n):
  val=arr[i]
  dic[i+1]=-1
  if pos_now[val]==-1:
    bit.add(i+1,1)
    pos_now[val]=i+1
  if pos_prev[val]!=-1:
    dic[pos_prev[val]]=i+1
  pos_prev[val]=i+1
prev=1
for l,r,id in query:
  while prev<l:
    val=arr[prev-1]
    if dic[pos_now[val]]!=-1:
      pos_now[val]=dic[pos_now[val]]
      bit.add(pos_now[val],1)
    prev+=1
  ans[id]=bit.sum(l,r)
for val in ans:
  print(val)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**5)
S = list(input())
n = len(S)
def Remove(binList,lenList):
    for i in range(0,lenList-1):
        if (binList[i] == "0" and binList[i+1] == "1") or (binList[i] == "1" and binList[i+1] == "0"):
            del binList[i:i+2]
            return Remove(binList,lenList - 2)
    return binList
if n > 10**5:
    sys.exit()
S = Remove(S,n)
print(n-len(S))

### FIXED CODE ###

S = list(input())
obj = min(S.count("0"),S.count("1"))
print(obj*2)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

import sys
#sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

from itertools import accumulate

n = int(input())
a = [int(i) for i in readline().split()]

res = [0]*(n+1)
for i in a: res[i] += 1

c = [0]
for i in res:
    if i > 0: c.append(i)
c.sort()#reverse=True)

l = len(c)-1
#print(c)

acc = list(accumulate(c))


memo = {}
def f(m,k):#最初のm個, kずつ
    if m == 0: return 0
    if m < k: return 0
#    if (m,k) in memo:
#        return memo[(m,k)]
    z = 0
    if acc[m]//k >= c[m]:
        return acc[m]//k
    else:
        return f(m-1,k-1)

for i in range(1,n+1):
    print(f(l,i))











### FIXED CODE ###

# coding: utf-8
# Your code here!
def f(m,k):#最初のm個, kずつ
    if m == 0: return 0
    if m < k: return 0
#    if (m,k) in memo:
#        return memo[(m,k)]
    z = 0
    if acc[m]//k >= c[m]:
        return acc[m]//k
    else:
        return f(m-1,k-1)


import sys
#sys.setrecursionlimit(10**6)
readline = sys.stdin.readline 

from itertools import accumulate

n = int(input())
a = [int(i) for i in readline().split()]

res = [0]*(n+1)
for i in a: res[i] += 1

c = [0]
for i in res:
    if i > 0: c.append(i)
c.sort()#reverse=True)

l = len(c)-1
#print(c)
acc = list(accumulate(c))

#print(acc,c)
res = [n]+[acc[m]//c[m] for m in range(1,l+1)]


#print(l,res)


m = l
for k in range(1,n+1):
    k -= l-m
    if res[m] >= k:
        print(acc[m]//k)
    else:
#        print(k,m)
        while res[m] < k:
            m -= 1
            k -= 1
        print(acc[m]//(k))
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
s = list(input())
q = int(input())
for _ in range(q):
  a,b,c = input().split()
  if a=='1':
    s[int(b)-1]=c
  else:
    print(len(set(s[int(b)-1:int(c)])))

### FIXED CODE ###

n=int(input())
l=list(input())
q=int(input())
bit=[[0]*(n+1) for i in range(26)]
def bit_sum(o,i):
  s=0
  while i:
    s+=bit[o][i]
    i-=i&-i
  return s
def bit_add(o,i,x):
  while i<=n:
    bit[o][i] += x
    i+=i&-i
for i in range(n):
  bit_add(ord(l[i])-97,i+1,1)
for i in range(q):
  a,b,c=input().split()
  b=int(b)-1
  if a=='1':
    bit_add(ord(l[b])-97,b+1,-1)
    l[b]=c
    bit_add(ord(c)-97,b+1,1)
  else:
    c=int(c)
    print(sum(1 for o in range(26) if bit_sum(o,c)-bit_sum(o,b)))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def solve():
    H, W = map(int, input().split())
    Ass = [tuple(map(int, input().split())) for _ in range(H)]
    Bss = [tuple(map(int, input().split())) for _ in range(H)]

    dp1 = [[set() for j in range(W)] for i in range(H)]
    dp2 = [[set() for j in range(W)] for i in range(H)]

    dist = H+W-3
    d1, d2 = (dist+1)//2, dist//2
#    print('d1:', d1, '/ d2:', d2)

    A, B = Ass[0][0], Bss[0][0]
    dp1[0][0] = set([abs(A-B)])
    for d in range(d1):
#        print('d:', d)
        for i in range(d+1):
            j = d-i
#            print((i, j))
            if 0 <= i+1 <= H-1 and 0 <= j <= W-1:
                A, B = Ass[i+1][j], Bss[i+1][j]
                for diff in dp1[i][j]:
                    dp1[i+1][j].add(abs(diff+A-B))
                    dp1[i+1][j].add(abs(diff+B-A))
            if 0 <= i <= H-1 and 0 <= j+1 <= W-1:
                A, B = Ass[i][j+1], Bss[i][j+1]
                for diff in dp1[i][j]:
                    dp1[i][j+1].add(abs(diff+A-B))
                    dp1[i][j+1].add(abs(diff+B-A))
#    for dpi in dp1:
#        print(dpi)
#    print()

    A, B = Ass[-1][-1], Bss[-1][-1]
    dp2[-1][-1] = set([abs(A-B)])
    for d in range(d2):
        for i0 in range(d+1):
            j0 = d-i0
            i, j = H-1-i0, W-1-j0
            if 0 <= i-1 <= H-1 and 0 <= j <= W-1:
                A, B = Ass[i-1][j], Bss[i-1][j]
                for diff in dp2[i][j]:
                    dp2[i-1][j].add(abs(diff+A-B))
                    dp2[i-1][j].add(abs(diff+B-A))
            if 0 <= i <= H-1 and 0 <= j-1 <= W-1:
                A, B = Ass[i][j-1], Bss[i][j-1]
                for diff in dp2[i][j]:
                    dp2[i][j-1].add(abs(diff+A-B))
                    dp2[i][j-1].add(abs(diff+B-A))
#    for dpi in dp2:
#        print(dpi)
#    print()

    ans = float('inf')
    d = d1
    for i in range(d+1):
        j = d-i
        if 0 <= i+1 <= H-1 and 0 <= j <= W-1:
            for diff1 in dp1[i][j]:
                for diff2 in dp2[i+1][j]:
                    diff = abs(diff1-diff2)
                    ans = min(ans, diff)
        if 0 <= i <= H-1 and 0 <= j+1 <= W-1:
            for diff1 in dp1[i][j]:
                for diff2 in dp2[i][j+1]:
                    diff = abs(diff1-diff2)
                    ans = min(ans, diff)

    print(ans)


solve()


### FIXED CODE ###

maxV = 80*(80+80)

H, W = map(int, input().split())
Ass = [tuple(map(int, input().split())) for _ in range(H)]
Bss = [tuple(map(int, input().split())) for _ in range(H)]

dp = [[0 for j in range(W)] for i in range(H)]

for i in range(H):
    for j in range(W):
        A, B = Ass[i][j], Bss[i][j]
        if A > B:
            A, B = B, A
        if i == 0 and j == 0:
            dp[i][j] = 1<<(maxV+B-A) | 1<<(maxV-B+A)
        if i > 0:
            dp[i][j] |= dp[i-1][j]<<(B-A) | dp[i-1][j]>>(B-A)
        if j > 0:
            dp[i][j] |= dp[i][j-1]<<(B-A) | dp[i][j-1]>>(B-A)

bitset = dp[-1][-1]
mask = 1<<(2*maxV)
ans = maxV
for i in range(-maxV, maxV+1):
    if bitset & mask:
        ans = min(ans, abs(i))
    mask >>= 1

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

import sys

sys.stdin.readline()
a = list(map(int, sys.stdin.readline().split()))

def largest_odd_idx(A):
    idx = -1
    max_a = 0
    for i, v in enumerate(A):
        if v % 2 == 0 and max_a < v:
            max_a = v
            idx = i
    return idx

cnt = 0
while True:
    idx = largest_odd_idx(a)
    if idx < 0:
        break
    for i in range(0, len(a)):
        if idx == i:
            a[i] //= 2
        elif a[i] * 3 > 1000000000:
            if a[i] % 2 == 0:
                a[i] //= 2
            else:
                break
        else:
            a[i] *= 3
    cnt += 1
print(cnt)

### FIXED CODE ###

import math
import sys

sys.stdin.readline()
a = list(map(int, sys.stdin.readline().split()))

a = [x for x in a if x % 2 == 0]

cnt = 0
for x in a:
    while x % 2 == 0:
        x //= 2
        cnt += 1

print(cnt)
### BUGGY CODE ###

n = int(input())

a = list(map(int,input().split()))
i = 0
c = 0
while(i < len(a)):
    if(a[i] == i+1):
        i += 1
    else:
        a.pop(i)
        c += 1

if(len(a) == 0):print(-1)
else:print(c)

### FIXED CODE ###

n = int(input())

a = list(map(int,input().split()))
i = 1
j = 1
c = 0
while(j <= n):
    if(a[j-1] == i):
        i += 1
    else:
        c += 1
    j += 1
if(c == n):print(-1)
else:print(c)
### BUGGY CODE ###

import sys

N = int(input())
task = []
time = 0

for i in range(1,N+1) :
    A, B =input().split()
    task.append((int(A) ,int(B)))
    work = sorted(task, key = lambda x:(x[1]))
for i in range(N) :
    time += work[i][0]
    if time > work[i][1] :
        print("No")
        sys.exit()

print("Yes")





### FIXED CODE ###

import sys

N = int(input())
tasks = sorted([list(map(int,input().split())) \
        for _ in range(N)],key = lambda x:(x[1]))
time = 0

for i in range(N) :
    time += tasks[i][0]
    if time > tasks[i][1] :
        print("No")
        sys.exit()

print("Yes")
### BUGGY CODE ###

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

    ans = 0
    temp = 0
    if N == 1:
        return 1

    if A[0] == 1 and A[1] != 1:
        return 1
    elif A[0] == 1 and A[1] == 1:
        return 0

    for i in range(N):
        if i == 0 and A[i+1] != A[i]:
            ans += 1
            continue

        temp = A[i]
#同じ数があるかどうか
        if i == N-1 and temp == A[i-1]:
            continue
        elif i != N-1:
            if temp == A[i+1] or temp == A[i-1]:
                continue

        for j in range(N):
            if A[j] == -1:
                continue
            elif A[j] <= temp/2 and A[i]%A[j] == 0:
                A[i] = -1
                break
            elif A[j] <= temp//2 and A[i]%A[j] != 0:
                continue
            elif A[j] > temp//2:
                ans += 1
                break
    return ans

print(main())


### FIXED CODE ###

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

    A.sort()
    dict = {}
    for i in range(1,A[N-1]+1):
        dict[i] = 0

    if N == 1:
        return 1

    if A[0] == 1 and A[1] != 1:
        return 1
    elif A[0] == 1 and A[1] == 1:
        return 0

    temp = 1

    for num in A:
        while True:
            if num*temp <= A[N-1]:
                dict[num*temp] += 1
                temp += 1
            else:
                temp = 1
                break

    ans = 0
    for num2 in A:
        if dict[num2] <= 1:
            ans += 1

    return ans


print(main())
### BUGGY CODE ###

s = input()
ls = len(s)
t = input()
lt = len(t)
td = dict()
for x in t:
  if x not in s:
    print(-1)
    exit(0)
for i in range(lt-1):
  if t[i] not in td:
    td[t[i]] = list()
  td[t[i]].append(t[i+1])
md = [dict() for _ in range(ls)]
cd = dict()
for i in range(ls-1,-1,-1):
  cd[s[i]] = i + ls
for i in range(ls-1,-1,-1):
  if s[i] not in td:
    cd[s[i]] = i
    continue
  for x in td[s[i]]:
    md[i][x] = cd[x]
  cd[s[i]] = i
ans = 0
cur = cd[t[0]]
for i in range(lt-1):
  cur = md[cur][t[i+1]]
  ans += (cur//ls)
  cur %= ls
print(1 + ans*ls+cur)


### FIXED CODE ###

def main():
  s = list(map(lambda x:ord(x)-97, list(input())))
  ls = len(s)
  ss = set(s)
  t = list(map(lambda x:ord(x)-97, list(input())))
  lt = len(t)
  st = set(t)
  td = [list() for _ in range(26)]
  if not st.issubset(ss):
    print(-1)
    exit()
  for i in range(lt-1):
    td[t[i]].append(t[i+1])
  md = [None for _ in range(ls)]
  cd = [0]*26
  for i in range(ls-1,-1,-1):
    cd[s[i]] = i + ls
  for i in range(ls-1,-1,-1):
    md[i] = cd.copy()
    cd[s[i]] = i
  ans = 0
  cur = cd[t[0]]
  for i in range(lt-1):
    cur = md[cur][t[i+1]]
    ans += (cur//ls)
    cur %= ls
  print(1 + ans*ls+cur)

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

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

for i in range (len(p)):
    p[i]=int(p[i])


sums=0
maxi=0

for i in range(0,n-k+1):
    sums=0
    for j in range(i,i+k):
        sums=sums+p[j]
        if sums>=maxi:
            maxi=sums
    
print((maxi+k)/2)


### FIXED CODE ###

n, k = list (map (int, input ().split ()))
p = [0] + list (map (int, input ().split ()))
s = [0 for i in range (n + 1)]
mx = 0
tag = 0
f = [0.0 for i in range (n + 1)]
for i in range (1, n + 1) :
    s[i] = s[i - 1] + (p[i] + 1) * p[i] / 2 / p[i]
    if (i >= k and s[i] - s[i - k] > mx) :
        mx = s[i] - s[i - k]
print (mx)
### BUGGY CODE ###

import collections
N=int(input())
A=list(map(int, input().split()))
A_dict=collections.Counter(A)
ANS=1
for i in A_dict.keys():
    ANS=ANS*i**A_dict[i]

if ANS>10**18:
    print(-1)
else:
    print(ANS)

### FIXED CODE ###

import collections
import sys

N=int(input())
A=list(map(int, input().split()))
A_dict=collections.Counter(A)
ANS=1
if 0 in A_dict.keys():
    print("0")
    sys.exit()
    
for key, value in A_dict.items():
    ANS=ANS*(key**value)
    if ANS>10**18:
        print(-1)
        sys.exit()

print(ANS)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(4100000)


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


def solve(inputs):
    [N] = string_to_int(inputs[0])
    count = 0
    for x in range(1, N):
        count += x
    return count


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


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


### FIXED 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 solve(inputs):
    [N] = string_to_int(inputs[0])
    num = N - 1
    if num == 0:
        return 0
    if num == 1:
        return 1
    if num % 2 == 0:
        # half_l = math.floor(num / 2)
        # half = (half_l + half_l + 1) / 2
        half = num // 2
        append = num // 2
    else:
        half = (num + 1) // 2
        append = 0
        # half = math.floor(num / 2)
    return half * num + append


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


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

from collections import Counter
n = int(input())

A = [Counter(input()) for _ in range(n)]

ans = 0
for i in range(n-1):
    for j in range(i+1, n):
        if A[i] == A[j]:
            ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter
n = int(input())

A = ["".join(sorted(input())) for _ in range(n)]
c = Counter(A)

ans = sum(x * (x-1) // 2 for x in c.values())
print(ans)
### BUGGY CODE ###

import sys
from math import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

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

N = INT()
A = LIST()

is_pc = 1
l = 1
for a in A:
    g = gcd(l, a)
    if g != 1:
        is_pc = 0
        break
    l = lcm(l, a)

is_sc = 1
g = 0
for a in A:
    g = gcd(g, a)
if g != 1:
    is_sc = 0

if is_pc:
    print('pairwise coprime')
elif is_sc:
    print('setwise coprime')
else:
    print('not coprime')


### FIXED CODE ###

import sys
from math import gcd

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

def factorize(num: int) -> dict:
    """ 素因数分解 """
    from math import sqrt
    from collections import Counter

    d = Counter()
    for i in range(2, int(sqrt(num))+1):
        while num % i == 0:
            num //= i
            d[i] += 1
        if num == 1:
            break
    if num != 1:
        d[num] += 1
    return d

N = INT()
A = LIST()

def check(se, fact):
    for k in fact:
        if k not in se:
            se.add(k)
        else:
            return False
    return True

is_pc = 1
se = set()
for a in A:
    fact = factorize(a)
    if not check(se, fact):
        is_pc = 0
        break

is_sc = 1
g = 0
for a in A:
    g = gcd(g, a)
if g != 1:
    is_sc = 0

if is_pc:
    print('pairwise coprime')
elif is_sc:
    print('setwise coprime')
else:
    print('not coprime')
### BUGGY CODE ###

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

P = [K for _ in range(N)]
D = []
for _ in range(Q):
    A = int(input()) - 1
    for i, p in enumerate(P):
        if A != i:
            P[i] -= 1

for x in P:
    if x <= 0:
        print('No')
    else:
        print('Yes')


### FIXED CODE ###

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

P = [K for _ in range(N)]
D = []
for _ in range(Q):
    A = int(input()) - 1
    P[A] += 1

for x in P:
    if Q + 1 <= x:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

n,k = map(int,input().split())
line = list(input().split())
setted_line = list(set(line))
origin_num = len(setted_line) 
pairs = {}
for i in range(len(setted_line)):
  count = line.count(setted_line[i])
  pairs[setted_line[i]] = count
sorted_pairs = sorted(pairs.items(), key = lambda x:x[1])
answer = 0
if origin_num <= k:
  answer = 0
else:
  gap = origin_num - k 
  for j in range(gap):
    answer += sorted_pairs[j][1]
print(answer)

### FIXED CODE ###

import collections
n,k = map(int,input().split())
line = list(input().split())
c = collections.Counter(line)
answer = 0
if k > len(c):
  answer = 0
else:
  gap = len(c) - k
  sorted_c = list(sorted(c.items(),key = lambda x:x[1]))
  for i in range(gap):
    answer += int(sorted_c[i][1])
print(answer)
### BUGGY CODE ###

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

for i in range(K):
    if A >= 1:
        A -= 1
    elif B >= 1:
        B -= 1

print(A, B)

### FIXED CODE ###

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

A -= K
if A < 0:
    K = abs(A)
    A = 0
else:
    K = 0

B -= K
if B < 0:
    B = 0

print(A, B)
### BUGGY CODE ###

N,M,L = map(int, input().split())
RL=[list(map(int, input().split())) for _ in range(M)]
Q=int(input())
QL=[list(map(int, input().split())) for _ in range(Q)]
inf=float('inf')
fuel=[[inf]*N for _ in range(N)]
dist=[[inf]*N for _ in range(N)]
for i in range(N):
    fuel[i][i]=0
for I in RL:
    fuel[I[0]-1][I[1]-1]=fuel[I[1]-1][I[0]-1]=I[2]
for k in range(N):
    for i in range(N):
        for j in range(N):
            fuel[i][j]=min(fuel[i][j],fuel[i][k]+fuel[k][j])
for i in range(N):
    for j in range(N):
        if fuel[i][j] <= L:
            dist[i][j]=1
for i in range(N):
    dist[i][i]=0
for k in range(N):
    for i in range(N):
        for j in range(N):
            dist[i][j]=min(dist[i][j], dist[i][k]+dist[k][j])
for i in range(Q):
    print(dist[QL[i][0]-1][QL[i][1]-1]-1 if dist[QL[i][0]-1][QL[i][1]-1] != inf else -1)


### FIXED CODE ###

def w(d):
    n=len(d)
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j]=min(d[i][j],d[i][k]+d[k][j])
    return d
N,M,L = map(int, input().split())
inf=float('inf')
fuel=[[inf]*N for _ in range(N)]
for i in range(N):
    fuel[i][i]=0
for _ in range(M):
    a,b,c=map(int,input().split())
    fuel[a-1][b-1]=fuel[b-1][a-1]=c
Q=int(input())
ST=[list(map(int, input().split())) for _ in range(Q)]
fuel = w(fuel)
for i in range(N):
    for j in range(N):
        if 0 < fuel[i][j] <= L:
            fuel[i][j]=1
        elif fuel[i][j] != 0:
            fuel[i][j] = inf
fuel = w(fuel)
for st in ST:
    print(fuel[st[0]-1][st[1]-1]-1 if fuel[st[0]-1][st[1]-1] != inf else -1)
### BUGGY CODE ###

k,s=map(int,input().split())
ans=0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i+j+l==s:
                ans+=1
print(ans)

### FIXED CODE ###

k, s = (int(x) for x in input().split())
 
count = 0
for x in range(k+1):
    for y in range(k+1):
        z = s-x-y
        if 0 <= z <= k:
            count += 1
print(count)
### BUGGY CODE ###

def comb(n,r,mod):
  a=1
  b=1
  r = min(r,n-r)
  for i in range(r):
    a = a*(n-i)%mod
    b = b*(i+1)%mod
  return a*pow(b,mod-2,mod)%mod

n = int(input())
a = list(map(int,input().split()))
mod = 10**9 + 7

a = sorted(a,reverse = True)
ans = 0
j = 0

for i in range(1,n):
  c = comb(a[0],a[i],mod)
  ans = max(ans,c)
  if ans == c:
    j = i
print(a[0],a[j])

### FIXED CODE ###

from bisect import *
n = int(input())
a = list(map(int,input().split()))
a = sorted(a)
ans = a[-1]//2
b = bisect_left(a,ans)
if a == [0,100]:
  print(100,0)
  exit()
if abs(ans-a[b]) <= abs(ans-a[b-1]):
  print(a[-1],a[b])
else:
  print(a[-1],a[b-1])
### BUGGY CODE ###

INF = 10 ** 9 + 7

S = input()

dp = [[0] * 13 for _ in range(len(S)+1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i+1)]
    if x == '?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(mul*k+j) % 13] += dp[i][j]
                dp[i+1][(mul*k+j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i+1][(mul*k+j) % 13] += dp[i][j]
            dp[i+1][(mul*k+j) % 13] %= INF
    mul = mul * 10 % 13

print(dp[len(S)][5])

### FIXED CODE ###

INF = 10 ** 9 + 7

S = input()

dp = [[0] * 13 for _ in range(len(S)+1)]
dp[0][0] = 1
mul = 1

for i in range(len(S)):
    x = S[-(i+1)]
    if x == '?':
        for k in range(10):
            for j in range(13):
                dp[i+1][(mul*k+j) % 13] += dp[i][j]
                dp[i+1][(mul*k+j) % 13] %= INF
    else:
        k = int(x)
        for j in range(13):
            dp[i+1][(mul*k+j) % 13] += dp[i][j]
            dp[i+1][(mul*k+j) % 13] %= INF
    mul = mul * 10 % 13

print(dp[len(S)][5])