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

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())
    N, K = next(it), next(it)
    A = [next(it) for i in range(N)]

    for k in range(K):
        B = [0]*N
        for i, di in enumerate(A):
            for j in range(max(0, i-di), min(i+di+1,N)):
                B[j] += 1
        A = B
        if all(a == N for a in A):
            break
    print(*A)

if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
from itertools import accumulate

def resolve():
    it = map(int, sys.stdin.read().split())
    N, K = next(it), next(it)
    A = [next(it) for i in range(N)]

    for k in range(K):
        B = [0]*(N+1)
        for i, di in enumerate(A):
            lhs = max(0, i-di)
            rhs = min(i+di+1, N)

            B[lhs] += 1
            B[rhs] -= 1

        if B[0] == N:
            print(*[N]*N)
            return
        A = accumulate(B)

    print(*list(A)[:-1])

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

import sys
from collections import deque
sys.setrecursionlimit(100000)
input = sys.stdin.readline

N, A, B, C, D = list(map(int, input().split()))
S = input()

def able(m, n, S):
    for i in range(m+1, n):
        if S[i] == '#' and S[i+1] == '#':
            return False
    return True

def able2(m, n, S):
    for i in range(m, n):
        if not able(m, n, S):
            return False
        if S[i] == '.' and S[i-1] == '.' and S[i+1] == '.':
            return True
    return False

if C>D:
    if able(A-1, C-1, S) and able2(B-1, D-1, S):
        print("Yes")
    else:
        print("No")
else:
    if able(A-1, C-1, S) and able(B-1, D-1, S):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import sys
from collections import deque
sys.setrecursionlimit(100000)
input = sys.stdin.readline

N, A, B, C, D = list(map(int, input().split()))
S = input()

def able(m, n, S):
    for i in range(m+1, n):
        if S[i] == '#' and S[i+1] == '#':
            return False
    return True

def able2(m, n, S):
    if not able(m, n, S):
        return False
    for i in range(m, n+1):
        if S[i] == '.' and S[i-1] == '.' and S[i+1] == '.':
            return True
    return False

if C>D:
    if able(A-1, C-1, S) and able2(B-1, D-1, S):
        print("Yes")
    else:
        print("No")
else:
    if able(A-1, C-1, S) and able(B-1, D-1, S):
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import sys
h,w,m = map(int, input().split())
h_t = []
w_t = []
s = []
for i1 in range(h):
  h_t.append(0)
for i2 in range(w):
  w_t.append(0)
for i in range(h):
  s.append([])
  for j in range(w):
    s[i].append(0)
for i3 in range(m):
  hi,wi = map(int, input().split())
  h_t[hi-1] += 1
  w_t[wi-1] += 1
  s[hi-1][wi-1] = 1
hmax = max(h_t)
wmax = max(w_t)
hmaxi = [i for i, v in enumerate(h_t) if v == max(h_t)]
wmaxi = [i for i, v in enumerate(w_t) if v == max(w_t)]
for ht in hmaxi:
  for wt in wmaxi:
    if s[ht][wt] == 0:
      print(hmax + wmax)
      sys.exit()
print(hmax + wmax-1)


### FIXED CODE ###

import sys
h,w,m = map(int, input().split())
h_t = [0 for _ in range(h)]
w_t = [0 for _ in range(w)]
t = []
for _ in range(m):
  hi,wi = map(int, input().split())
  h_t[hi-1] += 1
  w_t[wi-1] += 1
  t.append([hi-1,wi-1])
hmax = max(h_t)
wmax = max(w_t)
hmaxi = [i1 for i1 in range(h) if h_t[i1] == hmax]
wmaxi = [i2 for i2 in range(w) if w_t[i2] == wmax]
c = len(hmaxi)*len(wmaxi)
d = 0
for ht,wt in t:
  if h_t[ht] == hmax:
    if w_t[wt] == wmax:
      d += 1
if c ==d:
  print(hmax + wmax-1)
else:
  print(hmax + wmax)
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline
from collections import deque
def solve():
  
  n,m = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  a.sort()
  tmp = deque([])
  for i in range(m):
    l,r = (int(i) for i in input().split())
    tmp.append((l,r))
  tmp= deque(sorted(tmp,key=lambda tmp: tmp[1],reverse =True))
  ans = 0
  while tmp:
    b,c = tmp.popleft()
    place = bisect.bisect_left(a,c)-1
    if place == -1:
      break
    else:
        if len(a) == 0:
           break
        a = a[min(1+place,b)::]
        ans += c*(min(1+place,b))
    #print(a)
  if a:
   ans += sum(a)
  print (ans)
solve()

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline
from collections import deque
def solve():
  
  n,m = (int(i) for i in input().split())
  a = list(int(i) for i in input().split())
  a = deque(sorted(a))
  tmp = deque([])
  for i in range(m):
    r,l = (int(i) for i in input().split())
    tmp.append((l,r))
  tmp= deque(sorted(tmp,reverse =True))
  ans = 0
  while tmp:
    c,b = tmp.popleft()
    place = bisect.bisect_left(a,c)-1
    if place == -1:
      break
    else:
        if len(a) == 0:
           break
        for i in range(min(1+place,b)):
           a.popleft()
        ans += c*(min(1+place,b))
    #print(a)
  if a:
   ans += sum(a)
  print (ans)
solve()
### BUGGY CODE ###

N = int(input())
import sys
sys.setrecursionlimit(10000000)
MOD = 10**9+7
E = {}
for i in range(0,N):
    E[i] = []
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    E[a].append(b)
    E[b].append(a)

dp = [ [0 for i in range(2)] for j in range(100100)]

def dfs(c,p):
    dp[c][0],dp[c][1] = 1,1
    for to in E[c]:
        if to != p:
            dfs(to,c)
            dp[c][0] *= dp[to][0] + dp[to][1]
            dp[c][1] *= dp[to][0]
            dp[c][0] %= MOD
            dp[c][1] %= MOD

dfs(0,-1)

ans = (dp[0][0] + dp[0][1]) % MOD
print(ans)


### FIXED CODE ###

from heapq import heappush, heappop
import collections
import math
import heapq
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)
MOD = 10 ** 9 + 7
inf = float("inf")


def main():
    N = int(input())
    E = {}
    for i in range(0, N+1):
        E[i] = []
    for i in range(N-1):
        a, b = map(int, input().split())
        a -= 1
        b -= 1
        E[a].append(b)
        E[b].append(a)

    dp = [[0 for i in range(2)] for j in range(100100)]

    def dfs(c, p):
        dp[c][0], dp[c][1] = 1, 1
        for to in E[c]:
            if to != p:
                dfs(to, c)
                dp[c][0] *= dp[to][0] + dp[to][1]
                dp[c][1] *= dp[to][0]

    dfs(0, -1)

    ans = (dp[0][0] + dp[0][1]) % MOD
    print(ans)


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

#H=4
#W=6
#
#S[0]=["#",".",".","#",".","."]
#S[1]=[".",".",".",".",".","#"]
#S[2]=[".",".",".",".","#","."]
#S[3]=["#",".","#",".",".","."]

H,W=map(int,input().split())
S=[0]*H
for i in range(H):
    S[i]=list(input())


MAP=[[[0,0,0,0] for i in range(W)]for i in range(H)]
#MAP[H][W]

#ue
for i in range(W):
    c=0
    for j in range(H):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
        else:
            c=0

#shita
for i in range(W):
    c=0
    for j in range(H-1,-1,-1):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
        else:
            c=0

#hidari
for j in range(H):
    c=0
    for i in range(W):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
        else:
            c=0

#migi
MAX=0
for j in range(H):
    c=0
    for i in range(W-1,-1,-1):
        if(S[j][i]=="."):
            c+=1
            MAP[j][i][0]+=c
        else:
            c=0
        MAX=max(MAX,MAP[j][i][0]-3)

print(MAX)

### FIXED CODE ###

#H=4
#W=6
#
#S[0]=["#",".",".","#",".","."]
#S[1]=[".",".",".",".",".","#"]
#S[2]=[".",".",".",".","#","."]
#S[3]=["#",".","#",".",".","."]

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

S = [[0]*W for i in range(H)]

for i in range(H):
    T=list(input())
    for j in range(W):
        if T[j] == "#":
            S[i][j] = 0
        else:
            S[i][j] = 1
MAP=[[0]*(W+2) for i in range(H+2)]
MAPH=[[0]*(W+2) for i in range(H+2)]
MAPU=[[0]*(W+2) for i in range(H+2)]
MAPL=[[0]*(W+2) for i in range(H+2)]
MAPR=[[0]*(W+2) for i in range(H+2)]

MAX=0

for i in range(1,W+1):
    for j in range(1,H+1):
            MAPH[j][i]=(MAPH[j-1][i]+1)*S[j-1][i-1]
            MAP[j][i]+=MAPH[j][i]
            MAPU[H-j+1][W-i+1]=(MAPU[H-j+2][W-i+1]+1)*S[H-j][W-i]
            MAP[H-j+1][W-i+1]+=MAPU[H-j+1][W-i+1]
for j in range(1,H+1):
    for i in range(1,W+1):
            MAPL[j][i]=(MAPL[j][i-1]+1)*S[j-1][i-1]
            MAP[j][i]+=MAPL[j][i]
            MAPR[H-j+1][W-i+1]=(MAPR[H-j+1][W-i+2]+1)*S[H-j][W-i]
            MAP[H-j+1][W-i+1]+=MAPR[H-j+1][W-i+1]
            MAX=max(MAX,MAP[j][i]-3,MAP[H-j+1][W-i+1]-3)
print(MAX)
### BUGGY CODE ###

N = int(input())
power = 1
for i in range(1, N+1):
    power *= i
print(power % (10**9+7))


### FIXED CODE ###

from math import factorial as F
N = int(input())
print(F(N) % (10**9+7))
### BUGGY CODE ###

s=input()
k=int(input())

lis=[]
for i in range(len(s)):
    for j in range(i,len(s)):
        lis.append(s[i:j+1])
lis=set(lis)
lis=list(lis)
lis.sort()

print(lis[k-1])

### FIXED CODE ###

s=input()
k=int(input())

lis=[]
for i in range(len(s)):
    lis.append(s[i:i+5])
    lis.sort()

l=[]
for i in lis[:5]:
    for j in range(5):
        l.append(i[:j+1])

l=set(l)
l=list(l)

l.sort()

print(l[k-1])
### BUGGY CODE ###

N,K = list(map(int,input().split()))
A = list(map(int,input().split()))
if K >= 40:
    ans = [N]*N
    print(*ans)
else:
    for i in range(K):
        CA = [0]*N
        for j in range(N):
            CA[max(0,j-A[j]):min(j+A[j]+1,N)] = map(lambda x: x+1,CA[max(0,j-A[j]):min(j+A[j]+1,N)])
        A = [CA[i] for i in range(N)]
    print(*A)


### FIXED CODE ###

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

for k in range(1,min(K+1,45)):
    B = [0]*N
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1,i+A[i])
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
            
    for i in range(1,N):
        B[i] += B[i-1]
    A = B
print(*A)
### BUGGY CODE ###

from collections import defaultdict


def solve(n, cards):
    dp = {(1 << n) - 1: {0: 0}}
    for d in range(n):
        ndp = defaultdict(lambda: defaultdict(lambda: 1000000))
        for state, scores in dp.items():
            k = state
            curr = 0
            while k:
                b = k & -k
                i = b.bit_length() - 1
                num = cards[i][(d - i) % 2]
                for score, left_num in scores.items():
                    if left_num > num:
                        continue
                    ndp[state ^ b][score + curr] = min(ndp[state ^ b][score + curr], num)
                k ^= b
                curr += 1
        if len(ndp) == 0:
            return -1
        dp = ndp
    return min(dp[0].keys())


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cards = list(zip(aaa, bbb))
print(solve(n, cards))


### FIXED CODE ###

def iter_bit(k, LIMIT):
    v = (1 << k) - 1

    while v < LIMIT:
        yield v
        x = v & -v
        y = v + x
        v = (v & ~y) // x >> 1 | y


def solve(n, cards):
    dp = [{} for _ in range(1 << n)]
    dp[-1][0] = 0
    LIMIT = 1 << n

    for d in range(n):
        for state in iter_bit(n - d, LIMIT):
            scores = dp[state]
            k = state
            curr = 0
            while k:
                b = k & -k
                i = b.bit_length() - 1
                num = cards[i][(d - i) % 2]
                next_dp = dp[state ^ b]
                for left_num, score in scores.items():
                    if left_num > num:
                        continue
                    ns = score + curr
                    if num not in next_dp or next_dp[num] > ns:
                        next_dp[num] = ns
                k ^= b
                curr += 1

    if len(dp[0]) > 0:
        return min(dp[0].values())
    else:
        return -1


n = int(input())
aaa = list(map(int, input().split()))
bbb = list(map(int, input().split()))
cards = list(zip(aaa, bbb))
print(solve(n, cards))
### BUGGY CODE ###

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

ans = 1
for i in a:
    ans *= i
if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    result = 1
    if 0 in A:
        print(0)
        return

    for i in A:
        result *= i
        if result > 10**18:
            print(-1)
            return
    print(result)

main()
### BUGGY CODE ###

n_dice, n_choice = map(int, input().split())
dice_list = tuple(map(int, input().split()))
sumofarea_list = (sum(dice_list[i:i+n_choice]) for i in range(n_dice - n_choice + 1))
print(max(sumofarea_list)/2 + n_choice / 2)

### FIXED CODE ###

import itertools

n, k = map(int, input().split())
dices = map(int, input().split())
dices_EV = list(map(lambda x:(x+1)/2, dices))
dices_EV_accumulate = list(itertools.accumulate(dices_EV))
dices_EV_sums = [dices_EV_accumulate[i+k] - dices_EV_accumulate[i] for i in range(n-k)]
dices_EV_sums.append(dices_EV_accumulate[k-1])
print(max(dices_EV_sums))
### BUGGY CODE ###

# dp[i][j] := Aをiグラム、Bをjグラムちょうど買うための最小予算。
# i <= N * a_i <= 40*10=400
# j <= N * b_i <= 40*10=400
# ……だとダメだわ。マスの遷移が許されるかどうかの情報が入ってない。
# （ある薬品を2回使うことはできないから、薬品を買ったか否かの情報を入れなきゃいけない）
# dp[k][i][j] := k番目までの薬品を使って、Aをiグラム、Bをjグラムちょうど買うための最小予算。
# 40*400*400で、各マスの計算は2個のマスを参照すれば求まるから、
# 40*400*400*2 = 12800000 = 1280万 間に合う。

n, a_ratio, b_ratio = list(map(int, input().split()))
chemicals = [list(map(int, input().split())) for _ in range(n)]

inf = 10 ** 10
ab_max = 10
dp = [[[inf for j in range(n * ab_max + 1)] for i in range(n * ab_max + 1)] for k in range(n)]

dp[0][0][0] = 0
dp[0][chemicals[0][0]][chemicals[0][1]] = chemicals[0][2]

for k in range(1, n):
    for i in range(n * ab_max + 1):
        for j in range(n * ab_max + 1):
            if i-chemicals[k][0] >= 0 and j-chemicals[k][1] >= 0:
                dp[k][i][j] = min(dp[k-1][i][j],  dp[k-1][i-chemicals[k][0]][j-chemicals[k][1]] + chemicals[k][2])
            else:
                dp[k][i][j] = dp[k-1][i][j]

ans = inf
bai = 1
while(a_ratio * bai <= n * ab_max and b_ratio * bai <= n * ab_max):
    ans = min(ans, dp[n-1][a_ratio * bai][b_ratio * bai])
    bai += 1

if ans < inf:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

# dp[i][j] := Aをiグラム、Bをjグラムちょうど買うための最小予算。
# i <= N * a_i <= 40*10=400
# j <= N * b_i <= 40*10=400
# ……だとダメだわ。マスの遷移が許されるかどうかの情報が入ってない。
# （ある薬品を2回使うことはできないから、薬品を買ったか否かの情報を入れなきゃいけない）
# dp[k][i][j] := k番目までの薬品を使って、Aをiグラム、Bをjグラムちょうど買うための最小予算。
# 40*400*400で、各マスの計算は2個のマスを参照すれば求まるから、
# 40*400*400*2 = 12800000 = 1280万 間に合う。

n, a_ratio, b_ratio = list(map(int, input().split()))
chemicals = [list(map(int, input().split())) for _ in range(n)]

inf = 10 ** 10
ab_max = 10
dp = [[[inf for j in range(n * ab_max + 1)] for i in range(n * ab_max + 1)] for k in range(n)]

dp[0][0][0] = 0
dp[0][chemicals[0][0]][chemicals[0][1]] = chemicals[0][2]

for k in range(1, n):
    for i in range(n * ab_max + 1):
        for j in range(n * ab_max + 1):
            if i-chemicals[k][0] >= 0 and j-chemicals[k][1] >= 0:
                dp[k][i][j] = min(dp[k-1][i][j],  dp[k-1][i-chemicals[k][0]][j-chemicals[k][1]] + chemicals[k][2])
            else:
                dp[k][i][j] = dp[k-1][i][j]

ans = inf
bai = 1
while(a_ratio * bai <= n * ab_max and b_ratio * bai <= n * ab_max):
    ans = min(ans, dp[n-1][a_ratio * bai][b_ratio * bai])
    bai += 1

if ans < inf:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

N, X, Y= map(int, input().split()) 
Count = []
for i in range(N-1):
  Count.append(0)
  
for k in range(1, N):
  for i in range(1, N):
    for j in range(i+1, N+1):
      if (j-i > k) & ((abs(i-X) +abs(j-Y) +1)>k) & ((abs(i-X) +abs(j+1-Y) +1 )>(abs(i-X) +abs(j-Y) +1)>k):
        break
      if j-i <= (abs(i-X) +abs(j-Y) +1):
        if j-i == k:
          Count[k-1] = Count[k-1]+1
      else:
        if (abs(i-X) +abs(j-Y) +1) == k:
          Count[k-1] = Count[k-1]+1

for i in range(N-1):
  print(Count[i])

### FIXED CODE ###

N, X, Y= map(int, input().split()) 
Count = [0]*(N-1)
  

for i in range(1, N):
  for j in range(i+1, N+1):
    Count[min(j-i, (abs(i-X) +abs(j-Y) +1),  (abs(i-Y) +abs(j-X) +1))-1] += 1

for i in range(N-1):
  print(Count[i])
### BUGGY CODE ###

import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
      
def fun(S1,S2,n,m):
    if n == 0 or m == 0:
        return ""
    dp = list2d(n+1,m+1,"")
    for i in range(1,n+1):
        for j in range(1,m+1):
            if S1[i-1] == S2[j-1]:
                dp[i][j] = S1[i-1] + dp[i-1][j-1]
            else:
                a = dp[i-1][j]
                b = dp[i][j-1]
                if len(a) > len(b):
                    dp[i][j] = a
                else:
                    dp[i][j] = b
    return dp[n][m][::-1]
    

S1 = input()
S2 = input()
n = len(S1)
m = len(S2)
print(fun(S1,S2,n,m))

### FIXED CODE ###

import math,sys,bisect,heapq
from collections import defaultdict,Counter,deque
from itertools import groupby,accumulate
#sys.setrecursionlimit(200000000)
input = iter(sys.stdin.buffer.read().decode().splitlines()).__next__
ilele = lambda: map(int,input().split())
alele = lambda: list(map(int, input().split()))
def list2d(a, b, c): return [[c] * b for i in range(a)]
#def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
MOD = 1000000000 + 7
def Y(c):  print(["NO","YES"][c])
def y(c):  print(["no","yes"][c])
def Yy(c):  print(["No","Yes"][c])
      
def fun(A,B,m,n,dp):
    for i in range(1,m+1):
        for j in range(1,n+1):
            if A[i-1] == B[j-1]:
                dp[i][j] = 1 + dp[i-1][j-1]
            else:
                dp[i][j] = max(dp[i][j-1],dp[i-1][j])
    return dp
                
def longestsub(A,B):
    m = len(A)
    n = len(B)
    if m==0 or n==0:
        return ""
    temp = [0]*(n+1)
    dp = [temp.copy() for i in range(m+1)]
    d = fun(A,B,m,n,dp)
    i= m;j = n;Ans = ""
    while i>0 and j>0:
        if A[i-1] == B[j-1]:
            Ans += A[i-1]
            i-=1;j-=1
        else:
            a = d[i][j-1] ; b =d[i-1][j]
            if a > b:
                j-=1
            else:
                i-=1
    return Ans[::-1]

A = input()
B = input()
print(longestsub(A,B))
### BUGGY CODE ###

import sys

def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,K = MI()
A = LI()
A.sort()


def f(n):  # Anが必要か否か
    B = [0] + [A[i] for i in range(N) if i != n]
    dp = [[0]*K for _ in range(2)]  # dp[i][j] = B1~Biを用いてjを作れるか(メモリ節約のため工夫してる)
    dp[0][0] = 1
    for i in range(1,N):
        b = B[i]
        if i % 2 == 1:
            for j in range(K):
                if j >= b:
                    dp[1][j] = dp[0][j] | dp[0][j-b]
                else:
                    dp[1][j] = dp[0][j]
        else:
            for j in range(K):
                if j >= b:
                    dp[0][j] = dp[1][j] | dp[1][j-b]
                else:
                    dp[0][j] = dp[1][j]
    if sum(dp[(N-1) % 2 == 1][j] for j in range(max(K-A[n],0),K)) != 0:
        return True
    else:
        return False


left = -1  # 不必要
right = N  # 必要
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid

print(right)


### FIXED CODE ###

import sys

def MI(): return map(int,sys.stdin.readline().rstrip().split())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))  #空白あり


N,K = MI()
A = LI()
A.sort()


def f(n):  # Anが必要か否か
    B = [0] + [A[i] for i in range(N) if i != n]
    dp = [[0]*K for _ in range(2)]  # dp[i][j] = B1~Biを用いてjを作れるか(メモリ節約のため工夫してる)
    dp[0][0] = 1
    for i in range(1,N):
        b = B[i]
        for j in range(K):
            if j >= b:
                dp[i%2][j] = dp[1-i%2][j] | dp[1-i%2][j-b]
            else:
                dp[i%2][j] = dp[1-i%2][j]
    if sum(dp[(N-1) % 2][j] for j in range(max(K-A[n],0),K)) != 0:
        return True
    else:
        return False


left = -1  # 不必要
right = N  # 必要
while left + 1 < right:
    mid = (left + right)//2
    if f(mid):
        right = mid
    else:
        left = mid

print(right)
### BUGGY CODE ###

def score(D,c,s,t):
    v=list()
    last=[0]*26
    legacy=0
    for i in range(D):
        minus=0
        v.append(legacy)
        v[i]+=s[i][t[i]-1]
        last[t[i]-1]=i+1
        for j in range(26):
            minus+=c[j]*(i+1-last[j])
        v[i]-=minus
        legacy=v[i]
    return v[D-1]
s=list()
t=list()
D=int(input())
c=list(map(int,input().split()))
for i in range(D):
    s.append(list(map(int,input().split())))
for i in range(D):
    t.append(1)
    max=score(i+1,c,s,t)
    best=1
    for j in range(1,26):
        t[i]=j+1
        tensuu=score(i+1,c,s,t)
        if max<tensuu:
            best=j+1
            max=tensuu
    t[i]=best
for i in range(D):
    print(t[i])

### FIXED CODE ###

import random
def score(D,c,s,t):
    v=list()
    last=[0]*26
    legacy=0
    for i in range(D):
        minus=0
        v.append(legacy)
        v[i]+=s[i][t[i]-1]
        last[t[i]-1]=i+1
        for j in range(26):
            minus+=c[j]*(i+1-last[j])
        v[i]-=minus
        legacy=v[i]
    return v[D-1]
s=list()
t=list()
D=int(input())
c=list(map(int,input().split()))
for i in range(D):
    s.append(list(map(int,input().split())))
t=[random.randint(1,26)]*D
for i in range(100):
    d=random.randint(1,D)
    q=random.randint(1,26)
    old=t[d-1]
    oldscore=score(D,c,s,t)
    t[d-1]=q
    if score(D,c,s,t)<oldscore:
        t[d-1]=old
for i in range(D):
    print(t[i])
### BUGGY CODE ###

N = int(input())
S = input()
for x in range(N):
    if x == 0:
        ans = S.count(".")
        continue
    count = S[:x].count("#") + S[x:].count(".")
    if count < ans:
        ans = count
count = S.count("#")
if count < ans:
    ans = count
print(ans)

### FIXED CODE ###

N = int(input())
S = input()
LB = 0
RW = S.count(".")
ans = LB +RW
for x in range(N):
    if S[x] == "#":
        LB += 1
    else:
        RW -= 1
    count = LB +RW
    if count < ans:
        ans = count
print(ans)
### BUGGY CODE ###

import numpy as np

N,M = list(map(int,input().split()))
A = np.array([int(i) for i in input().split()])

for i in range(M):
  #print(A)
  idx = np.argmax(A)
  A[idx] //= 2

print(np.sum(A))


### FIXED CODE ###

import heapq

N,M = list(map(int,input().split()))
A_tmp = [int(i) for i in input().split()]

#print(A_tmp)
A = [-i for i in A_tmp]

heapq.heapify(A)
#print(A)

for i in range(M):
  tmp = heapq.heappop(A)
  heapq.heappush(A, -(-tmp // 2))
  #print(A)

print(-sum(A))
### BUGGY CODE ###

N = int(input())
l = [int(x) for x in input().split()]
ans = 1
for i in range(N):
  ans *= l[i]
if ans > pow(10, 18):
  print(-1)
else:
  print(ans)

### FIXED CODE ###

import sys

N = int(input())
l = [int(x) for x in input().split()]
if 0 in l:
  print(0)
  sys.exit()
ans = 1
for i in range(N):
  if ans > pow(10, 18):
    ans = -1
    break
  else:
    ans *= l[i]
if ans > pow(10, 18):
  print(-1)
else:
  print(ans)