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

from functools import lru_cache
import sys
input = sys.stdin.readline


@lru_cache(None)
def int_bitmap(n: int, size=32) -> list:
    table = [0] * size
    for i in range(size):
        table[i] = (n >> i) & 1
    return table


def add_array(A: list, B: list) -> list:
    if len(A) != len(B):
        return -1
    else:
        return [a + b for a, b in zip(A, B)]


def sub_array(A: list, B: list) -> list:
    if len(A) != len(B):
        return -1
    else:
        return [a - b for a, b in zip(A, B)]


def bin_search(A, start, end):
    left, right = start, end
    while left < right:
        mid = (left + right) // 2
        if max(sub_array(A[end], A[mid])) < 2:  # midが条件を満たすとき、左をmidに置き換える
            right = mid
        elif max(sub_array(A[end], A[mid])) > 1:  # midを満たさないとき、左をmidに置き換える
            left = mid + 1
    return left


n = int(input())
_A = [int_bitmap(int(i), 20) for i in input().split()]

cusum = [None]
cusum[0] = int_bitmap(int(0), 20)

ans = 0

# pre-processsing for cul_sum
for i in range(1, n + 1):
    cusum.append(add_array(cusum[i - 1], _A[i - 1]))

for i in range(1, n + 1):

    if max(cusum[i]) < 2:
        ans += i
    # 右端をiとしたときに条件を満たす最長区間を２分探索する
    else:
        p = bin_search(cusum, 0, i)
        ans += (i - p)

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


n = int(input())
A = [int(i) for i in input().split()]
_sum = 0
_xor = 0
l, r = 0, 0
ans = 0
while l < n:
    while r < n and _sum + A[r] == _xor ^ A[r]:
        _sum += A[r]
        _xor ^= A[r]
        r += 1
    ans += r - l
    _sum -= A[l]
    _xor ^= A[l]
    if l == r:
        r += 1
    l += 1

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

# -- coding: utf-8 --
import math
N, H = map(int, input().split())
sl = []
th = []
for i in range(N):
    s, t = map(int, input().split())
    sl.append(s)
    th.append(t)
turn = 0
thm = list(filter(lambda x:x>max(sl), th))
thdec = sorted(th, reverse=True)

if sum(thdec) >= H:
    for i in range(len(thdec)):
        if sum(thdec[:i+1]) >= H:
            turn = i + 1
            break
else:
    turn = math.ceil((H - sum(thm)) / max(sl)) + len(thm)

print(turn)

### FIXED CODE ###

# -- coding: utf-8 --
import math
N, H = map(int, input().split())
th = []
sl_max = 0
for i in range(N):
    s, t = map(int, input().split())
    sl_max = max(sl_max, s)
    th.append(t)
turn = 0
thdec = sorted(th, reverse=True)

for i in range(len(thdec)):
    if thdec[i] >= sl_max:
        H -= thdec[i]
        turn += 1
        if H <= 0:
            break
    else:
        break

if H > 0:
    turn += math.ceil(H / sl_max)

print(turn)
### BUGGY CODE ###

N_K=list(map(int,input().split()))
N=N_K[0]
K=N_K[1]
cost=list(map(int,input().split()))
#cost=[int(input()) for i in range(N)]

answers=[0,abs(cost[1]-cost[0])]
if K==1:
	S=0
	for i in range(N-1):
		S += abs(cost[i]-cost[i+1])
	print (S)
else:
	for i in range(2,N):
		comp=[]
		if i<K:
			for j in range(1,i+1):
				comp.append(answers[i-j]+abs(cost[i]-cost[i-j]))
			answers.append(min(comp))
		else:
			for j in range(1,K+1):
				comp.append(answers[i-j]+abs(cost[i]-cost[i-j]))
			answers.append(min(comp))			
	print(answers[-1])

### FIXED CODE ###

N_K=list(map(int,input().split()))
N=N_K[0]
K=N_K[1]
cost=list(map(int,input().split()))
answers=[0,abs(cost[1]-cost[0])]
if K==1:
	S=0
	for i in range(N-1):
		S += abs(cost[i]-cost[i+1])
	print (S)
else:
	for i in range(2,N):
		comp=[]
		if i<K:
			comp=[answers[i-j]+abs(cost[i]-cost[i-j]) for j in range(1,i+1)]
			answers.append(min(comp))
		else:
			comp=[answers[i-j]+abs(cost[i]-cost[i-j]) for j in range(1,K+1)]
			answers.append(min(comp))			
	print(answers[-1])
### BUGGY CODE ###

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

A = [int(x) for x in input().split()]
A.sort()
max = 0
BC = []
for i in range(M):
    b,c = [int(x) for x in input().split()]
    max += b
    for j in range(b):
        BC.append(c)
BC.sort(reverse=True)

now = 0
for i in range(len(A)):
    if(now >= max):
        break
    if(A[i] < BC[now]):
        A[i] = BC[now]
        now+=1

# print(A)
print(sum(A))


### FIXED CODE ###

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

A = [int(x) for x in input().split()]
A.sort()
max = 0
BC = []
for i in range(M):
    b,c = [int(x) for x in input().split()]
    max += b
    BC.append([c,b])

BC.sort(reverse = True)
str =[]
for c,b in BC:
    str+=[c]*b
    # print(str)
    if(len(str) > N):
        break

now = 0
for i in range(len(A)):
    if(now >= max or str[now] < A[i]):
        break
    if(A[i] < str[now]):
        A[i] = str[now]
        now+=1

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

import sys
n, m = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(m)]
ln1 = []
ln2 = []
for i in p:
    if i[0] == 1:
        ln1.append(i[1])
for j in p:
    if j[1] == n:
        ln2.append(j[0])

for k in ln1:
    if k in ln2:
        print('POSSIBLE')
        sys.exit()
print('IMPOSSIBLE')

### FIXED CODE ###

import sys
n, m = map(int, input().split())
p = [list(map(int, input().split())) for _ in range(m)]
ln1 = []
ln2 = []
for i in p:
    if i[0] == 1:
        ln1.append(i[1])
for j in p:
    if j[1] == n:
        ln2.append(j[0])

if len(set(ln1) & set(ln2)) == 0:
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')
### BUGGY CODE ###

import math
from collections import deque
a, b, n = map(int, input().split())
d = deque(list(math.floor(a*i/b)- a * math.floor(i/b) for i in range(1, n+1)))
print(max(d))

### FIXED CODE ###

import math
a, b, n = map(int, input().split())
x = min(b-1, n)
ans = math.floor(a*x/b)- a * math.floor(x/b)
print(ans)
### BUGGY CODE ###

import math

N = int(input())
points = []
for _ in range(N):
  points.append(tuple(map(int, input().split())))

# get orientation
def orientation(p, q, r):
  v = (q[1] - p[1]) * (r[0] - q[0]) - (q[0] - p[0]) * (r[1] - q[1])
  if v == 0:
    return 0
  elif v > 0:
    return 1
  else:
    return 2

# get left most point
def left_index(points):
  minn = 0
  for i in range(1, len(points)):
    if points[i][0] < points[minn][0]:
      minn = i
    elif points[i][0] == points[minn][0]:
      if points[i][1] > points[minn][1]:
        minn = i
  return minn

# get convex hull
def convex_hull(points, n):
  if n < 3:
    return
  l = left_index(points)
  hull = []
  p = l
  q = 0
  while True:
    hull.append(p)
    q = (p + 1) % n
    for i in range(n):
      if orientation(points[p], points[i], points[q]) == 2:
        q = i
    p = q
    if p == l:
      break
  return hull

hull = convex_hull(points, len(points))

res = 0

def distance(p, q):
  return abs(p[0] - q[0]) + abs(p[1] - q[1])

if len(points) == 2:
  print(distance(points[0], points[1]))
  exit()

def cross(a, b, c, d):
  return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])

# Rotating Calipers
n = len(hull)
i = j = 0
for k in range(n):
  if hull[k] < hull[i]: i = k
  if hull[j] < hull[k]: j = k
res = 0
si = i; sj = j
while i != sj or j != si:
  res = max(res, distance(points[hull[i]], points[hull[j]]))
  if cross(points[hull[i]], points[hull[i-n+1]], points[hull[j]], points[hull[j-n+1]]) < 0:
    i = (i + 1) % n
  else:
    j = (j + 1) % n
print(res)

### FIXED CODE ###

from math import sqrt

N = int(input())
ps = set()
for _ in range(N):
  ps.add(tuple(map(int, input().split())))
ps = list(ps)
ps.sort()

def cross3(a, b, c):
  return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0])

def cross(a, b, c, d):
  return (b[0]-a[0])*(d[1]-c[1]) - (b[1]-a[1])*(d[0]-c[0])

# ps = [(x, y), ...]: ソートされた座標list
def convex_hull(ps):
  qs = []
  N = len(ps)
  for p in ps:
    # 一直線上で高々2点にする場合は ">=" にする
    while len(qs) > 1 and cross3(qs[-1], qs[-2], p) > 0:
      qs.pop()
    qs.append(p)
  t = len(qs)
  for i in range(N-2, -1, -1):
    p = ps[i]
    while len(qs) > t and cross3(qs[-1], qs[-2], p) > 0:
      qs.pop()
    qs.append(p)
  return qs

# キャリパー法(Rotating Calipers法)
# 凸多角形を回転しながら走査し、最遠点対を求める
def dist(a, b):
  return abs(a[0]-b[0]) + abs(a[1]-b[1])

def rotating_calipers(ps):
  qs = convex_hull(ps)
  n = len(qs)
  if n == 2:
    return dist(qs[0], qs[1])
  i = j = 0
  for k in range(n):
    if qs[k] < qs[i]: i = k
    if qs[j] < qs[k]: j = k
  res = 0
  si = i; sj = j
  while i != sj or j != si:
    res = max(res, dist(qs[i], qs[j]))
    if cross(qs[i], qs[i-n+1], qs[j], qs[j-n+1]) < 0:
      i = (i + 1) % n
    else:
      j = (j + 1) % n
  return res

if len(ps) == 1:
  print(0)
elif len(ps) == 2:
  print(dist(ps[0], ps[1]))
else:
  print(rotating_calipers(ps))
### BUGGY CODE ###

N = int(input())
cnt = 0
number = 1

while number <= N:
    
    for i in range(1,N+1):
        for j in range(1,N+1):
            for k in range(1,N+1):
                if i**2 + j**2 + k**2 + i*j + j*k + k*i == number:
                    cnt += 1
                else:
                    continue
    print(cnt)
    cnt = 0
    number += 1
            
    

### FIXED CODE ###

N = int(input())
ans_list = [0 for _ in range(1,10100)]

for i in range(1,100):
    for j in range(1,100):
        for k in range(1,100):
            value = i**2 + j**2 + k**2 + i*j + j*k + k*i
            if value <= 10000:
                ans_list[value] += 1

for i in range(1, N+1):
    print(ans_list[i])
### BUGGY CODE ###

n=int(input())
#それぞれ長さはn-1
a=[[(j-1,i) if j-1<i else (i,j-1) for j in list(map(int,input().split()))] for i in range(n)]
#試合の候補をいれる
d=dict()
for i in range(n):
    if a[i][0] in d:
        d[a[i][0]]+=1
    else:
        d[a[i][0]]=1
#どこまで見たか
b=[0]*n
check=[n-1]*n
#最大n(n-1)/2回
ans=0
while b!=check:
    ans+=1
    nextd=[]
    cleard=[]
    #一個も同じのなかったらむり
    g=True
    #print(d)
    for i in d:
        if d[i]==2:
            g=False
            e,f=i
            cleard.append(i)
            b[e]+=1
            b[f]+=1
            if b[e]<n-1:
                nextd.append(a[e][b[e]])
            if b[f]<n-1:
                nextd.append(a[f][b[f]])
    if g:
        exit(print(-1))       
    for i in nextd:
        if i in d:
            d[i]+=1
        else:
            d[i]=1
    for i in cleard:
        d.pop(i)
print(ans)







### FIXED CODE ###

from collections import deque
#わからない、テストケース
n=int(input())
#それぞれ長さはn-1
a=[[j-1+n*i if j-1<i else i+n*(j-1) for j in list(map(int,input().split()))] for i in range(n)]
#試合の候補をいれる
d=dict()
for i in range(n):
    if a[i][0] in d:
        d[a[i][0]]+=1
    else:
        d[a[i][0]]=1
#どこまで見たか
b=[0]*n
#最大n(n-1)/2回
ans=0
nextd=deque()
cleard=deque()
changeable1=deque(set([a[i][0] for i in range(n)]))
while len(d):
    ans+=1
    #一個も同じのなかったらむり
    g=True
    changeable2=deque()
    for i in changeable1:
        if d[i]==2:
            g=False
            e,f=i//n,i%n
            cleard.append(i)
            b[e]+=1
            b[f]+=1
            if b[e]<n-1:
                nextd.append(a[e][b[e]])
                changeable2.append(a[e][b[e]])
            if b[f]<n-1:
                nextd.append(a[f][b[f]])
                changeable2.append(a[f][b[f]])
    if g:
        exit(print(-1))
    ln,lc=len(nextd),len(cleard)  
    for _ in range(ln):
        i=nextd.popleft()
        if i in d:
            d[i]+=1
        else:
            d[i]=1
    for _ in range(lc):
        i=cleard.popleft()
        #print(i)
        #print(d)
        d.pop(i)
    changeable1=set(changeable2)
print(ans)
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
minb=min(min(A),max(A)-N)
maxb=max(max(A),min(A)+N)
ans=float('inf')
for b in range(minb,maxb+1):
  d=0
  for i in range(N):
    d+=abs(A[i]-(b+i))
  ans=min(ans,d)
print(ans)

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=[]
for i in range(N):
  B.append(A[i]-(i+1))
B.sort()
b=B[N//2]
ans=0
for i in range(N):
  ans+=abs(B[i]-b)
print(ans)
### BUGGY CODE ###

x = 1
for i in range(10 ** 8):
    x *= i
print(x)

### FIXED CODE ###

# ABC133A - T or T
def main():
    n, a, b = list(map(int, input().rstrip().split()))
    print(min(n * a, b))


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

import math
class sqrt_tree:
    def __init__(self,dat,f):
        self.dat = dat
        self.sq = int(len(dat) ** 0.5)
        self.f = f
        self.baqet = [self.f(dat[i * self.sq:(i + 1) * self.sq]) for i in range(len(dat) // self.sq)]
    
    #query
    def q(self,l,r):
        r += 1
        if math.ceil(l / self.sq) >= r // self.sq:
            return self.f(self.dat[l:r])
        ret = []
        if math.ceil(l / self.sq) < len(self.baqet):
            ret.append(self.f(self.baqet[math.ceil(l / self.sq):r // self.sq]))
        if l % self.sq:
            ret.append(self.f(self.dat[l:l + self.sq]))
        if r % self.sq:
            ret.append(self.f(self.dat[r - r % self.sq:r]))
        return self.f(ret)

import sys
f = sys.stdin

_, d = map(int, f.readline().split())

x,y = {},{}
for line in f:
    xi, yi, bi = map(int, line.split())
    if bi not in x:
        x[bi],y[bi] = [],[]
    x[bi].append(xi)
    y[bi].append(yi)

b = sorted(x.keys())

xmax = sqrt_tree([max(x[bi]) for bi in b],max)
xmin = sqrt_tree([min(x[bi]) for bi in b],min)
ymax = sqrt_tree([max(y[bi]) for bi in b],max)
ymin = sqrt_tree([min(y[bi]) for bi in b],min)

def get_lr(b,d):
    l = r = 0
    while r < len(b):
        while b[l] + d < b[r]:
            l += 1
        for k in range(r,len(b)):
            if b[l] + d < b[k]:
                break
            r = k
        yield l,r
        r += 1
        l += 1
    
max_size = max((xmax.q(l,r) - xmin.q(l,r)) * (ymax.q(l,r) - ymin.q(l,r)) for l,r in get_lr(b,d))
print(max_size)

### FIXED CODE ###

import math
def segmentTree(dat, f, sentinel):
        pad = 2 ** math.ceil(math.log(len(dat),2))
        dat = [0] * pad + dat + [sentinel] * (pad - len(dat))
        for i in range(pad - 1, 0, -1):
            dat[i] = f(dat[i * 2],dat[i * 2 + 1])
        return dat

def get_lr(b,d):
    l = r = 0
    while r < len(b):
        while b[l] + d < b[r]:
            l += 1
        for r in range(r,len(b)):
            if b[l] + d < b[r]:
                r -= 1
                break
        r += 1
        yield l,r
        l += 1
    
import sys
f = sys.stdin

_, d = map(int, f.readline().split())

xyb = []
for line in f:
    xyb.append(tuple(map(int, line.split())))
from operator import itemgetter
xyb.sort(key=itemgetter(2))

x = [xybi[0] for xybi in xyb]
y = [xybi[1] for xybi in xyb]
b = [xybi[2] for xybi in xyb]

xmax = segmentTree(x,max,sentinel = 0)
xmin = segmentTree(x,min,sentinel = 2000000)
ymax = segmentTree(y,max,sentinel = 0)
ymin = segmentTree(y,min,sentinel = 2000000)


pad = len(xmax) // 2
max_size = 0
def create_index(l,r):
    index = []
    ia = index.append
    while l < r:
        if r & 1:
            r -= 1
            ia(r)
        if l & 1:
            ia(l)
            l += 1
        l >>= 1
        r >>= 1
    return index

for l,r in get_lr(b,d):
    l += pad 
    r += pad
    index = create_index(l,r)

    now_xmax = max(xmax[i] for i in index)
    now_ymax = max(ymax[i] for i in index)
    if max_size < now_xmax * now_ymax:
        max_size = max(max_size,((now_xmax - min(xmin[i] for i in index)) * (now_ymax - min(ymin[i] for i in index))))
print(max_size)
### BUGGY CODE ###

import collections
N = int(input())
A = []
B=[]
ans=0
for i in range(N):
    x=collections.Counter(list(input()))
    if x in A:
      ii=A.index(x)
      B[ii]+=1
    else:
      A.append(x)
      B.append(1)
ans=0
for b in B:
  ans+=(b-1)*(b)/2
print(int(ans))




### FIXED CODE ###

N = int(input())
dic = {}
ans = 0
for i in range(N):
    tmp = "".join(sorted(input()))
    if tmp in dic:
        ans += dic[tmp]
        dic[tmp] += 1
    else:
        dic[tmp] = 1
print(ans)
### BUGGY CODE ###

n,m = list(map(int, input().split()))
h = list(map(int, input().split())) 
ab =  [[int(_) for _ in input().split()] for __ in range(m)]

n_list =[x for x in range(1,n+1)]
for i in ab:
    if (h[i[0]-1]  > h[i[1]-1]) and (i[1] in n_list):
        n_list.remove(i[1])
    elif (h[i[0]-1]  < h[i[1]-1]) and (i[0] in n_list):
        n_list.remove(i[0])
    elif h[i[0]-1]  == h[i[1]-1]:
        if i[0] in n_list:
            n_list.remove(i[0])
        if i[1] in n_list:
            n_list.remove(i[1])          
print(len(n_list))

### FIXED CODE ###

n,m = list(map(int, input().split()))
h = list(map(int, input().split())) 
ab =  [[int(_) for _ in input().split()] for __ in range(m)]

n_list =[x for x in range(1,n+1)]
ze = dict(zip(n_list, [0 for i in range(len(n_list))]))

for i in ab:
    if (h[i[0]-1]  > h[i[1]-1]):
        ze[i[1]] += 1
    elif (h[i[0]-1]  < h[i[1]-1]) :
        ze[i[0]] += 1
    elif h[i[0]-1]  == h[i[1]-1]:
        ze[i[0]] += 1
        ze[i[1]] += 1

res = 0
for k, v in ze.items():
    if v == 0:
        res += 1
print(res)
### BUGGY CODE ###

N = int(input())
A = [int(j) for j in input().split()]
import functools
import operator

result = functools.reduce(operator.mul, A)
if result >10**18:
    print(-1)
else:
    print(result)

### FIXED CODE ###

N = int(input())
A = [int(j) for j in input().split()]
from collections import Counter

A_C =Counter(A)
A_C = sorted(A_C.items(),key=lambda x:-x[0])

if 0 == A_C[-1][0]:
    print(0)
    exit()
    
result = 1
for a in A_C:
    result*=(a[0]**a[1])

    if result >10**18:
        print(-1)
        exit()

print(result)
### BUGGY CODE ###

import numpy as np

N,K,Q=map(int,input().split())
A=np.array([int(input())-1 for i in range(Q)])

for j in range(N):
    if K+np.count_nonzero(A==j)>Q:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

N, K, Q = map(int, input().split())
 
P = [0] * N
for i in range(Q):
    tmp = int(input()) - 1
    P[tmp] += 1
 
sumP = sum(P)
for n in range(N):
    ans = 'No'
    total = sumP - P[n]
    if  K - total > 0:
        ans = 'Yes'
    print(ans)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N = int(input())

Ans = 0

for i in range(1,N+1):
  if int(float(i)**0.5) <= 1:
    rMax = 1
  else:
    rMax = int(float(N)**0.5)  

  for x in range(1,rMax+1):
    if x**2 > i:
      break
    else:
      for y in range(1,rMax+1):
        if x**2 + y**2 > i:
          break
        else:
          for z in range(1,rMax+1):
            if x**2 + y**2 + z**2 > i:
              break
            else:
              if x**2 + y**2 + z**2 + (x * y) + (y * z) + (z * x) == i:
                Ans += 1
  
  print(Ans)
  Ans = 0

### FIXED CODE ###

# -*- coding: utf-8 -*-
# スペース区切りの整数の入力
N = int(input())

Ans = 0
numlist = [0] * 10001

if int(float(N)**0.5) <= 1:
  rMax = 1
else:
  rMax = int(float(N)**0.5)  

for x in range(1,rMax+1):
  for y in range(1,rMax+1):
    for z in range(1,rMax+1):
      Ans = x**2 + y**2 + z**2 + (x * y) + (y * z) + (z * x)
      if Ans <= 10000:
        numlist[Ans] += 1
  
for r in range(1,N+1):
  print(numlist[r])
### BUGGY CODE ###

from collections import deque

dirs = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def main():
    H, W = map(int, input().split())
    S = [list(input()) for _ in range(H)]
    q = deque()
    q.append((0, 0, 1))
    sp = -1
    while len(q):
        i, j, path = q.popleft()
        if i == H-1 and j == W-1:
            sp = path
            break
        if S[i][j] != '.' and S[i][j] < path:
            continue
        S[i][j] = path
        for d in dirs:
            ni, nj = i+d[0], j+d[1]
            if ni >= 0 and nj >= 0 and ni < H and nj < W and S[ni][nj] != '#':
                if S[ni][nj] == '.' or path+1 < S[ni][nj]:
                    q.append((ni, nj, path+1))
    if sp == -1:
        print(sp)
    else:
        ans = 0
        for i in range(H):
            for j in range(W):
                if S[i][j] != '#':
                    ans += 1
        print(ans - sp)


if __name__ == "__main__":
    main()


### FIXED CODE ###

directions = [(1, 0), (0, 1), (-1, 0), (0, -1)]


def main():
    H, W = map(int, input().split())
    s = [input() for _ in range(H)]
    path = [[float("inf")] * W for _ in range(H)]
    white = sum([len(row.replace("#", "")) for row in s])
    scan = [(0, 0, 1)]  # i, j, cost
    while len(scan):
        i, j, cost = scan.pop(0)
        if cost >= path[i][j]:
            continue
        path[i][j] = cost
        for d in directions:
            nexti = i + d[0]
            nextj = j + d[1]
            if 0 <= nexti and nexti < H and \
               0 <= nextj and nextj < W and \
               s[nexti][nextj] == ".":
                scan.append((nexti, nextj, cost + 1))
    if path[H-1][W-1] == float("inf"):
        print(-1)
    else:
        print(white - path[H-1][W-1])


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

n=input()
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 ###

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


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

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

def main():
    n = int(input())
    a = list(map(int,input().split()))
    mod = 10**9+7
    div = {}
    for i in range(61):
        div[i] = 0
    for i in range(n):
        c = 0
        while a[i]>0:
            if a[i] %2 == 1:
                div[c] += 1
            a[i] = a[i]//2
            c+=1
    ans = 0
    for k in div.keys():
        ans += div[k] * (n-div[k]) * 2**k
        ans = ans % mod
    print(ans)

if __name__ == "__main__":
    main()


### FIXED CODE ###

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

p = 10**9+7
ans = 0
for i in range(60):
    x = 1<<i
    one = sum(1 for j in a if j&x)
    ans += pow(2,i,p)*one*(n-one)

print(ans%p)
### BUGGY CODE ###

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

k = m // n

c = 1
for i in range(1,k+1):
    if m % i == 0:
        c = i

print(c)

### FIXED CODE ###

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

ans = 1

for i in range(1,int(m**0.5)+1):
    if m % i == 0 and m /n >= i:
        ans = max(ans,i)
        if i != m // i and m/n >= (m//i):
            ans = max(ans,m // i)

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

# -*- coding: utf-8 -*-
# モジュールのインポート
import math
import itertools

# 標準入力を取得
N = int(input())

# 求解処理


def has_z(n: int, x: int, y: int) -> bool:
    d = 4 * n - 3 * x**2 - 3 * y**2 - 2 * x * y
    if d < 0:
        return False
    z = (-(x + y) + math.sqrt(d)) / 2
    return (z.is_integer()) and (z >= 1)


for n in range(1, N + 1):
    ans = 0
    max_v = int(math.sqrt(n))
    for x in range(1, max_v + 1):
        for y in range(x, max_v + 1):
            if has_z(n, x, y):
                ans += 1 + (x != y)
    print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
# モジュールのインポート
import math
import itertools

# 標準入力を取得
N = int(input())

# メイン処理


def g(x: int, y: int, z: int) -> int:
    return x**2 + y**2 + z**2 + x*y + y*z + z*x


l = [0 for n in range(N)]
for x, y, z in itertools.product(range(1, int(math.sqrt(N)) + 1), repeat=3):
    v = g(x, y, z)
    if v <= N:
        l[v - 1] += 1

# 結果出力
for ans in l:
    print(ans)
### BUGGY CODE ###

import itertools
x,y,z,k = list(map(int, input().split())) 
a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

ab = [i + j for (i, j) in list(itertools.product(a, b))]

ab.sort(reverse=True)

abc = [ij + h for (ij, h) in list(itertools.product(ab[:min(3000,x*y*z)], c))]

abc.sort(reverse=True)

for g in range(k):
  print(abc[g])

### FIXED CODE ###

import heapq
x,y,z,k = list(map(int, input().split())) 
a = sorted(list(map(int, input().split())),reverse=True)
b = sorted(list(map(int, input().split())),reverse=True)
c = sorted(list(map(int, input().split())),reverse=True)

ans = []
log = set()

total = (a[0] + b[0] + c[0]) * (-1)
heapq.heappush(ans, (total, 0, 0, 0))
log.add((0, 0, 0))

for i in range(k):
  (total, aa, bb, cc) = heapq.heappop(ans)
  print(total * (-1))
  if (aa+1, bb, cc) not in log:
    if aa+1 < x:
      total = (a[aa+1] + b[bb] + c[cc]) * (-1)
      heapq.heappush(ans, (total, aa+1, bb, cc))
      log.add((aa+1, bb, cc))
  if (aa, bb+1, cc) not in log:
    if bb+1 < y:
      total = (a[aa] + b[bb+1] + c[cc]) * (-1)
      heapq.heappush(ans, (total, aa, bb+1, cc))
      log.add((aa, bb+1, cc))
  if (aa, bb, cc+1) not in log:
    if cc+1 < z:
      total = (a[aa] + b[bb] + c[cc+1]) * (-1)
      heapq.heappush(ans, (total, aa, bb, cc+1))
      log.add((aa, bb, cc+1))