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

N, M = list(map(int, input().split()))
temp = [list(map(int, input().split())) for i in range(M)]
temp = list(zip(*temp))
P, Y = temp
#print(P, Y)
data = dict()
for p, y in zip(P, Y):
  if p not in data:
    data[p] = [y]
  else:
    data[p].append(y)
    
for i in data.keys():
  data[i] = sorted(data[i])
  
for p, y in zip(P, Y):
  print("{:06}{:06}".format(p, data[p].index(y)+1))

### FIXED CODE ###

N, M = list(map(int, input().split()))
temp = [list(map(int, input().split())) for i in range(M)]
temp = list(zip(*temp))
P, Y = temp
#print(P, Y)
data = dict()
for p, y in zip(P, Y):
  if p not in data:
    data[p] = [y]
  else:
    data[p].append(y)

data = {i:{value:j+1 for j, value in enumerate(sorted(data[i]))} for i in data.keys()}

for p, y in zip(P, Y):
  print("{:06}{:06}".format(p, data[p][y]))
### BUGGY CODE ###

N, M = map(int, input().split())
H = list(map(int,input().split()))
Road = [list(map(int, input().split())) for _ in range(M)]
num = 0
for i in range(N):
  for j in range(M):
    if Road[j][1] == i+1 and H[Road[j][0]-1] >= H[i]:
      break
    elif Road[j][0] == i+1 and H[Road[j][1]-1] >= H[i]:
      break
  else:
    num += 1
print(num)

### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int,input().split()))
Road = [sorted(list(map(int, input().split()))) for _ in range(M)]
num = N
Mem = [0 for _ in range(N)]
for j in range(M):
  if H[Road[j][0]-1] > H[Road[j][1]-1] and Mem[Road[j][1]-1] != 1:
    num -= 1
    Mem[Road[j][1]-1] = 1
  elif H[Road[j][1]-1] > H[Road[j][0]-1] and Mem[Road[j][0]-1] != 1:
    num -= 1
    Mem[Road[j][0]-1] = 1
  elif H[Road[j][1]-1] == H[Road[j][0]-1]:
    if Mem[Road[j][0]-1] != 1 and Mem[Road[j][1]-1] != 1:
      num -= 2
      Mem[Road[j][0]-1] = 1
      Mem[Road[j][1]-1] = 1
    elif Mem[Road[j][0]-1] == 1 and Mem[Road[j][1]-1] == 1:
      continue
    else:
      num -= 1
      Mem[Road[j][0]-1] = 1
      Mem[Road[j][1]-1] = 1
print(num)
### BUGGY CODE ###

import math

def segment_sieve(a, b):
    is_prime = [True] * (b - a)
    sqrt_b = math.ceil(math.sqrt(b))
    is_prime_small = [True] * (sqrt_b)

    i = 2
    while i * i < b:
        if is_prime_small[i]:
            j = 2 * i
            while j * j < b:
                is_prime_small[j] = False
                j += i

            j = max(2, round((a + i - 1) // i)) * i
            while j < b:
                is_prime[j - a] = False
                j += i

        i+=1
        
    return is_prime
                

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

minimum = (min(l for l, r in LR) + 1) // 2
maximum = max(r for l, r in LR)
primes = segment_sieve(minimum, maximum + 1)
for l, r in LR:
    count = 0
    for i, v in enumerate(primes):
        if i + minimum >= l and i + minimum > 1 and i + minimum <= r and (i + minimum) % 2 == 1 and v and primes[(i + minimum + 1) // 2 - minimum]:
            count += 1
    print(count)


### FIXED CODE ###

import math

def sieve(n):
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, n+1):
        if is_prime[i]:
            j = 2 * i
            while j <= n:
                is_prime[j] = False
                j += i
    return is_prime

Q = int(input())
LR = [list(map(int, input().split())) for _ in range(Q)]

primes = sieve(100000 + 1)
c = [0] * (100000 + 2)

for i, v in enumerate(primes):
    if v and i > 1 and i % 2 == 1 and primes[(i + 1) // 2]:
        c[i] = c[i-1] + 1
    else:
        c[i] = c[i-1]

for l, r in LR:
    print(c[r]-c[l-1])
### BUGGY CODE ###

from collections import deque
import copy
H, W = map(int, input().split())
maze = [list(input()) for i in range(H)]
S = []
for i in range(H):
  for j in range(W):
    if maze[i][j] == ".":
      maze[i][j] = float("inf")
      S.append([i, j])
    else:
      maze[i][j] = -1
def bfs(H, W, maze, S):
  ans = 0
  for sy, sx in S:
    maze1 = copy.deepcopy(maze)
    maze1[sy][sx] = 0
    q = deque()
    q.append([sy,sx])
    while len(q)>0:
      y, x = q.popleft()
      for i, j in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
        nexty = y+i
        nextx = x+j
        if nexty < 0 or nexty>=H or nextx < 0 or nextx>=W:
          continue
        if maze1[nexty][nextx] != -1:
          if maze1[nexty][nextx] > maze1[y][x]:
            maze1[nexty][nextx] = maze1[y][x] + 1
            q.append([nexty, nextx])
            ans = max(ans, maze1[nexty][nextx])
  print(ans)
bfs(H, W, maze, S)

### FIXED CODE ###

from collections import deque
import copy
def bfs():
    h,w = map(int, input().split())
    maze = [list(input()) for i in range(h)]
    S, G = [], []
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                S.append([y,x])
                G.append([y,x])
                maze[y][x]=float("inf")
            else:
                maze[y][x]=-1
    l = []
    ans = 0
    for i in range(len(S)):
        maze1 = copy.deepcopy(maze)
        maze1[S[i][0]][S[i][1]]=0
        que=deque([[S[i][0],S[i][1]]])
        while que:
          y,x=que.popleft()
          for k,m in [(1,0),(0,1),(-1,0),(0,-1)]:
            nexty,nextx=y+k,x+m
            if nexty < 0 or nexty >= h or nextx < 0 or nextx >= w:
                continue
            dist=maze1[nexty][nextx]
            if dist!=-1:
              if dist>maze1[y][x]+1:
                maze1[nexty][nextx]=maze1[y][x]+1
                que.append([nexty,nextx])
            ans = max(ans, maze1[nexty][nextx])
    print(ans)
bfs()
### BUGGY CODE ###

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

button = 1
count = 0
while(True):
    button = buttons[button - 1]
    count += 1
    if (button == 2):
        print(count)
        break
    elif(count > N):
        print(-1)

### FIXED CODE ###

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

button = 1
count = 0
while(True):
    button = buttons[button - 1]
    count += 1
    if (button == 2):
        print(count)
        break
    elif(count > N):
        print(-1)
        break
### BUGGY CODE ###

N, M = map(int, input().split())
ss = set(x for x in range(1,N+1))
for i in range(M):
  
  L, R = map(int, input().split())
  st = set(x for x in range(L, R+1))
  ss = ss & st
print(len(ss))

### FIXED CODE ###

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


for i in range(M-1):
      L1, R1 = map(int, input().split())
      if R1 < L or R < L1:
        print(0)
        exit()
      else:
        if L <= L1 <= R:
          L = L1
          
        elif L <= R1 <= R:
          R = R1
        
          
print(R-L+1)
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
s = input()
res = 0
for num in itertools.product(range(10), repeat=3):
    p = 0
    for i,j in enumerate(s):
        if int(j) == num[p]:
            p += 1
            if p == 3:
                res += 1
                break
print(res)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
mod2 = 998244353
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
s = input()
res = 0
a = [str(i) for i in range(10)]
for num in itertools.product(a, repeat=3):
    p = 0
    for i,j in enumerate(s):
        if j == num[p]:
            p += 1
            if p == 3:
                break
    if p == 3:
        res += 1
print(res)
### BUGGY CODE ###

#!/usr/bin/env python3
from functools import reduce
from itertools import product
from math import gcd

k = int(input())
p = list(product(range(1, k + 1), repeat=3))
print(sum(reduce(gcd, i) for i in p))


### FIXED CODE ###

#!/usr/bin/env python3
from functools import reduce
from itertools import combinations
from math import gcd

K = int(input())

sum = K * (K + 1) // 2

for i in combinations(range(1, K + 1), 2):
    sum += 6 * reduce(gcd, i)

for i in combinations(range(1, K + 1), 3):
    sum += 6 * reduce(gcd, i)

print(sum)
### BUGGY CODE ###

from functools import reduce
from math import gcd


def primes(n):
    is_prime = [i % 2 != 0 and i % 3 != 0 and i % 5 != 0 and i % 7 != 0 for i in range(n + 1)]
    is_prime[1] = False
    is_prime[2] = is_prime[3] = is_prime[5] = is_prime[7] = True
    for p in range(3, int(n**0.5) + 1, 2):
        if not is_prime[p]:
            continue
        for i in range(p**2, n + 1, p):
            is_prime[i] = False
    return [i for i, p in enumerate(is_prime) if p]


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    if reduce(gcd, a) > 1:
        print("not coprime")
        return
    p = primes(max(max(a), 10))
    for pi in p:
        c = 0
        for ai in a:
            if c > 1:
                print("setwise coprime")
                return
            c += ai % pi == 0
    print("pairwise coprime")


if __name__ == '__main__':
    main()


### FIXED CODE ###

from math import gcd


def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    m = max(a)
    p = [i for i in range(m + 1)]
    for i in range(3, m + 1):
        for j in range(2, int(i**.5 + 1) + 1):
            if i % j == 0:
                p[i] = j
                break
    factors = set()
    for ai in a:
        if ai == 1:
            continue
        f = set()
        while ai > p[ai]:
            f.add(p[ai])
            ai //= p[ai]
        f.add(ai)
        if factors & f:
            break
        factors |= f
    else:
        print("pairwise coprime")
        return
    g = a[0]
    for ai in a[1:]:
        g = gcd(ai, g)
        if g == 1:
            print("setwise coprime")
            return
    print("not coprime")


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

import sys
from collections import deque
import copy
import numpy


readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start,ex_kyori):
    tansaku = deque()
    tansaku.append(start)
    visited = {i:set() for i in range(h)}
    kyori = ex_kyori
    while tansaku:
        pre_y,pre_x = tansaku.popleft()
        if pre_x in visited[pre_y]:
            continue
        for i in range(pre_x-1,pre_x+2,2):
            if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                tansaku.append([pre_y,i])
                kyori[pre_y][i] = min(kyori[pre_y][i],kyori[pre_y][pre_x]+1)
        for j in range(pre_y-1,pre_y+2,2):
            if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                tansaku.append([j,pre_x])
                kyori[j][pre_x] = min(kyori[j][pre_x],kyori[pre_y][pre_x]+1)
        visited[pre_y].add(pre_x)
    return kyori

h,w = nm()
tizu = []
sharp = []
saitan = [[10**10]*w for _ in range(h)]
saitan = numpy.array(saitan)
for i in range(h):
    temp = list(input())
    s_temp = [[i,j] for j in range(w)  if temp[j] == '#' ]
    tizu.append(temp)
    sharp += s_temp
for i,j in sharp:
    saitan[i][j] = 0 
for i in sharp:
    saitan = bfs(i,saitan)
print(numpy.max(saitan))

### FIXED CODE ###

import sys
from collections import deque



readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prl = lambda x: print(*x ,sep='\n')

def bfs(start):
    tansaku = deque(start)
    visited = {i:set() for i in range(h)}
    res = 0
    black = len(start)
    while black != h*w:
        for _ in range(len(tansaku)):
            pre_y,pre_x = tansaku.popleft()
            if pre_x in visited[pre_y]:
                continue
            for i in range(pre_x-1,pre_x+2,2):
                if 0 <= i <= w-1 and tizu[pre_y][i] == '.':
                    tansaku.append([pre_y,i])
                    tizu[pre_y][i] = '#'
            for j in range(pre_y-1,pre_y+2,2):
                if 0 <= j <= h-1 and tizu[j][pre_x] == '.':
                    tansaku.append([j,pre_x])
                    tizu[j][pre_x] = '#'
            visited[pre_y].add(pre_x)
        black += len(tansaku)
        res += 1
    return res

h,w = nm()
tizu = []
sharp = []
for i in range(h):
    temp = list(input())
    s_temp = [[i,j] for j in range(w)  if temp[j] == '#' ]
    tizu.append(temp)
    sharp += s_temp
ans = bfs(sharp)
print(ans)
### BUGGY CODE ###

def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = [[0] * (k + 1) for _ in range(n)]
    dp[0][0] = 1
    dpi = dp[0]
    for i, a in enumerate(a_s[:-1]):
        dpi1 = dp[i + 1]
        dpi1[0] = s = dp[i][0] % md
        for j in range(1, a + 1):
            dpi1[j] = s = (s + dpi[j]) % md
        for j in range(a + 1, k + 1):
            dpi1[j] = s = (s + dpi[j] - dpi[j - a - 1]) % md
        dpi = dpi1
    return sum(dp[-1][k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(n, k, a_s))


### FIXED CODE ###

def f(n, k, a_s):
    md = 10 ** 9 + 7
    dp = [0] * (k + 1)
    dp[0] = 1
    for a in a_s[:-1]:
        ndp = [0] * (k + 1)
        ndp[0] = s = dp[0] % md
        for j in range(1, a + 1):
            ndp[j] = s = (s + dp[j]) % md
        for j in range(a + 1, k + 1):
            ndp[j] = s = (s + dp[j] - dp[j - a - 1]) % md
        dp = ndp
    return sum(dp[k - a_s[-1]:]) % md


n, k = map(int, input().split())
a_s = list(map(int, input().split()))
print(f(n, k, a_s))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
 
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline #文字列入力のときは注意
 
#n = int(input())
n,q = [int(i) for i in readline().split()]
 
g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)
 
add = [0]*n
for _ in range(q):
    p,x = [int(i) for i in readline().split()]
    add[p-1] += x
 
ans = [0]*n
#ans[0] = add[0]
 
def dfs(v,p,value): #p: parent of v
    value += add[v]
    ans[v] = value
    for c in g[v]:
        if c == p: continue
        dfs(c,v,value)
 
dfs(0,-1,0)
 
#print(add)
 
print(*ans)

### FIXED CODE ###

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
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 LSR(n):
    return [LS() for i in range(n)]
 
sys.setrecursionlimit(1000000)
mod = 1000000007
 
#A
def A():
    a = I()
    s = input()
    if a >= 3200:
        print(s)
    else:
        print("red")
    return
 
#B
def B():
    n = I()
    a = LI()
    ans = 0
    for i in a:
        ans += 1/i
    print(1/ans)
    return
 
#C
def C():
    n = I()
    v = LI()
    q = []
    for i in v:
        heappush(q,i)
    while q:
        x = heappop(q)
        if not q:
            print(x)
            return
        y = heappop(q)
        heappush(q,(x+y)/2)
    return
 
#D
def D():
    def dfs(x,d,s):
        for y in v[x]:
            if d[y]:
                s += f[y]
                ans[y] = s
                d[y] = 0
                dfs(y,d,s)
                s -= f[y]
    n,q = LI()
    v = [[] for i in range(n)]
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
    f = [0]*n
    for i in range(q):
        p,x = LI()
        p -= 1
        f[p] += x
    ans = [0]*n
    d = [1]*n
    d[0] = 0
    ans[0] = f[0]
    s = f[0]
    dfs(0,d,s)
    print(*ans)
    return
 
#E
def E():
    s = input()
    t = input()
 
    return
 
#F
def F():
 
    return
 
#Solve
if __name__ == "__main__":
    D()
### BUGGY CODE ###

N=int(input())
A=[0]*N
for i in range(N):
    A[i]=int(input())

j=0
ans=0
count=[0]*N
while j!=1:
    ans+=1
    j=A[j]-1
    count[ans]=j
    if count.count(j)==2:
        ans=-1
        break

print(ans)

### FIXED CODE ###

N=int(input())
A=[0]*N
for i in range(N):
    A[i]=int(input())

j=0
ans=0
count=[0]*N
while j!=1:
    ans+=1
    j=A[j]-1
    count[j]+=1
    if count[j]>=2:
        ans=-1
        break

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

# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0
throwgh_point_list = [-1 for i in range(N)]

def dfs(i, current, throwgh_point_list, ans_point_list):   
    # 頂点をN個通ったら終了処理
    if i >= N:
        # すでにカウント済の経路である場合
        if throwgh_point_list in ans_point_list:
            return

        # すでにカウント済ではないかつ全ての点に到達している場合
        # 順不同で比較
        if set(throwgh_point_list) == set(list(range(N))):
            global ans_count
            ans_count += 1
            ans_point_list.append(copy.copy(throwgh_point_list))
        return

    for j in range(len(Graph_list[current])):
        # 現在地を書き込む
        throwgh_point_list[i] = current

        # 次の点に移動する        
        dfs(i + 1, Graph_list[current][j], throwgh_point_list, ans_point_list)

dfs(0, 0, throwgh_point_list, [])
print(ans_count)

### FIXED CODE ###

# https://atcoder.jp/contests/abc054/tasks/abc054_c

import copy
import sys
input = sys.stdin.readline

# 頂点, 辺の数
N, M = map(int, input().split())

# グラフのリスト
# 各頂点からどこの頂点に向かう辺があるかどうかという情報
Graph_list = [[] for i in range(N)]

# 入力
for i in range(M):
    a, b = map(int, input().split())
    a += -1
    b += -1

    # 無向グラフなのでa, b両方
    Graph_list[a].append(b)
    Graph_list[b].append(a)

ans_count = 0           # 正解の経路の数
visited = [False] * N
visited[0] = True

def dfs(i, current, visited):   
    # 頂点をN個通ったら終了処理
    if i >= N-1:

        # 全ての点に到達している場合
        if all(visited):
            global ans_count
            ans_count += 1
            return 
        return 

    for j in Graph_list[current]:
        if visited[j] == False:
            # 現在地を書き込む
            visited[j] = True
            # 次の点に移動する        
            dfs(i + 1, j, visited)

            visited[j] = False

dfs(0, 0, visited)
print(ans_count)
### BUGGY CODE ###

# n < 50 のとき
# substring の全列挙

s = input()
n = len(s)
K = int(input())

substr = []
for i in range(n):
    for j in range(i, n):
        substr.append(s[i:j+1])

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

### FIXED CODE ###

s = input()
n = len(s)
K = int(input())

substr = []
# O(n*K)
for i in range(n):
    for j in range(i, i+K):
        substr.append(s[i:j+1])

substr = sorted(list(set(substr)))
print(substr[K-1])
### BUGGY CODE ###

import math


k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        for x in range(1,k+1):
            ans +=math.gcd(i,math.gcd(j,x)) 

            
print(ans)


### FIXED CODE ###

import math


k = int(input())
ans = 0
for i in range(1,k+1):
    for j in range(1,k+1):
        tmp = math.gcd(i,j)
        for x in range(1,k+1):
            ans +=math.gcd(tmp,x) 

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

S=input()
count2019 = [0]*2019
count2019[0]=1
mod2019 = 0
d = 1
for i in S[::-1]:
    mod2019 =mod2019+int(i)*d
    mod2019%=2019
    count2019[mod2019] +=1
    d *= 10
    d%2019
ans =0
for i in count2019:
   ans+= i*(i-1)//2
print(ans)
# print(count2019)

### FIXED CODE ###

s = list(input())
# s = list(str(10**200000))
n = len(s)
ans = 0
s.reverse()
# print(s)
x = 1
tot = 0
count = [0]*2019
for i in range(n):
    count[tot]+=1
    tot += int(s[i])*x
    # print(tot)
    tot %= 2019
    ans += count[tot]
    x = x*10%2019
print(ans)
### BUGGY CODE ###

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

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

### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))

c = Counter(a)
for i in range(n):
    print(c[i + 1])
### BUGGY CODE ###

s=input()
t=input()
dp=[[""]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+s[i]
        else:
            if len(dp[i+1][j])>len(dp[i][j+1]):
                dp[i+1][j+1]=dp[i+1][j]
            else:
                dp[i+1][j+1]=dp[i][j+1]
print(dp[len(s)][len(t)])

### FIXED CODE ###

s=input()
t=input()
dp=[[0]*(len(t)+1) for _ in range(len(s)+1)]
for i in range(len(s)):
    for j in range(len(t)):
        if s[i]==t[j]:
            dp[i+1][j+1]=dp[i][j]+1
        else:
            dp[i+1][j+1]=max(dp[i+1][j],dp[i][j+1])

res=""
i=len(s); j=len(t)
while i>0 and j>0:
    if dp[i][j]==dp[i-1][j]:
        i-=1
    elif dp[i][j]==dp[i][j-1]:
        j-=1
    else:
        res="".join([s[i-1],res])
        i-=1
        j-=1
print(res)
### BUGGY CODE ###

n,m = list(map(int,input().split()))
dc = {}
for i in range(n):
    a,b = list(map(int,input().split()))
    if dc.get(a):
        dc[a] = dc.get(a)+[b]
    else:
        dc[a] = [b]

# print(dc)

ans = 0
cands = []
for i in range(1,m+1):
    p = dc.get(i)
    if p:
        cands.extend(p)
    if len(cands) > 0:
        q = max(cands)
        cands.remove(q)
        ans += q
    # print("---",cands)

print(ans)

### FIXED CODE ###

import heapq
from collections import defaultdict
 
dc = defaultdict(list)
n,m = map(int,input().split())
for i in range(n):
    a,b = map(int,input().split())
    dc[a].append(b)

ans = 0
cands = []
for i in range(1,m+1):
    for j in dc[i]:
        heapq.heappush(cands, -j)
    if len(cands) > 0:
        ans += heapq.heappop(cands)*(-1)
    # print("---",cands)

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

n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(a)
for i in range(n):

    if max(a) > a[i]:
        print(max(a))
    else:
        if a.count(a[i]) > 1:
            print(a[i])
        else:
            print(b[-2])


### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
b = sorted(a)
max_a = max(a)
max_cnt = a.count(max_a)
for i in range(n):

    if max_a > a[i]:
        print(max_a)
    else:
        if max_cnt > 1:
            print(a[i])
        else:
            print(b[-2])
### BUGGY CODE ###

n, p = map(int, input().split())
m = int(p**(1/n)) + 10

for i in range(m, 0, -1):
    if p%(i**n) == 0:
        print(i)
        exit()

### FIXED CODE ###

n, p = map(int, input().split())
l = []
ans = 1

for i in range(2, int(p**0.5) + 2):
    if p%i == 0:
        cnt = 0
        while p%i == 0:
            p /= i
            cnt += 1
        l.append([i, cnt])

if p != 1:
    l.append([p, 1])

for i, j in l:
    while j >= n:
        ans *= i
        j -= n

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

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

### 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 ###

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

ans = a[0]
for i in range(1, len(a)):
    ans *= a[i]

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

### FIXED CODE ###

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

if a[0] == 0:
    print(0)
    exit()
else:
    ans = a[0]
    for i in range(1, len(a)):
        ans *= a[i]
        if ans > 10**18:
            print("-1")
            exit()
    
    
    print(ans)