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

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

n = INT()
a = LIST()
ans = 1
flag = 0 in a
for i in a:
    ans *= i
    if ans > 10 ** 18 and not flag:
        print(-1)
        exit()
print(ans)

### FIXED CODE ###

import sys, re, os
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, acos, atan, asin, log, log10, gcd
from itertools import permutations, combinations, product, accumulate, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
#from fractions import gcd
def debug(*args):
    if debugmode:
        print(*args)
def input(): return sys.stdin.readline().strip()
def STR(): return input()
def INT(): return int(input())
def FLOAT(): return float(input())
def MAP(): return map(int, input().split())
def S_MAP(): return map(str, input().split())
def LIST(): return list(map(int, input().split()))
def S_LIST(): return list(map(str, input().split()))
def lcm(a, b): return a * b // gcd(a, b)
sys.setrecursionlimit(10 ** 9)
inf = sys.maxsize
mod = 10 ** 9 + 7
dx = [0, 1, 0, -1, 1, -1, -1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
debugmode = True

t = 10 ** 18

n = INT()
a = LIST()
ans = 1
a.sort(reverse=True)
if a[-1] == 0:
    print(0)
    exit()
for i in a:
    ans *= i
    if ans > t:
        print(-1)
        exit()
print(ans)
### BUGGY CODE ###


n = int(input())
A= [int(c) for c in input().strip().split(' ')]
# s = input().strip()
A = sorted(A)
i,j,k=0,1,2
cnt =0
# print(A)
for i in range(n):
    for j in range(i+1,n):
         for k in range(j+1,n):
             if A[k] < A[j]+A[i]:
                 cnt+=1
print(cnt)

### FIXED CODE ###


n = int(input())
A= [int(c) for c in input().strip().split(' ')]
# s = input().strip()
A = sorted(A)
cnt =0
for i in range(n-1,1,-1):
    l,r=0,i-1

    while(l<r):
        # print(l,r,i)
        if(A[l]+A[r]>A[i]):
            cnt+=r-l
            r-=1
        else:
            l+=1
print(cnt)
### BUGGY CODE ###

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def get_rank(L):
    D = {x:i for i,x in enumerate(sorted(L))}
    return [D[x] for x in L]
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<28, 1<<28, N*(N-1)//4+1, N*(N-1)//4+1
    f = 1
    while (r - l) / max(abs(l), 1) > 0.000000001:
        m = (l+r) / 2 if f else (l * rc + r * lc) / (lc + rc)
        A = [b for a, b in sorted([(s*m+t, i) for i, (s, t) in enumerate(Z)])]
        A = get_rank([s*m+t for s, t in Z])
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = (c - N*(N-1)//4) * 2
        else:
            r = m
            rc = (N*(N-1)//4 - c) * 2 + 1
        f ^= 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))

### FIXED CODE ###

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<28, 1<<28, N*(N-1)//4+1, N*(N-1)//4+1
    f = 1
    while (r - l) / max(abs(l), 1) > 0.000000001:
        m = (l+r) / 2 if f else (l * rc + r * lc) / (lc + rc)
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**40)<<16)+i for i, (s, t) in enumerate(Z)])]
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = (c - N*(N-1)//4) * 2
        else:
            r = m
            rc = (N*(N-1)//4 - c) * 2 + 1
        f ^= 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))
### BUGGY CODE ###

N = int(input())
A = []
for i in range(N):
    A.append( [ int(n) for n in input().split() ] )

day = 0
while(True):
    day += 1
    v = list(range(N))
    # その日まだ試合していない人のリスト
    for p in range(N):
        if len(A[p]) == 0:
            continue
        q = A[p][0]-1
        if p in v  and  q in v  and  A[q][0]-1 == p:
            #print(day, p, q, v, A)
            v.remove(p)
            v.remove(q)
            del A[p][0]
            del A[q][0]
        
    flag = 0
    for i in range(N):
        if len(A[i]) > 0:
            flag = 1
    if flag == 0:
        print(day)
        break
        
    if len(v) == N:
        print(-1)
        break

### FIXED CODE ###

# match of  a vs b
def match(a, b):
    """
    :type a: int
    :type b: int
    :rtype: int
    """
    return min(a,b) + N * max(a,b)

N = int(input())
A = []
for i in range(N):
    A.append( [ int(n)-1 for n in input().split() ] )

# NEXT[ match(a,b) ]  must be held after  match(a,b)
NEXT = [ [] for i in range(N*N) ]
# How many matches must be held before  match(a,b)
before = [ 0 for i in range(N*N) ]

for i in range(N):
    for j in range(N-2):
        # i vs A[i][j+1]  must be held after  i vs A[i][j]
        NEXT[ match(i,A[i][j]) ].append( match(i,A[i][j+1]) )
        before[ match(i,A[i][j+1]) ] += 1
        
q  = []
q0 = []

for i in range(N):
    for j in range(i+1,N):
        if before[ match(i,j) ] == 0:
            q.append( match(i,j) )
            
day = 0

while True:
    day += 1
    for M in q:
        for m in NEXT[M]:
            before[m] -= 1
            if before[m] == 0:
                q0.append(m)
        NEXT[M] = []
    q = q0
    q0 = []
    #print(NEXT)
    #print(before)
    if q == []:
        break

if NEXT == [ [] for i in range(N*N) ]:
    print(day)
else:
    print(-1)
### BUGGY CODE ###

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

L.sort()
c=N-1
ans=0
while c>1:
  for i,a in enumerate(L[:c]):
    for b in L[i+1:c]:
      if L[c]<a+b:
        ans+=1
  c-=1
print(ans)

### FIXED CODE ###

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

L.sort()
ans=0
i=0
while i<N-2:
    j=i+1
    k=j+1
    while j<N-1:
        while k<N:
            if L[i]+L[j]<=L[k]:
                ans+=k-j-1
                break
            k+=1
        if k==N:
            ans+=k-1-j
        j+=1
    i+=1
print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())
ans = 0
for a in range(K+1):
    for b in range(K+1):
        for c in range(K+1):
            if a + b + c == S:
                ans += 1
print(ans)

### FIXED CODE ###

k,s=map(int,input().split())
c=0
for i in range(k+1):
    for j in range(k+1):
        if s>=i+j and s-(i+j)<=k:
            c+=1
print(c)
### BUGGY CODE ###

import math
import collections
def main():

    N = int(input())
    d = collections.defaultdict(set)

    ans = 0
    for i in range(1, int(math.sqrt(N))+1):
        p = i
        while p <= N:
            d[p].add(i)
            d[p].add(p//i)
            p += i

    for i in range(1, N+1):
        ans += i * len(d[i])

    return ans

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

import math
import collections
def main():

    N = int(input())
    d = dict()
    for i in range(1, N+1):
        d[i] = 0

    ans = 0
    for i in range(1, N+1):
        p = N//i
        ans += p * (p+1)//2 * i
    return ans

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

n = int(input())
p = list(map(int,input().split()))
ans = 0
ps=[]

for i in p:
    ps.append(i)
    #print(ps)
    if min(ps)>=i:
        ans+=1
        
print(ans)


### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
ans = 0
ps=[]
p_min = p[0]
for i in p:
    if p_min>i:
        p_min=i
    
    if p_min>=i:
        ans+=1
print(ans)
### BUGGY CODE ###

import copy
from collections import deque
H, W = map(int, input().split())
M = [list(input()) for _ in range(H)]

black = deque()
for i in range(H):
  for j in range(W):
    if M[i][j] == '#':
      black.append((i, j))

ans = 0
while True:
  ans += 1
  next_black = deque()
  while black:
    bi, bj = black.popleft()
    if bi - 1 >= 0 and M[bi - 1][bj] == '.':
      M[bi - 1][bj] = '#'
      next_black.append((bi - 1, bj))
    if bj - 1 >= 0 and M[bi][bj - 1] == '.':
      M[bi][bj - 1] = '#'
      next_black.append((bi, bj - 1))
    if bi + 1 < H and M[bi + 1][bj] == '.':
      M[bi + 1][bj] = '#'
      next_black.append((bi + 1, bj))
    if bj + 1 < W and M[bi][bj + 1] == '.':
      M[bi][bj + 1] = '#'
      next_black.append((bi, bj + 1))
  if next_black:
     black = copy.copy(next_black)
  else:
     break
print(ans - 1)


### FIXED CODE ###

from collections import deque
import copy
 
def main():
    h, w = map(int, input().split())
    a = [[j == "#" for j in input()] for _ in range(h)]
 
 
    que = deque([(i, j) for i in range(h) for j in range(w) if a[i][j]])
 
    count = 0
    while True:
        count += 1
        nque = deque()
        while que:
            y, x = que.popleft()
            if x > 0 and not a[y][x-1]:
                a[y][x-1] = True
                nque.append((y,x-1))
            if x < w-1 and not a[y][x+1]:
                a[y][x+1] = True
                nque.append((y,x+1))
            if y > 0 and not a[y-1][x]:
                a[y-1][x] = True
                nque.append((y-1,x))
            if y < h-1 and not a[y+1][x]:
                a[y+1][x] = True
                nque.append((y+1,x))
 
        if nque:
            que = copy.copy(nque)
        else:
            break
 
    print(count - 1)

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

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    else:
      ans=-1
      break
  else:
    ans+=dd
    B[ind]-=d*dd
    push(B[ind],ind)
  
print(ans)


### FIXED CODE ###

n=int(input())
A=[int(i) for i in input().split()]
B=[int(i) for i in input().split()]

from heapq import heappop, heappush
push = lambda x,i: heappush(BB,(-x,i))
BB=[]

for i,b in enumerate(B):
  push(b,i)

ans=0
while BB:
  b,ind=heappop(BB)
  b,ai=-b,A[ind]
  if b<ai:
    ans=-1
    break
  d=B[(ind-1)%n]+B[(ind+1)%n]
  dd=(b-ai)//d
  if dd==0:
    if b==ai:
      continue
    ans=-1
    break
  ans+=dd
  B[ind]-=d*dd
  push(b-d*dd,ind)
  
print(ans)
### BUGGY CODE ###

A,B,C,D=map(int,input().split())
mod=998244353
dp=[[[0 for k in range(2)] for i in range(D+1)] for i in range(C+1)]
dp[C][D][0]=1
dp[C][D][1]=1
for i in range(D-1,B-1,-1):
    dp[C][i][0]=(dp[C][i+1][1]*C)%mod
    dp[C][i][1]=(dp[C][i+1][1]*C)%mod
for j in range(C-1,A-1,-1):
    dp[j][D][0]=(dp[j+1][D][0]*D)%mod
    dp[j][D][1]=(dp[j+1][D][0])%mod

for i in range(C-1,A-1,-1):
    for j in range(D-1,B-1,-1):
        dp[i][j][0]=(dp[i+1][j][0]*j+dp[i][j+1][1]*i)%mod
        dp[i][j][1]=(dp[i+1][j][0]+dp[i][j+1][1]*i)%mod

print(dp[A][B][0])


### FIXED CODE ###

A,B,C,D=map(int,input().split())
mod=998244353
dpx=[[0 for i in range(D+1)] for j in range(C+1)]
dpy=[[0 for i in range(D+1)] for j in range(C+1)]
dpx[C][D]=1
dpy[C][D]=1
for i in range(D-1,B-1,-1):
    dpx[C][i]=(dpy[C][i+1]*C)%mod
    dpy[C][i]=(dpy[C][i+1]*C)%mod
for j in range(C-1,A-1,-1):
    dpx[j][D]=(dpx[j+1][D]*D)%mod
    dpy[j][D]=(dpx[j+1][D])%mod

for i in range(C-1,A-1,-1):
    for j in range(D-1,B-1,-1):
        dpx[i][j]=((dpx[i+1][j]*j)%mod+(dpy[i][j+1]*i)%mod)%mod
        dpy[i][j]=(dpx[i+1][j]+(dpy[i][j+1]*i)%mod)%mod

print(dpx[A][B])
### 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())
if a - k > 0:
    c = a - k
elif a - k <= 0:
    c = 0
    if b - (k - a) > 0:
        b -= (k - a)
    elif b - (k - a) <= 0:
        b = 0
print(c, b)
### BUGGY CODE ###

from itertools import permutations
n,m,rl=map(int,input().split());r=list(map(int,input().split()))
d=[[float("inf")for _ in range(n)]for _ in range(n)]
for i in range(m):
  x,y,z=map(int,input().split())
  d[x-1][y-1],d[y-1][x-1]=z,z
for i in range(n):d[i][i]=0
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])
a=float("inf")
for i in permutations(r,rl):
  aa=0
  for j in range(rl-1):aa+=d[i[j]-1][i[j+1]-1]
  a=min(a,aa)
print(a)

### FIXED CODE ###

from itertools import permutations
n,m,rl=map(int,input().split());r=list(map(int,input().split()))
d=[[float("inf")for _ in range(n)]for _ in range(n)]
for i in range(m):
  x,y,z=map(int,input().split())
  d[x-1][y-1],d[y-1][x-1]=z,z
for i in range(n):d[i][i]=0
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])
a=float("inf")
for i in permutations(r,rl):
  aa=0
  for j in range(rl-1):aa+=d[i[j]-1][i[j+1]-1]
  a=min(a,aa)
print(a)
### BUGGY CODE ###

import bisect
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


def main():
    n = I()
    a = LI()
    b = LI()
    c = LI()
    a.sort()
    b.sort()
    c.sort()
    ans = 0
    for bi in b:
        a_ind = bisect.bisect_left(a, bi)
        a_oks = a[:a_ind]
        c_ind = bisect.bisect_right(c, bi)
        c_oks = c[c_ind:]
        ans += len(a_oks) * len(c_oks)
    print(ans)


main()


### FIXED CODE ###

import bisect
import sys


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


def main():
    n = I()
    a = LI()
    b = LI()
    c = LI()
    a.sort()
    b.sort()
    c.sort()
    ans = 0
    for bi in b:
        num_a = bisect.bisect_left(a, bi)
        num_c = n - bisect.bisect_right(c, bi)
        ans += num_a * num_c
    print(ans)


main()
### BUGGY CODE ###

from collections import deque
n,m,k=map(int,input().split())
fr=[[]]
for i in range(n-1):
  fr.append([])
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1].append(b)
  fr[b-1].append(a)

belong=[0]*n
large=[]
anslist=[0]*n
count=0
def bfs(k):
  global count
  if belong[k-1]==0:
    count+=1
    use=deque()
    use.append(k)
    ans=0
    aldic=[]
    for i in range(0,10**100):
      if not bool(use):
        break
      else:
        check=use.popleft()
        if check not in aldic:
          aldic.append(check)
          for x in fr[check-1]:
            use.append(x)
    for x in aldic:
      belong[x-1]=count
      anslist[x-1]=len(aldic)-len(fr[x-1])-1

for i in range(1,n+1):
  bfs(i)
for i in range(k):
  a,b=map(int,input().split())
  if belong[a-1]==belong[b-1]:
    anslist[a-1]-=1
    anslist[b-1]-=1
for i in range(0,len(anslist)):
  if i!=len(anslist)-1:
    print(anslist[i],end=" ")
  else:
    print(anslist[i])

### FIXED CODE ###

from collections import deque
n,m,k=map(int,input().split())
fr=[[]]
for i in range(n-1):
  fr.append([])
for i in range(m):
  a,b=map(int,input().split())
  fr[a-1].append(b)
  fr[b-1].append(a)

belong=[0]*n
anslist=[0]*n
count=0
def bfs(k):
  global count
  if belong[k-1]==0:
    count+=1
    use=deque()
    use.append(k)
    ans=0
    aldic={}
    while use:
      if not bool(use):
        break
      else:
        check=use.popleft()
        if check not in aldic:
          aldic[check]=1
          for x in fr[check-1]:
            use.append(x)
    for x in aldic:
      belong[x-1]=count
      anslist[x-1]=len(aldic)-len(fr[x-1])-1

for i in range(1,n+1):
  bfs(i)
for i in range(k):
  a,b=map(int,input().split())
  if belong[a-1]==belong[b-1]:
    anslist[a-1]-=1
    anslist[b-1]-=1
for i in range(0,len(anslist)):
  if i!=len(anslist)-1:
    print(anslist[i],end=" ")
  else:
    print(anslist[i])
### BUGGY CODE ###

N = int(input())
lGain = []
for i in range(N):
    r = input()
    for j in range(len(lGain)):
        if r == lGain[j]:
            break
    else:
        lGain.append(r)

print(len(lGain))

### FIXED CODE ###

N = int(input())
lResult = [input() for i in range(N)]

gain = list(set(lResult))

print(len(gain))
### BUGGY CODE ###

s = input()
K = int(input())

r = []
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        x = s[i:j]
        r.append(x)

x = sorted(list(set(r)))
print(x[K-1])

### FIXED CODE ###

s = input()
K = int(input())

ss = sorted(list(set(s)))

def f(s, c):
    indexes = []
    st = set()
    for i, si in enumerate(s):
        if si == c:
            indexes.append(i)
    for i in indexes:
        cnt = 0
        for j in range(i, len(s)):
            x = s[i:j+1]
            st.add(x)
            cnt += 1
            # print('cnt', cnt)
            if cnt > 5:
                break
    return sorted(list(st))

r = []
for ssi in ss:
    x =  f(s, ssi)
    r += x
    if len(r) > 5:
        break


ans = r[K-1]
# print(r)
print(ans)
### BUGGY CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

dp = [[0]*(n+1) for _ in range(n+1)]

for length in range(1,n+1):
    for stidx in range(n-length+1):
        # 次郎の手番
        if(n-length)%2:
            dp[stidx][stidx+length] = min(dp[stidx+1][stidx+length] - a[stidx],
                                          dp[stidx][stidx+length-1] - a[stidx+length-1])
        # 太郎の手番
        else:
            dp[stidx][stidx+length] = max(dp[stidx+1][stidx+length] + a[stidx],
                                          dp[stidx][stidx+length-1] + a[stidx+length-1])
            
print(dp[0][n])

### FIXED CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = list(li())

dp = [[0]*(n+1) for _ in range(n+1)]

for length in range(1,n+1):
    for stidx in range(n-length+1):
        # 次郎の手番
        if(n-length)%2:
            dp[stidx][stidx+length] = min(dp[stidx+1][stidx+length] - a[stidx],
                                          dp[stidx][stidx+length-1] - a[stidx+length-1])
        # 太郎の手番
        else:
            dp[stidx][stidx+length] = max(dp[stidx+1][stidx+length] + a[stidx],
                                          dp[stidx][stidx+length-1] + a[stidx+length-1])
            
print(dp[0][n])
### BUGGY CODE ###

from scipy.sparse import*
i=lambda:map(int,input().split())
f=csgraph.floyd_warshall
I=9e9
n,m,l=i()
d=eval('[I]*-~n,'*-~n)
exec('a,b,c=i();d[a][b]=c;'*m)
d=f(d,0)
d[d>l]=I
d[d<I]=1
d=f(d)
d[d>I]=I
q,=i()
exec('s,t=i();print(int(d[s,t]%I)-1);'*q)

### FIXED CODE ###

from scipy.sparse import*
s=csgraph.floyd_warshall
n,m,l,*t=map(int,open(0).read().split())
d=eval('[9e9]*-~n,'*-~n)
for a,b,c in zip(*[iter(t[:m*3])]*3):d[a][b]=d[b][a]=c
d=s(d)
d[d>l]=9e9
d[d<=l]=1
d=s(d)
d[d>9e9]=9e9
for s,t in zip(*[iter(t[m*3+1:])]*2):print(int(d[s,t]%9e9-1))
### BUGGY CODE ###

n=int(input())
A=sorted(list(map(int,input().split())),reverse=True)
for i in range(n):
    if A.count(A[i])>=2:
        for j in range(i+2,n):
            if A[i+2:].count(A[j])>=2:
                print(A[i]*A[j])
                exit()
print(0)

### FIXED CODE ###

from collections import Counter
n=int(input())
A=list(map(int,input().split()))
C=sorted(Counter(A).items(),key=lambda x:x[0],reverse=True)
m=len(C)
for i in range(m):
    if C[i][1]>=4:
        print(C[i][0]**2)
        exit()
    elif C[i][1]>=2:
        a=C[i][0]
        for j in range(i+1,m):
            if C[j][1]>=2:
                print(a*C[j][0])
                exit()
print(0)
### BUGGY CODE ###

import sys
import numpy as np

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 9, n + 1)
precalc = [np.zeros(weight_limit + 1, dtype=np.int64)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    parent_dp = precalc[u >> 1]
    dp = parent_dp.copy()
    dp[w:] = np.maximum(parent_dp[w:], parent_dp[:-w] + v)
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp = {0: 0}
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for cw, cv in list(dp.items()):
            nw = cw + w
            nv = cv + v
            if nw > weight_limit:
                continue
            if nw not in dp or dp[nw] < nv:
                dp[nw] = nv
        u >>= 1
    ans = max(v + precalc[u][l - w] for w, v in dp.items())
    buf.append(ans)

print('\n'.join(map(str, buf)))


### FIXED CODE ###

import sys

n, *inp = map(int, sys.stdin.buffer.read().split())
vvv = [0] + inp[0:n * 2:2]
www = [0] + inp[1:n * 2:2]

weight_limit = 10 ** 5
precalc_limit = min(1 << 10, n + 1)
precalc = [[0] * (weight_limit + 1)]

for u in range(1, precalc_limit):
    v = vvv[u]
    w = www[u]
    dp = precalc[u >> 1][:]
    for x in range(weight_limit, w - 1, -1):
        nv = dp[x - w] + v
        if dp[x] < nv:
            dp[x] = nv
    precalc.append(dp)

buf = []
mp = iter(inp[n * 2 + 1:])
for u, l in zip(mp, mp):
    if u < precalc_limit:
        buf.append(precalc[u][l])
        continue
    dp_w = [0]
    dp_v = [0]
    while u >= precalc_limit:
        v = vvv[u]
        w = www[u]
        for i in range(len(dp_w)):
            nw = dp_w[i] + w
            if nw > l:
                continue
            nv = dp_v[i] + v
            dp_w.append(nw)
            dp_v.append(nv)
        u >>= 1
    ans = 0
    for w, v in zip(dp_w, dp_v):
        nv = v + precalc[u][l - w]
        if ans < nv:
            ans = nv
    buf.append(ans)

print('\n'.join(map(str, buf)))