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



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

    k_cand = [i * k for i in range(1, (2 * n) // k + 1)]

    ans = []
    for i in range(1, n + 1):
        a = i
        for k1 in k_cand:
            b = k1 - a
            if b <= 0 or b > n:
                continue

            for k2 in k_cand:
                c = k2 - b
                if c <= 0 or c > n:
                    continue

                if (a + c) % k == 0:
                    ans.append((a, b, c))

    print(len(ans))
        

if __name__ == "__main__":
    submit()

### FIXED CODE ###

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

    if k % 2:
        count = sum([1 for c in range(1, n + 1) if c % k == 0])
        print(count ** 3)
    else:
        count_1 = sum([1 for c in range(1, n + 1) if c % k == 0])
        count_2 = sum([1 for c in range(1, n + 1) if c % k == k // 2])
        print(count_1 ** 3 + count_2 ** 3)


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

N = int(input())
A = list(map(int,input().split()))
for i in range(1,N+1) :
    ans = A.count(i)
    print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
C = [0] * N
for i in range(len(A)) :
    x = A[i]
    C[x-1] += 1
for i in range(N) :
    print(C[i])
### BUGGY CODE ###

def main():
    H, W, D = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))
    Q = int(input())
    queries = []
    for _ in range(Q):
        R, L = map(int, input().split())
        queries.append([R, L])

    d = dict()
    for i in range(H):
        for j in range(W):
            d[A[i][j]] = [i, j]

    for R, L in queries:
        i, j = d[R]
        magic = 0
        if R != L:
            while R+D != L:
                k, l = d[R+D]
                magic += abs(i-k)+abs(j-l)
                i, j = k, l
                R = R+D
            k, l = d[R+D]
            magic += abs(i-k) + abs(j-l)
        print(magic)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections
def main():
    H, W, D = map(int, input().split())
    A = []
    for _ in range(H):
        A.append(list(map(int, input().split())))
    Q = int(input())
    queries = []
    for _ in range(Q):
        L, R = map(int, input().split())
        queries.append([L, R])

    d = collections.defaultdict(list)
    for i in range(H):
        for j in range(W):
            d[A[i][j] % D].append([A[i][j], i, j])
    for v in d:
        d[v] = sorted(d[v], key = lambda x: x[0])

    d1 = collections.defaultdict(list)
    for v in d:
        prefix = [0]
        if v == 0:
            prefix.append(0)
        for i in range(len(d[v])-1):
            mag = abs(d[v][i][1] - d[v][i+1][1]) + abs(d[v][i][2]-d[v][i+1][2])
            prefix.append(prefix[-1]+mag)
        d1[v] = prefix
    # print(d1)

    # print(A)
    for L, R in queries:
        if L == R:
            print(0)
        else:
            l = (R-L) // D
            i = L // D
            v = L % D
            magic = d1[v][i+l] - d1[v][i]
            print(magic)

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

import sys

import numpy as np

readline = sys.stdin.buffer.readline


def f(N, K, A):
    p = 0
    for i in range(K):
        C = np.zeros(N + 1, dtype=np.int64)

        for j, a in enumerate(A):
            l = max(0, j - a)
            r = min(j + a + 1, N)
            C[l] += 1
            C[r] -= 1

        A = np.cumsum(C)

        if len(set(A[:-1])) == 1:
            p += 1
            if p == 2:
                break
    return A


def solver():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    A = f(N, K, A)
    print(*A[:-1])


solver()


### FIXED CODE ###

import sys

from numba import njit

import numpy as np

readline = sys.stdin.buffer.readline


@njit('i8[:](i8, i8, i8[:])', cache=True)
def f(N, K, A):
    for i in range(min(K, 100)):
        C = np.zeros(N + 1, dtype=np.int64)

        for j, a in enumerate(A):
            l = max(0, j - a)
            r = min(j + a + 1, N)
            C[l] += 1
            C[r] -= 1

        A = np.cumsum(C)

    return A


def solver():
    N, K = map(int, readline().split())
    A = list(map(int, readline().split()))
    A = f(N, K, np.array(A))
    print(*A[:-1])


solver()
### BUGGY CODE ###


import itertools
import sys
import math

sys.setrecursionlimit(10**9)

def comb(n, r):
    mod = 10**9 + 7
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * pow(i+1, mod-2, mod) % mod
    return res

def main():
    N, a, b = map(int,input().split())

    # print(comb(10**5,5000,10**9+7))
    nCa = comb(N,a)
    nCb = comb(N,b)

    _, ans = divmod(2**N-1 - nCa - nCb,10**9+7)
    print(ans)

if __name__ == "__main__":
  main()


### FIXED CODE ###


import itertools
import sys
import math

sys.setrecursionlimit(10**9)

def comb(n, r):
    mod = 10**9 + 7
    r = min(r, n-r)
    res = 1
    for i in range(r):
        res = res * (n - i) * pow(i+1, mod-2, mod) % mod
    return res

def main():
    N, a, b = map(int,input().split())

    # print(comb(10**5,5000,10**9+7))
    nCa = comb(N,a)
    nCb = comb(N,b)

    _, ans = divmod(2**N-1 - nCa - nCb,10**9+7)
    print(ans)

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

"""
2019 4038 6057 8076 10095
12114 14133 16152 18171
"""

s = input()
count = 0

for i in range(len(s)-4):
  for j in range(4, len(s)-i):
    if int(s[i:i+j+1]) % 2019 == 0:
      count += 1

if int(s[-4:])%2019 == 0:
  count += 1
print(count)

### FIXED CODE ###

import collections
s = input()

l = [int(s[-1])]
d = 10
for i in range(len(s)-2, -1, -1):
  l.append((l[-1] + int(s[i])*d) % 2019)
  d *= 10
  d %= 2019
c = collections.Counter(l)
ans = 0  
for i in c.values():
  ans += i*(i-1)//2

ans += c[0]

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

N=int(input())
H=list(map(int,input().split()))
L=[0 for _ in range(N)]
for t in range(N):
    for i in range(t,N):
        if t==i:
            continue
        if H[t]>=H[i]:
            L[t]+=1
            H[t]=H[i]
        else:
            break
print(max(L))

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
min=H[0]
count=[0 for _ in range(N)]
cnt=0
t=0
for i in range(1,N):
    if H[i]<=min:
        min=H[i]
        cnt+=1
    else:
        count[t]=cnt
        cnt=0
        t+=1
        min=H[i]
count[t]=cnt
print(max(count))
### BUGGY CODE ###

from itertools import chain
from collections import Counter

def factors(n):
    yield from chain.from_iterable(({i, n//i} for i in range(1, int(n ** 0.5) + 1) if n % i == 0))

def get_non_divisible():
    n, *lst = map(int, open(0).read().split())
    c = Counter(lst)
    d = {val: sum((-c.get(f, 0) for f in factors(val)), len(lst)) for val in c}
    res = 0
    for i in lst:
      if d[i] == n - 1:
        res += 1
    return res
  
if __name__ == '__main__':
    print(get_non_divisible())

### FIXED CODE ###

from collections import defaultdict, Counter

def main():
  n, *A = map(int, open(0).read().split())
  A.sort()
  n = A[-1]
  isPrime = [True] * (n + 1)
  prep = 0
  for i in A:
    if prep == i:
      isPrime[prep] = False
      continue
    if isPrime[i]:
      for j in range(i * 2, n + 1, i):
        isPrime[j] = False
    prep = i

  prep = res = 0
  for i in A:
    if prep == i:
      continue
    if isPrime[i]:
      res += 1
    prep = i
  print(res)
if __name__ == '__main__':
  main()
### BUGGY CODE ###

import math
from functools import reduce
import itertools

limit_num = int(input())

def gcd(*numbers):
	return reduce(math.gcd, *numbers)

result = 0
result_list = []
for num in itertools.product(range(1, limit_num + 1), repeat=3):
	result_list.append(gcd(num))
print(sum(result_list))


### FIXED CODE ###

import math
from functools import reduce
import itertools

def gcd(*numbers):
	return reduce(math.gcd, *numbers)

limit_num = int(input())
result_list = []
for num in itertools.product(range(1, limit_num + 1), repeat=3):
	result_list.append(gcd(num))

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

import sys
read=sys.stdin.buffer.readline

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

L.sort()

def binary_tree(data,l_index,value):
    left=l_index
    right=N-2
    while left<=right:
        mid=(left+right)//2
        if data[mid]>=value and data[mid-1]<value:
            return mid-1
        elif data[mid]<value:
            left=mid+1
        else:
            right=mid-1
    if data[-1]<value:
        return N-1
    return -1

ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        x=binary_tree(L,j+1,L[i]+L[j])
        if x!=-1:
            ans+=(x-j)

print(ans)

### FIXED CODE ###

import sys
from bisect import bisect_left

read=sys.stdin.buffer.readline

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

L.sort()

ans=0
for i in range(N-2):
    for j in range(i+1,N-1):
        ans+=bisect_left(L,L[i]+L[j])-(j+1)

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

H,W = map(int, input().split())

#迷路の初期化
a = [[-1] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    s = input()
    for j in range(1,W+1):
        if s[j-1] == ".":
            a[i][j] = 0
        elif s[j-1] == "#":
            a[i][j] = -1
        else:
            print("ERROR")

#dpの初期化
dp_sum = [[0] * (W+2) for i in range(H+2)]
#step
#steplst =  [[] for i in range((H+W)+2)]
steplst =  [[]]
#stepdxy = [[1,0],[-1,0],[0,1],[0,-1]]
stepdxy = [[1,0],[0,1]]

def do_step(n):
    stepok = 0
    steplst.append([])
    if n == 1:
        x,y = 1,1
        a[x][y] = -9
        for dx,dy in stepdxy:
            if a[x+dx][y+dy] == 0 or a[x+dx][y+dy] == n:
                dp_sum[x+dx][y+dy] += 1
                a[x+dx][y+dy] = n
                steplst[n].append([x+dx,y+dy])
                stepok = 1
    else:
        for x,y in steplst[n-1]:
            for dx,dy in stepdxy:
                if a[x+dx][y+dy] == 0:
                    dp_sum[x+dx][y+dy] += dp_sum[x][y]
                    a[x+dx][y+dy] = n
                    steplst[n].append([x+dx,y+dy])
                    stepok = 1
                elif a[x+dx][y+dy] == n:
                    dp_sum[x+dx][y+dy] += dp_sum[x][y]
    return stepok

stepn = 1
while do_step(stepn) == 1:
    #for i in range(len(dp_sum)):
    #    print(dp_sum[i],a[i])
    stepn += 1

print(dp_sum[H][W] % (10**9+7))

### FIXED CODE ###

H,W = map(int, input().split())

#迷路の初期化
a = [[-1] * (W+2) for i in range(H+2)]
for i in range(1,H+1):
    s = input()
    for j in range(1,W+1):
        if s[j-1] == ".":
            a[i][j] = 0
        elif s[j-1] == "#":
            a[i][j] = -1
        else:
            print("ERROR")

#dpの初期化
dp_sum = [[0] * (W+2) for i in range(H+2)]
#step
stepdic = {}
#stepdxy = [[1,0],[-1,0],[0,1],[0,-1]]
stepdxy = [[1,0],[0,1]]

def do_step(n):
    stepok = 0
    if n == 1:
        x,y = 1,1
        a[x][y] = -9
        for dx,dy in stepdxy:
            if a[x+dx][y+dy] == 0 or a[x+dx][y+dy] == n:
                dp_sum[x+dx][y+dy] += 1
                a[x+dx][y+dy] = n
                stepdic.setdefault(n,[]).append([x+dx,y+dy])
                stepok = 1
    if n-1 in stepdic.keys():
        for x,y in stepdic[n-1]:
            for dx,dy in stepdxy:
                if a[x+dx][y+dy] == 0:
                    dp_sum[x+dx][y+dy] += dp_sum[x][y]
                    a[x+dx][y+dy] = n
                    stepdic.setdefault(n,[]).append([x+dx,y+dy])
                    stepok = 1
                elif a[x+dx][y+dy] == n:
                    dp_sum[x+dx][y+dy] += dp_sum[x][y]
    return stepok

stepn = 1
while do_step(stepn) == 1:
    stepn += 1

print(dp_sum[H][W] % (10**9+7))
### BUGGY CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

for i in range(K):
    if len(H) == 0:
        break
    ma = max(H)
    H.remove(ma)

ans = 0
for i in range(len(H)):
    ans += H[i]

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
H = list(map(int, input().split()))

if N <= K:
    print(0)
else:
    H = sorted(H)
    ans = 0
    for i in range(N-K):
        ans += H[i]
    print(ans)
### BUGGY CODE ###

import collections

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

s = sum([i*(i-1)//2 for i in collections.Counter(a).values()])

for j in a:
    print(s - a.count(j)+1)


### FIXED CODE ###

import collections

n = int(input())
a = list(map(int,input().split()))
d = collections.Counter(a)
s = sum([i*(i-1)//2 for i in d.values()])

for j in a:
    print(s-d[j]+1)
### BUGGY CODE ###

import numpy as np
n,m=map(int,input().split())
a=sorted([list(map(int,input().split()))for i in range(m)])
s=np.array([float("INF")]*(n+1))
s[1]=0
for i in range(m):
    if a[i][0]!=1 and s[a[i][0]]==0:
        print(-1)
        break
    else:
        s[a[i][0]:a[i][1]+1]=np.minimum(s[a[i][0]:a[i][1]+1],s[a[i][0]]+a[i][2])
if s[-1]!=float("INF"):
    print(int(s[-1]))
else:
    print(-1)

### FIXED CODE ###

from heapq import heappush,heappop
n,m=map(int,input().split())
a=[[[i-1,0]]for i in range(n+1)]
a[0]=[]
for i in range(m):
    l,r,c=map(int,input().split())
    a[l].append([r,c])
q=[float("INF")]*(n+1)
q[1]=0
c=[]
heappush(c,[0,1])
while c:
    s,t=heappop(c)
    if t==n:
        print(s)
        break
    for i,j in a[t]:
        if q[i]>s+j:
            q[i]=s+j
            heappush(c,[s+j,i])
else:
    print(-1)
### BUGGY CODE ###

import sys 
sys.setrecursionlimit(10**6)

def dfs(v, pv):
    # global P

    for nv in G[v]:
        if nv != pv:
            P[nv] += P[v]
            dfs(nv, v)

n,q = map(int, input().split())
G = [[] for _ in range(n)]              # adjacent list
for i in range(n-1):
    a,b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)

P = [0]*n                               # add list
for i in range(q):
    p,x = map(int, input().split())
    P[p-1] += x


dfs(0, 0)
print(*P)



### FIXED CODE ###

import sys
from operator import itemgetter #sortedの対象を決めたい
from fractions import gcd #最大公約数求めたい
from math import ceil, floor, sqrt #小数点切り上げ、切り捨て、平方根求めたい
from copy import deepcopy #参照で影響されないコピーが作られる
from collections import Counter, deque #要素ごとの出現回数を数える。双方向アクセス可能データ型
import heapq
from functools import reduce
sys.setrecursionlimit(200000)

input = sys.stdin.readline
# template


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

ct = [0] * (n+1)
o = [0] * (n+1)
g = [[] for _ in range(n+1)]

for i in range(n-1):
    a,b = map(int, input().split())
    g[a].append(b)
    g[b].append(a)

for i in range(q):
    p,x = map(int, input().split())
    o[p] += x

todo = [1]
seen = [False] * (n+1)
while todo:
    p = todo.pop(-1)
    ct[p] += o[p]
    seen[p] = True
    for i in g[p]:
        if seen[i]:
            ct[p] += ct[i]
        else:
            todo.append(i)

print(*ct[1:])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
a = []
count = 0
for i in range(N):
  temp = input()
  temp = list(temp)
  temp.sort()
  temp = "".join(temp)
  count += a.count(temp)
  a.append(temp)

print(int(count))

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
dic = {}
count = 0
for i in range(N):
  temp = "".join(sorted(input()))
  if temp in dic:
    count += dic[temp]
    dic[temp] += 1
  else:
    dic[temp] = 1

print(count)
### BUGGY CODE ###

import sys
import bisect
input = sys.stdin.readline

N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        l = L[j + 1:]
        index = bisect.bisect_left(l, L[i] + L[j])
        ans += index

print(ans)


### FIXED CODE ###

import sys
import bisect
input = sys.stdin.readline

N = int(input())
L = sorted(list(map(int, input().split())))
ans = 0
for i in range(N - 2):
    for j in range(i + 1, N - 1):
        index = bisect.bisect_left(L, L[i] + L[j])
        n = index - j - 1
        ans += n

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

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

for i in range(m):
  a.sort()
  t=int(a.pop(-1)/2)
  a.append(t)
print(sum(a))



### FIXED CODE ###

import heapq
N, M = list(map(int,input().split()))
h = []
for i in input().split():
  heapq.heappush(h,-int(i))
for i in range(M):
  x = -heapq.heappop(h)
  x //=2
  heapq.heappush(h,-x)
print(-sum(h))
### BUGGY CODE ###

# C - Reconciled?
N, M = map(int,input().split())

S = 1
for i in range(1,min(N,M)+1):
    S *= i % 1000000007

ans = 0
if abs(N-M) > 1:
    ans = 0
elif abs(N-M) == 1:
    ans = S*S*max(N,M)
else:
    ans = S*S*2

ans = ans % 1000000007

print(ans)


### FIXED CODE ###

# C - Reconciled?
import math
N, M = map(int,input().split())

S = math.factorial(min(N,M)) % 1000000007

ans = 0
if abs(N-M) > 1:
    ans = 0
elif abs(N-M) == 1:
    ans = S*S*max(N,M)
else:
    ans = S*S*2

ans = ans % 1000000007

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

# -*- coding: utf-8 -*-
import itertools

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

Nlst = []
# for i in range(1,N+1):
#     Nlst.append(i)

if K % 2 == 0:
    for i in range(1,N+1):
        if i % K == 0 or i % (K/2) == 0:
            Nlst.append(i)
else:
    for i in range(1,N+1):
        if i % K == 0:
            Nlst.append(i)

tmplst = []
for i in itertools.product(Nlst, repeat=3):
    tmplst.append(i)

ans = 0

for (a,b,c) in tmplst:
    if (a+b) % K == 0 and (b+c) % K == 0 and (c+a) % K == 0:
        ans += 1


print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
import itertools

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

Nlst = []
Nlst_gu = []
# for i in range(1,N+1):
#     Nlst.append(i)

if K % 2 == 0:
    for i in range(1,N+1):
        if i % K == 0:
            Nlst.append(i)
        elif i % (K/2) == 0:
            Nlst_gu.append(i)
else:
    for i in range(1,N+1):
        if i % K == 0:
            Nlst.append(i)
#
# print(Nlst)
# print(Nlst_gu)

ans = len(Nlst)
ans_gu = len(Nlst_gu)

print(ans * ans * ans + ans_gu * ans_gu * ans_gu)

#
# tmplst = []
# for i in itertools.product(Nlst, repeat=3):
#     tmplst.append(i)
#
# ans = 0
#
# for (a,b,c) in tmplst:
#     if (a+b) % K == 0 and (b+c) % K == 0 and (c+a) % K == 0:
#         ans += 1
#
#
# print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
A.sort()
count=0
now=0
for i in range (N):
    if A[i]==now:
        pass
    elif A.count(A[i])>A[i]:
        count+=A.count(A[i])-A[i]
    elif A.count(A[i])<A[i]:
        count+=A.count(A[i])
    now=A[i]
print(count)

### FIXED CODE ###

N=int(input())
list=list(map(int,input().split()))
while len(list) != 0and max(list) > len(list):
    list = [i for i in list if i < len(list)]
#list2 = [i for i in list if i < N]
set = set(list)
cnt=0
for i in set:
    c=list.count(i)
    if c > i:
        cnt +=c-i
    elif c < i:
        cnt +=c
print(N-len(list)+cnt)

##できなかった．
### BUGGY CODE ###

S = list(input())
Q = int(input())

for _ in range(Q):
    q = input()
    if q == "1":
        S.reverse()
    else:
        _, t, c = q.split()
        if t == "1":
            S.insert(0, c)
        else:
            S.append(c)

print("".join(S))


### FIXED CODE ###

from collections import deque

S = list(input())
d = deque(S)
Q = int(input())

flag = 0
for _ in range(Q):
    q = input()
    if q == "1":
        flag += 1
    else:
        _, t, c = q.split()
        if flag % 2 == 0:
            if t == "1":
                d.appendleft(c)
            else:
                d.append(c)
        else:
            if t == "2":
                d.appendleft(c)
            else:
                d.append(c)

if flag % 2 == 1:
    d.reverse()
print("".join(list(d)))
### BUGGY CODE ###

from math import factorial
from itertools import combinations

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

def comb(n,r):
    return factorial(n)//(factorial(n-r) * factorial(r))

res = []
for i in A[1:]:
    res.append([comb(A[0],i),A[0],i])

res.sort(reverse=True)

print(res[0][1],res[0][2])

### FIXED CODE ###

n = int(input())
A = sorted(list(map(int,input().split())),reverse=True)
k = 10**10
for i in range(1,n):
    k = min(k,abs(A[0]/2 -A[i]))
    if k == abs(A[0]/2 -A[i]):
        ans = [A[0],A[i]]
print(ans[0],ans[1])
### BUGGY CODE ###

import decimal
from itertools import permutations


def distance(a, b):
  return decimal.Decimal(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2)).sqrt()


N = int(input())

P = [None] * N
for i in range(N):
  P[i] = tuple(map(int, input().split()))

total = decimal.Decimal(0)
count = 0
for points in permutations(P, len(P)):
  it = iter(points)
  last = next(it)
  for p in it:
    total += distance(p, last)
    last = p
  count += 1

print(total / count)


### FIXED CODE ###

import decimal
import math
from itertools import permutations

decimal.getcontext().prec = 16

cache = {}


def distance(a, b):
  return math.sqrt(pow(a[0] - b[0], 2) + pow(a[1] - b[1], 2))


N = int(input())

P = [None] * N
for i in range(N):
  P[i] = tuple(map(int, input().split()))

total = 0
count = 0
for points in permutations(P, len(P)):
  it = iter(points)
  last = next(it)
  for p in it:
    total += distance(p, last)
    last = p
  count += 1

print(total / count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
D - Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d

"""
import sys


from collections import OrderedDict, deque

def main(args):
    N = int(input())
    G = [[] for _ in range(N+1)]
    res = OrderedDict()
    for _ in range(N-1):
        a, b = map(int, input().split())
        res[(a, b)] = -1
        G[a].append(b)
        G[b].append(a)

    k = max(len(g) for g in G)
    colors = [set(range(1, k+1)) for _ in range(N+1)]
    q = deque([1])
    visited = set([1])
    while q:
        cn = q.popleft()
        for nn in G[cn]:
            if nn not in visited:
                visited.add(nn)
                q.append(nn)
                c = min(colors[cn])
                colors[cn].discard(c)
                colors[nn].discard(c)
                if (cn, nn) in res:
                    res[(cn, nn)] = c
                if (nn, cn) in res:
                    res[(nn, cn)] = c
    print(k)
    for v in res.values():
        print(v)


if __name__ == '__main__':
    main(sys.argv[1:])


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
D - Coloring Edges on Tree
https://atcoder.jp/contests/abc146/tasks/abc146_d

"""
import sys


from collections import OrderedDict, deque

def main(args):
    N = int(input())
    G = [[] for _ in range(N+1)]
    res = OrderedDict()
    for _ in range(N-1):
        a, b = map(int, input().split())
        res[(a, b)] = -1
        G[a].append(b)
        G[b].append(a)

    k = max(len(g) for g in G)
    colors = [0 for _ in range(N+1)]
    q = deque([1])
    visited = set([1])
    while q:
        cn = q.popleft()
        color = 1
        for nn in G[cn]:
            if nn not in visited:
                if color == colors[cn]:
                    color += 1
                visited.add(nn)
                q.append(nn)
                c = color
                colors[nn] = color
                color += 1
                if (cn, nn) in res:
                    res[(cn, nn)] = c
                if (nn, cn) in res:
                    res[(nn, cn)] = c
    print(k)
    for v in res.values():
        print(v)


if __name__ == '__main__':
    main(sys.argv[1:])
### BUGGY CODE ###

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

def kouyaku(n,p):
    if n==1:
        return p
    else:
        for i in range(round((p/n)+1),0,-1):
            if p%(i**n)==0:
                return i
            
print(kouyaku(n,p))

### FIXED CODE ###

N, P = map(int, input().split())
ans = 1
 
if N >= 45:
  print(ans)
elif N == 1:
  print(P)
  
 
  
else:
  i = 1
  while(i**N <= P):
    if P % (i**N) == 0:
      ans = i
    i += 1
  print(ans)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 1
b = 1
c = 1
p = 10**18
for i in range(N):
  if A[i] == 0:
    c = 0
    break
  else:
    ans *= A[i]
    if p < ans:
      b = -1
if c == 0:
  print(c)
elif b == -1:
  print(b)
else:
  print(ans)
    
  

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
n0 = A.count(0)
n1 = A.count(1)
import math
ans = 1
if N-n0-n1>60:
  ans = -1
for i in range(N):
  if A[i] == 0 or ans == 0:
    ans = 0
    break
  elif ans <0:
    ans = -1
  elif math.log10(A[i])+math.log10(ans)>18:
    ans = -1
    b = 1
  else:
    ans *= A[i]

if ans == 0:
  print(0)
elif ans < 0:
  print(-1)
elif ans>10**18:
  print(-1)
else:
  print(ans)