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

#全体に同じものを足すときは累積和を考えたい

N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

graph = [set([]) for _ in range(N+1)]
for a,b in AB:
    graph[a].add(b)
    graph[b].add(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
check = [False for _ in range(N+1)]

for p,x in PX:
    counter[p] += x

def dfs(graph,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        check[p] = True
        for e in graph[p]:
            if not check[e]:
                counter[e] += counter[p]
                stk.append(e)
                check[e] = True

dfs(graph,counter,1)

ans = " ".join(map(str,counter[1:]))
print(ans)


### FIXED CODE ###

#全体に同じものを足すときは累積和を考えたい

N,Q = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N-1)]
PX = [list(map(int,input().split())) for _ in range(Q)]

graph = [[] for _ in range(N+1)]

for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)
#どちらが親か分からないがとりあえずつながっている
#どちらが親かは後で判断

counter = [0 for _ in range(N+1)]
#counter[i]:i番目の頂点のカウンター
parent = [None for _ in range(N+1)]

for p,x in PX:
    counter[p] += x

def dfs(graph,counter,edge):
    stk = []
    stk.append(edge)
    while len(stk) > 0:
        p = stk.pop()
        for e in graph[p]:
            if parent[p] == e:
                continue
            else:
                parent[e] = p
                counter[e] += counter[p]
                stk.append(e)

dfs(graph,counter,1)

ans = " ".join(map(str,counter[1:]))
print(ans)
### BUGGY CODE ###

from collections import deque
N, K = map(int, input().split())
      
A =  list(map(int, input().split()))
B = [0] * (N + 1)

for i in range(N):
  B[i+1] = A[i]
#print(B)

start = 1
d = deque([])
first = 0
while True:
  a = B[start]
  start = a
  first += 1
  if a in d:
    break
  d.append(a)
    
#print(first, start)

second = 0
start_ = start
while True:
  start_ = B[start_]
  second += 1
  if start_ == start:
    break
#print(second)

if K <= first:
  S = 1
else:
  K -= first
  K %= second
  S = start

for i in range(K):
  S = B[S]
print(S)

### FIXED CODE ###

def main():

  N, K = map(int, input().split())   
  A = [0] + list(map(int, input().split()))
  cur = 1
  visited = [-1] * (N + 1)
  visited[cur] = 0
  for i in range(1, K + 1):
    next_cur = A[cur]
    if next_cur == cur:
      print(next_cur)
      return
    elif visited[next_cur] != -1:
      mod = i - visited[next_cur]
      start = visited[next_cur]
      break
    else:
      visited[next_cur] = visited[cur] + 1
      cur = next_cur
  else:
    print(next_cur)
    return
  K = (K - start) % mod
  print(visited.index(K+start))
  
  
if __name__ == "__main__":
  main()
### BUGGY CODE ###

a,b = map(str,input().split())
list = ['DEFAULT']*400
tmp = 3
while tmp*tmp<=int(a+b):
  list[tmp] = str(tmp*tmp)
if (a+b) in list:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

a,b = map(str,input().split())
c = int(a+b)
list = ['DEFAULT']*400
tmp = 3
while tmp*tmp<=c:
  list[tmp] = tmp*tmp
  tmp +=1
if c in list:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

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

from collections import Counter
c = Counter(a)

answers=dict()
for k in range(n):
    ak = a[k]
    if ak in answers:
        ans = answers[ak]
    else:
        temp = [c[cc]-(ak==cc) for cc in c]
        ans = sum(t*(t-1)//2 for t in temp)
        answers[ak]=ans
    
    print(ans)

### FIXED CODE ###

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

from collections import Counter
c = Counter(a)

ans0 = sum(cc*(cc-1)//2 for cc in c.values())

for k in range(n):
    m = c[a[k]]
    print(ans0-m+1)
### BUGGY CODE ###

def main():
    n = input()
    for i in xrange(n):
        X = raw_input()
        Y = raw_input()
        print lcs(X,Y)

def lcs(X,Y):
    m = len(X)
    n = len(Y)
    c = [[0]*(n+1) for i in xrange(m+1)]

    for i in xrange(m):
        for j in xrange(n):
            if X[i] == Y[j]:
                c[i+1][j+1] = c[i][j] + 1
            else:
                c[i+1][j+1] = max(c[i][j+1],c[i+1][j])
    return c[m][n]
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n = input()
    for i in xrange(n):
        X = raw_input()
        Y = raw_input()
        print lcs(X,Y)

def lcs(X,Y):
    m = len(X)
    n = len(Y)
    r1 = [0 for i in xrange(n+1)]
 
    for i in xrange(m):
        r0 = r1[:]
        for j in xrange(n):
            if X[i] == Y[j]:
                r1[j+1] = r0[j] + 1
            elif r0[j+1] < r1[j]:
                r1[j+1] = r1[j]
    return r1[-1]

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

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
dp = [0]*(n+1)
dp[0] = 1
mod = 10**9 + 7
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1
for i in range(2,n+1):
  if i in a:
    continue
  else:
    dp[i] = (dp[i-1]+dp[i-2]) % mod
print(dp[-1] % mod)

### FIXED CODE ###

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
a = [int(input()) for _ in range(m)]
a = set(a)
dp = [0]*(n+1)
dp[0] = 1
mod = 10**9 + 7
if 1 in a:
  dp[1] = 0
else:
  dp[1] = 1
for i in range(2,n+1):
  if i in a:
    continue
  else:
    dp[i] = (dp[i-1]+dp[i-2]) % mod
print(dp[-1] % mod)
### BUGGY CODE ###

def takeSecond(elem):
    return elem[1]

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

sushi = [list(map(int,input().split())) for i in range(n)]

sushi.sort(key=takeSecond,reverse=True)

selected = sushi[:k]
kindset = set([item[0] for item in selected])

startKindNum = len(kindset)

score = startKindNum*startKindNum + sum([item[1] for item in selected])

scorelist = []
scorelist.append(score)
front_pointer = k - 1
pointer = k
for i in range(startKindNum+1,min([k+1,n+1])):
    #remove the smallest one that does not decrease kind
    for p in range(front_pointer,-1,-1):
        item = selected[p]
        flag = False
        for idx in range(p):
            if(selected[idx][0]==item[0]):
                score -= item[1]
                selected.remove(item)
                front_pointer = p - 1
                flag = True
                break
        if(flag):
            break

    #add the largest one that add kind
    for j in range(pointer,n):
        if(sushi[j][0] not in kindset):
            selected.append(sushi[j])
            kindset.add(sushi[j][0])
            k += 1
            pointer = j + 1            
            score += 2*startKindNum + 1 + sushi[j][1]
            startKindNum += 1
            scorelist.append(score)
            break
print(max(scorelist))


### FIXED CODE ###

def takeSecond(elem):
    return elem[1]

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

sushi = [list(map(int,input().split())) for i in range(n)]

sushi.sort(key=takeSecond,reverse=True)
'''
selected = sushi[:k]
kindset = set([item[0] for item in selected])

startKindNum = len(kindset)

score = startKindNum*startKindNum + sum([item[1] for item in selected])
maxscore = score
front_pointer = k - 1
pointer = k
for i in range(startKindNum+1,min([k+1,n+1])):
    #remove the smallest one that does not decrease kind
    for p in range(front_pointer,-1,-1):
        item = selected[p]
        flag = False
        for idx in range(p):
            if(selected[idx][0]==item[0]):
                score -= item[1]
                selected.remove(item)
                front_pointer = p - 1
                flag = True
                break
        if(flag):
            break

    #add the largest one that add kind
    for j in range(pointer,n):
        if(sushi[j][0] not in kindset):
            selected.append(sushi[j])
            kindset.add(sushi[j][0])
            k += 1
            pointer = j + 1            
            score += 2*startKindNum + 1 + sushi[j][1]
            if(score>maxscore):
                maxscore = score
            startKindNum += 1
            break
'''
kindset = set([])
score = 0
extras = []
for item in sushi[:k]:
    if item[0] in kindset:
        extras.append(item[1])
    else:
        kindset.add(item[0])
    score += item[1]
score += len(kindset)**2
maxscore = score
for item in sushi[k:]:
    if not  extras:
        break
    if item[0] in kindset:
        continue
    score += (item[1] - extras.pop()) + 2*len(kindset) + 1
    kindset.add(item[0])
    #print(score)
    if score > maxscore:
        maxscore = score


print(maxscore)
### BUGGY CODE ###

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

# for i in range(m):
#     a = sorted(a)
#     b,c = map(int,input().split())
#     for j in range(b):
#         if a[j] >= c:
#             break
#         else:
#             a[j] = c
# print(sum(a))

for i in range(m):
    b,c = map(int,input().split())
    a.extend([c]*b)
    a = sorted(a)[-n:]
print(sum(a))

### FIXED CODE ###

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

# for i in range(m):
#     a = sorted(a)
#     b,c = map(int,input().split())
#     for j in range(b):
#         if a[j] >= c:
#             break
#         else:
#             a[j] = c
# print(sum(a))
d = []
for i in range(m):
    b,c = map(int,input().split()) # b 交換できる枚数 c:カードの値
    d.append((b,c))

# dを降順にsorted
d = sorted(d,key=lambda x: x[1], reverse=True)

for i in range(m):
    b,c = d[i]
    a.extend([c]*b)
    if len(a) > 2*n:
        break

print(sum(sorted(a)[-n:]))
### BUGGY CODE ###

import sys
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
mod = 10**9 + 7
inf = float('inf')
ans = int(0)

S = str(input())
N = len(S)
M = 13
c = [0]*(N)
for i in range(N):
    c[i] = (10**i)%M
#print(c)
c.reverse()
#print(c)
"""
dp = [[0]*M for _ in range(N+1)]
i = int(0)
for j in range(M):
    dp[0][j] = 1
for s in S:
    if s == "?":
        for l in range(10):
            m = l * c[i] % M
            dp[i+1][(M - m) % M] += dp[i][j]
    else:
        m = int(s) * c[i] % M
        dp[i][(M - m) % M] +=dp[i][j]
    i +=1
"""
dp = [[0]*M for _ in range(N)]
if S[0] == "?":
    for l in range(10):
        m = l * c[0]%M
        dp[0][m] += 1
else:
    m = int(S[0]) * c[0]%M
    dp[0][m] = 1
for i in range(1,N):
    if S[i] == "?":
        for j in range(M):
            for l in range(10):
                m = l*c[i]%M
                dp[i][j] += dp[i-1][(M+j-m)%M]
    else:
        for j in range(M):
            m = int(S[i])*c[i]%M
            dp[i][j] = dp[i-1][(M+j-m)%M]

#print(dp)
print(dp[N-1][5]%mod)

### FIXED CODE ###

import sys
 
 
def solve():
    input = sys.stdin.readline
    mod = 10 ** 9 + 7
    s = str(input().rstrip('\n'))
    ls = [[0] * 13 for _ in range(len(s))]
    for i in range(len(s)):
        if i == 0:
            if s[-i-1] == "?":
                for j in range(10):
                    ls[i][j] += 1
            else:
                ls[i][int(s[-i-1])] += 1
        else:
            mult = pow(10, i, 13)
            if s[-i-1] == "?":
                for j in range(13):
                    for k in range(10):
                        ls[i][(k * mult + j) % 13] += ls[i-1][j]
            else:
                st = int(s[-i-1])
                for j in range(13):
                    ls[i][(st * mult + j) % 13] += ls[i-1][j]
        for j in range(13):
            ls[i][j] = ls[i][j] % mod
    print(ls[-1][5])
 
 
if __name__ == '__main__':
    solve()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]"):
    weightA = 0
    tmp_A = N
    for idx, a in enumerate(A):
        if weightA + a > K:
            tmp_A = idx
            break
        else:
            weightA += a
    max_count = current_count  = tmp_A
    len_A = tmp_A

    weightB = 0
    terminated = False
    for b in B:
        if terminated == True and weightA + weightB > K:
            break

        if len_A==0 and weightA + weightB + b > K:
            break

        if weightA + weightB + b <= K:
            weightB += b
            current_count += 1

        elif terminated==False:
            while weightA + weightB + b > K:
                if len_A>0:
                    weightA -= A[len_A-1]
                    len_A -= 1
                    current_count -= 1
                else:
                    terminated=True

            if weightA + weightB + b <= K:
                weightB += b
                current_count += 1
        max_count = max(max_count, current_count)

    print(max_count)
    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    solve(N, M, K, A, B)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
a, b = [0], [0]

for i in range(N):
    a.append(a[i] + A[i])
for i in range(M):
    b.append(b[i] + B[i])
ans, j = 0, M
for i in range(N+1):
    if a[i] > K:
        break
    while b[j] > K - a[i]:
        j -= 1
    ans = max(ans, i + j)
print(ans)
### BUGGY CODE ###



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

    # dp[i][j] : i ~ j - 1までの数列におけるX - Yのスコア
    # taroのターンの場合、
    #   max(dp[i + 1][j] + iスコア, dp[i][j - 1] + jスコア)
    # jiroのターンの場合
    #   min(dp[i + 1][j] - iスコア, dp[i][j - 1] - jスコア)

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

    # len = 1, 2, 3, ...と求めてゆく
    # len = xのとき、dp[i + 1][j]かdp[i][j - 1]はlen = x - 1のときのスコアなので
    # 計算済み
    for l in range(1, n + 1):
        for i in range(n):
            j = i + l
            if j > n:
                break
            
            # taroのターン, nとlの偶奇が一致する時
            if (n - l) % 2 == 0:
                dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
            else:
                dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])

    print(dp[0][n])
            

submit()

### FIXED CODE ###



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

    # dp[i][j] : i ~ j - 1までの数列におけるX - Yのスコア
    # taroのターンの場合、
    #   max(dp[i + 1][j] + iスコア, dp[i][j - 1] + jスコア)
    # jiroのターンの場合
    #   min(dp[i + 1][j] - iスコア, dp[i][j - 1] - jスコア)

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

    # len = 1, 2, 3, ...と求めてゆく
    # len = xのとき、dp[i + 1][j]かdp[i][j - 1]はlen = x - 1のときのスコアなので
    # 計算済み
    for l in range(1, n + 1):
        for i in range(n):
            j = i + l
            if j > n:
                break
            
            # taroのターン, nとlの偶奇が一致する時
            if (n - l) % 2 == 0:
                dp[i][j] = max(dp[i + 1][j] + a[i], dp[i][j - 1] + a[j - 1])
            else:
                dp[i][j] = min(dp[i + 1][j] - a[i], dp[i][j - 1] - a[j - 1])

    print(dp[0][n])
            

submit()
### BUGGY CODE ###

from collections import Counter
s = input()
n = len(s)
c = Counter([])
c[0]+=1
for i in range(n):
    t = int(s[i:])%2019
    c[t]+=1
ans = 0
for v in c.values():
    ans+=v*(v-1)//2
print(ans)

### FIXED CODE ###

s = input()

n = len(s)
c = [0]*2019
c[0]+=1
t = 0
digit = 1
for ss in s[::-1]:
    t = (t+int(ss)*digit) % 2019
    digit = (digit * 10) % 2019
    c[t]+=1
ans = 0
ans = sum(cc*(cc-1)//2 for cc in c)
print(ans)
### BUGGY CODE ###

import bisect

N=[int(x)for x in input().split()]
D=[int(x) for x in input().split()]

D.sort()
total=0

for i in range(len(D)-2):
    for j in range(i+1,len(D)-1):
        v=D[i]-D[j]
        total+= bisect.bisect_left(D[j+1:],D[i]+D[j])


print(total)


### FIXED CODE ###

import bisect

N=int(input())
D=[int(x) for x in input().split()]

D.sort()
total=0

for i in range(N-2):
    for j in range(i+1,N-1):
        total+=bisect.bisect_left(D,D[i]+D[j])-j-1

print(total)
### BUGGY CODE ###

N,M = map(int,input().split())
edge_from = [set() for _ in range(N+1)]
edge_to = [set() for _ in range(N+1)]
ans = [-1]*(N+1)
child = set()
parent = -1
for _  in range(N-1+M):
    go,to = map(int,input().split())
    edge_from[go].add(to)
    edge_to[to].add(go)
    child.add(to)
for i in range(1,N+1):
    if i not in child:
        parent = i
stack = [parent]
distance = [-1]*(N+1)
distance[parent] = 0
while stack:
    v = stack.pop()
    for u in edge_from[v]:
        distance[u] = max(distance[v] + 1,distance[u])
        stack.append(u)
dis = [set() for _ in range(max(distance)+1)]
for i in range(1,N+1):
    dis[distance[i]].add(i)
for i in range(1,N+1):
    if i == parent :
        ans[i] = 0
    else:
        for j in dis[distance[i]-1]:
            if j in edge_to[i]:
                ans[i] = j
                break
for i in range(1,N+1):
    print(ans[i])           

### FIXED CODE ###

from collections import defaultdict, deque
import heapq
v, n = map(int, input().split())
es = [[int(x) for x in input().split()] for _ in range(v+n-1)]

outs = defaultdict(list)
ins = defaultdict(int)
edge_from = [[] for _ in range(v+1)]
edge_to = [[] for _ in range(v+1)]
ans = [-1]*(v+1)
for v1, v2 in es:
    edge_from[v1].append(v2)
    edge_to[v2].append(v1)
    outs[v1].append(v2)
    ins[v2] += 1

q = deque(v1 for v1 in range(v) if ins[v1] == 0)
res = []
while q:
    v1 = q.popleft()
    res.append(v1)
    for v2 in outs[v1]:
        ins[v2] -= 1
        if ins[v2] == 0:
            q.append(v2)
rev = [0]*(v+1)
for i in range(1,v+1):
    rev[res[i]] = i
redge_to = [[] for _ in range(v+1)]
for i in range(1,v+1):
    for j in edge_to[i]:
        ri = rev[i]
        rj = rev[j]
        heapq.heappush(redge_to[ri],-rj)
for ri in range(1,v+1):
    if redge_to[ri]:
        rj = redge_to[ri][0]
        i = res[ri]
        j = res[-rj]
        ans[i] = j
    else:
        i =res[ri]
        ans[i] = 0
for i in ans[1:]:
    print(i)
### BUGGY CODE ###

S = list(input())
Q = int(input())
x = 1
for i in range(Q):
    a, *b = input().split()
    if a == "1":
        x *= -1
    elif a == "2":
        c, d = b
        if (c == "2" and x == -1) or  (c == "1" and x == 1):
            S.insert(0, d)
        else:
            S.append(d)
if x == -1:
    S = S[::-1]
print(*S, sep="")

### FIXED CODE ###

from collections import deque
S = deque(input())
Q = int(input())
x = 1
l=[]
for i in range(Q):
    a, *b = input().split()
    if a == "1":
        x *= -1
    elif a == "2":
        c, d = b
        if (c == "2" and x == -1) or  (c == "1" and x == 1):
            S.appendleft(d)
        else:
            S.append(d)
if x == -1:
    S.reverse()
print(*S, sep="")
### BUGGY CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]


h,w=map(int,input().split())
a=[list(map(int,input().split())) for i in range(h)]
b=[list(map(int,input().split())) for i in range(h)]

lst=[[0]*w for i in range(h)]

lst[0][0]={abs(a[0][0]-b[0][0]):1}
# print(lst)
d=deque([(0,0)])
while d:
    now=d.popleft()
    if now[0]+1<h:
        if lst[now[0]+1][now[1]]==0:
            d.append((now[0]+1,now[1]))
            lst[now[0]+1][now[1]]={}

        for i in lst[now[0]][now[1]].keys():
            ab=abs(a[now[0]+1][now[1]]-b[now[0]+1][now[1]])
            lst[now[0]+1][now[1]][i+ab]=1
            lst[now[0]+1][now[1]][abs(i-ab)]=1

    # print(lst)
    if now[1]+1<w:
        if lst[now[0]][now[1]+1]==0:
            d.append((now[0],now[1]+1))
            lst[now[0]][now[1]+1]={}

        for i in lst[now[0]][now[1]].keys():
            ab=abs(a[now[0]][now[1]+1]-b[now[0]][now[1]+1])
            lst[now[0]][now[1]+1][i+ab]=1
            lst[now[0]][now[1]+1][abs(i-ab)]=1
    # print(d)
    # print(lst)
anslst=list(lst[-1][-1].keys())
anslst.sort(key=lambda x: abs(x))
print(abs(anslst[0]))

### FIXED CODE ###

import sys

input = sys.stdin.buffer.readline

h, w = map(int, input().split())
AA = [list(map(int, input().split())) for _ in range(h)]
BB = [list(map(int, input().split())) for _ in range(h)]

kouho = [[0] * (w) for _ in range(h)]
delta = abs(AA[0][0] - BB[0][0])
kouho[0][0] |= 1 << delta
for y in range(h):
    for x in range(w):
        nx = x + 1
        ny = y
        if nx < w:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp

        nx = x
        ny = y + 1
        if ny < h:
            delta = abs(AA[ny][nx] - BB[ny][nx])
            temp = 0
            for i in range(1, delta + 1):
                if (kouho[y][x] >> i) % 2:
                    temp |= 1 << (delta - i)
            # print(x,y,kouho[y][x],temp,delta)
            kouho[ny][nx] |= kouho[y][x] << delta
            kouho[ny][nx] |= kouho[y][x] >> delta
            kouho[ny][nx] |= temp
# print(kouho)
for i in range(81):
    if (kouho[h - 1][w - 1] >> i) % 2:
        print(i)
        exit()
### BUGGY CODE ###

S = int(input())

leng = len(str(S))
count = 0

for j in range(leng-3):
    for i in range(leng-j, 3, -1):
        partial = S // (10 ** j)
        partial = partial % (10 ** i)
        if partial == 0:
            continue
        if partial % 2019 == 0:
            count += 1
print(count)

### FIXED CODE ###

s = input()[::-1]

counts = [0] * 2019
counts[0] = 1

num, d = 0, 1

for char in s:
    num += int(char) * d
    num %= 2019
    d *= 10
    d%= 2019
    counts[num] += 1

ans = 0
for cnt in counts:
    ans += cnt * (cnt - 1) // 2

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

import bisect

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

for i in range(M):
    t=A[-1]//2
    index=bisect.bisect_right(A,t)
    A=A[0:len(A)-1]
    A.insert(index,t)
    

print(sum(A))

### FIXED CODE ###

import heapq

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

que = []
for a in A:
  heapq.heappush(que, -1*a)
 
for a in range(M):
  maxvalue = -1 * heapq.heappop(que)
  maxvalue /= 2
  heapq.heappush(que, -1*maxvalue)
 
print(sum([int(-1*a) for a in que]))
### BUGGY CODE ###

L, R = map(int,input().split())

new_list = []
for i in range(L,R):
    for j in range(i+1, R+1):
        A = [(i*j)%2019]
        mi = min(A)
        new_list.append(mi)

print(min(new_list))


### FIXED CODE ###

import sys
L, R = map(int,input().split())

new_list = []
for i in range(L,R):
    for j in range(i+1, R+1):
        new_list.append((i*j)%2019)
        
        if (i*j)%2019 == 0:
            print(0)
            sys.exit()
print(min(new_list))
### BUGGY CODE ###

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


### FIXED CODE ###

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