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

import fractions, sys
input = sys.stdin.buffer.readline


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


def calc(n, m):
    for i in range(cycle//m+1):
        X = m * (i + 0.5)
        flag = True
        for x in n:
            if (X - x // 2) % x != 0:
                flag = False
                break
        if flag:
            return int(X)
    print(0)
    exit()
    return


N, M = map(int, input().split())
A = list(map(int, input().split()))
cycle = 1
ma = 0
for a in A:
    cycle = lcm(cycle, a)
    ma = max(ma, a)
start = calc(A, ma)

print((M - start) // cycle + 1)



### FIXED CODE ###

import fractions, sys
input = sys.stdin.buffer.readline


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


def calc(n, m):
    for i in range(cycle//m+1):
        X = m * (i + 0.5)
        if X > M:
            print(0)
            exit()
            return
        flag = True
        for x in n:
            if (X - x // 2) % x != 0:
                flag = False
                break
        if flag:
            return int(X)
    print(0)
    exit()
    return


N, M = map(int, input().split())
A = list(map(int, input().split()))
cycle = 1
ma = 0
for a in A:
    cycle = lcm(cycle, a)
    ma = max(ma, a)
start = calc(A, ma)

print((M - start) // cycle + 1)
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for _ in range(H)]

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i, row in enumerate(grid):
    for j, s in enumerate(row):
        if s == "#":
            dist[i][j] = 0
            que.append(i*W + j)

ans = 0
while len(que) > 0:
    num = que.popleft()
    h = num // W
    w = num % W
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if dist[ny][nx] == INF:
            que.append(ny * W + nx)
        dist[ny][nx] = min(dist[ny][nx], dist[h][w]+1)
        ans = max(ans, dist[ny][nx])

print(ans)

### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
grid = [input() for _ in range(H)]

dxdy = [(-1,0), (1,0), (0,-1), (0,1)]
INF = 999999
que = deque()

dist = [[INF] * W for _ in range(H)]
for i, row in enumerate(grid):
    for j, s in enumerate(row):
        if s == "#":
            dist[i][j] = 0
            que.append(i*W + j)

ans = 0
while len(que) > 0:
    num = que.popleft()
    h = num // W
    w = num % W
    for dx, dy in dxdy:
        nx = w + dx
        ny = h + dy
        if ny<0 or ny>=H or nx<0 or nx>=W:
            continue
        if dist[ny][nx] == INF:
            que.append(ny * W + nx)
        dist[ny][nx] = min(dist[ny][nx], dist[h][w]+1)
        ans = max(ans, dist[ny][nx])

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

import fractions
N = int(input())
A_array = list(map(int, input().split()))

gcd_max = 1

if N == 2:
    print(max(A_array[0], A_array[1]))
    exit()
for i in range(N):
    gcd = 0
    for j, A in enumerate(A_array):
        if i == j:
            continue
        if gcd == 0:
            gcd = A
            continue
        # print(A,gcd)
        gcd = min(gcd, fractions.gcd(A, gcd))
        if gcd <= gcd_max:
            break
    gcd_max = max(gcd_max, gcd)
print(gcd_max)

### FIXED CODE ###

import fractions
N = int(input())
A_array = list(map(int, input().split()))

if N == 2:
    print(max(A_array[0], A_array[1]))
    exit()

remove_index = []
for i, A in enumerate(A_array):
    if i == 0:
        gcd_max = A
        remove_index.append(i)
        continue
    gcd = fractions.gcd(gcd_max, A)
    # print(i, gcd_max, gcd)
    if gcd_max > gcd:
        gcd_max = gcd
        remove_index.append(i)
# print(remove_index)
# print(gcd_max, remove_index)

gcd_ans = gcd_max
for index in remove_index:
    gcd = 0
    for i, A in enumerate(A_array):
        if i == index:
            continue
        if gcd == 0:
            gcd = A
            continue
        # print(gcd,A)
        gcd = fractions.gcd(gcd, A)
        if gcd_ans >= gcd:
            break
    # print(gcd_ans,gcd)
    gcd_ans = max(gcd_ans, gcd)
print(gcd_ans)
### BUGGY CODE ###

N=int(input())
s=[''.join(sorted(input())) for i in range(N)]


dic={}
counter=0
for i in range(N):
  if (s[i] in dic.keys())==True:
    counter+=dic[s[i]]
    dic[s[i]]=dic[s[i]]+1
  else:
    dic[s[i]]=1

print(counter)

### FIXED CODE ###

N=int(input())
s=[''.join(sorted(input())) for i in range(N)]


dic={}
counter=0
for i in range(N):
  if (s[i] in dic.keys())==True:
    counter+=dic[s[i]]
    dic[s[i]]=dic[s[i]]+1
  else:
    dic[s[i]]=1

print(counter)
### BUGGY CODE ###

n=int(input())
s=list(map(int,input().split()))
s.sort()
c=0
if len(s)==2:
    ans=[max(s),min(s)]
for i in range(n//2,n):
    for j in s:
        if s[i]//2-2<=j<=s[i]//2+2:
            bunsi=bunbo=1
            for k in range(j):
                bunsi*=(s[i]-k)
                bunbo*=k+1
            if c<=bunsi//bunbo:
                c=bunsi//bunbo
                ans=[s[i],j]
print(*ans)

### FIXED CODE ###

n=int(input())
s=list(map(int,input().split()))
s.sort()
c=float("inf")
a=max(s)
for i in s[0:n]:
    x=abs(a/2-i)
    if x<c:
        c=x
        b=i
print(a,b)
### BUGGY CODE ###

H, W, D = [int(x) for x in input().split()]
A = [0] * (H * W + 1)
for h in range(H):
    inp = [int(x) for x in input().split()]
    for i, a in enumerate(inp):
        A[a] = (i + 1, h + 1)
Q = int(input())
for q in range(Q):
    l, r = [int(x) for x in input().split()]
    m = 0
    while l != r:
        m += abs(A[l+D][0] - A[l][0]) + abs(A[l+D][1] - A[l][1])
        l = l + D
    print(m)


### FIXED CODE ###

H, W, D = [int(x) for x in input().split()]
A = [0] * (H * W + 1)
for h in range(H):
    inp = [int(x) for x in input().split()]
    for i, a in enumerate(inp):
        A[a] = (i + 1, h + 1)

table = [0] * (H * W + 1)
for i in range(D):
    x = H * W - i - D
    r = 0
    while x > 0:
        table[x] = abs(A[x][0] - A[x+D][0]) + abs(A[x][1] - A[x+D][1]) \
                   + r
        r = table[x]
        x -= D
for q in range(int(input())):
    l, r = [int(x) for x in input().split()]
    print(table[l] - table[r])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**9)
def dfs(v,t,f,used,graph):
    if v==t:
        return f
    used[v] = True
    for to in graph[v]:
        c = graph[v][to]
        if used[to] or c==0:
            continue
        d = dfs(to,t,min(f,c),used,graph)
        if d>0:
            graph[v][to] -= d
            graph[to][v] += d
            return d
    return 0

def max_flow(s,t,graph):
    flow = 0
    while True:
        used = [False]*len(graph)
        f = dfs(s,t,float('inf'),used,graph)
        flow += f
        if f==0:
            return flow

H,W = map(int,input().split())
a = [input() for _ in range(H)]
a = [[s for s in a[i]] for i in range(H)]

H,W=100,100
a = [['o']*W for i in range(H)]
a[0][0]='S'
a[-1][-1]='T'

def encode(h,w):
    return h*W+w

def decode(d):
    return (d//W,d%W)

ans = 10**9
for h in range(H):
    for w in range(W):
        if a[h][w]=='S':
            s = encode(h,w)
            a[h][w]='o'
        if a[h][w]=='T':
            t = encode(h,w)
            a[h][w]='o'

if decode(s)[0]==decode(t)[0] or decode(s)[1]==decode(t)[1]:
    ans = -1

graph = [{} for _ in range(H*W)]

for h in range(H):
    for w in range(W):
        if a[h][w]=='.':
            continue
        for i in range(H):
            if i==h:
                continue
            if a[i][w]=='.':
                continue
            graph[encode(h,w)][encode(i,w)] = 1
            graph[encode(i,w)][encode(h,w)] = 1
        for j in range(W):
            if j==w:
                continue
            if a[h][j]=='.':
                continue
            graph[encode(h,w)][encode(h,j)] = 1
            graph[encode(h,j)][encode(h,w)] = 1

ans = min(ans,max_flow(s,t,graph))
print(ans)

### FIXED CODE ###

def dfs(v,t,f,used,graph):
    if v==t:
        return f
    used[v] = True
    for to in graph[v]:
        c = graph[v][to]
        if used[to] or c==0:
            continue
        d = dfs(to,t,min(f,c),used,graph)
        if d>0:
            graph[v][to] -= d
            graph[to][v] += d
            return d
    return 0
 
def max_flow(s,t,graph):
    flow = 0
    while True:
        used = [False]*len(graph)
        f = dfs(s,t,float('inf'),used,graph)
        flow += f
        if f==0 or f==float('inf'):
            return flow
 
H,W = map(int,input().split())

a = [input() for _ in range(H)]
a = [[s for s in a[i]] for i in range(H)]

graph = [{} for _ in range(H+W+2)]

for h in range(H):
    for w in range(W):
        if a[h][w]=='o':
            graph[h][H+w] = 1
            graph[H+w][h] = 1
        if a[h][w]=='S':
            graph[H+W][h] = float('inf')
            graph[H+W][H+w] = float('inf')
            graph[h][H+W] = 0
            graph[H+w][H+W] = 0
        if a[h][w]=='T':
            graph[H+W+1][h] = 0
            graph[H+W+1][H+w] = 0
            graph[h][H+W+1] = float('inf')
            graph[H+w][H+W+1] = float('inf')

ans = max_flow(H+W,H+W+1,graph)
if ans == float('inf'):
    ans = -1

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

import itertools
R,G,B,N = map(int, input().split())
count = 0
Rc = [i * R for i in range(0, N+1) if i * R <= N]
Gc = [i * G for i in range(0, N+1) if i * G <=  N]
Bc = [i * B for i in range(0, N+1) if i * B <=  N]
#print(Rc)
#print(Gc)
#print(Bc)
Combi = list(itertools.product(Rc, Gc, Bc))
print(sum([True for i in Combi if sum(i) == N]))

### FIXED CODE ###

R,G,B,N = map(int, input().split())
count = 0
for r in range(N // R + 1) :
    for g in range((N - r*R) // G + 1) :
        if (N - r*R - g*G) %B == 0 :
            count += 1
print(count)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
numlist = list(map(int, input().split()))
if 0 < numlist.count(0):
    print('0')
    quit()

total = 1
for i in numlist:
  total *= i

if 10 ** 18 < total:
  print('-1')
else:
  print(total) 

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
numlist = list(map(int, input().split()))
if 0 < numlist.count(0):
    print('0')
    quit()

total = 1
for i in numlist:
  total *= i
  if 10 ** 18 < total:
    print('-1')
    quit()

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

n = int(input())
a = [int(s) for s in input().split()]

count = 0

for i in range(n):
    if a.count(a[i]) >= 2:
        count += 1
        break

if count >= 1:
    print('NO')
else:
    print('YES')

### FIXED CODE ###

def has_duplicates(seq):
    return len(seq) != len(set(seq))

n = int(input())
a = [int(s) for s in input().split()]

if has_duplicates(a) == False:
    print('YES')
else:
    print('NO')
### BUGGY CODE ###

import math
n=int(input())
l=[int(x) for x in input().split()]
for k in range(n):
  L=l.pop(k)
  ans=0
  for i in range(n+1):
    c=l.count(i)
    if c>1:
      ans=ans+math.factorial(c) // (math.factorial(c- 2) * 2)
  print(ans)
  l.insert(k,L)
    
    

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
l = [0]*N
ans = 0
for a in A:
    l[a-1] += 1
for j in l:
    ans += int(j*(j-1)/2)
for k in range(N):
    print(ans - l[A[k]-1] + 1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit((10 ** 5) * 2)
 
def kai(a):
  if a == 1:
    return 1
  else:
    return a*kai(a-1)
  
N = int(input())
S = input()
count = 0
ans = 1
 
for i, s in enumerate(S):
  if ((s == "W") & (i%2 == 0)) or ((s == "B") & (i%2 == 1)):
    ans *= (i - (count*2))
    count += 1
if count != N:
  print(0)
else:
  print((ans*kai(N))%(10**9 + 7))

### FIXED CODE ###

N = int(input())
S = input()
count = 0
ans = 1
m = 10**9 + 7
 
for i in range(N):
  if S[2*i] == "W":
    ans = ans * ((2*i) - (count*2))%m
    count += 1
  if S[2*i + 1] == "B":
    ans = ans * ((2*i + 1) - (count*2))%m
    count += 1
 
if count != N:
  print(0)
else:
  for o in range(1, N+1):
    ans *= o
    ans %= m
  print(ans % m)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    ans = -float('inf')
    for i in range(n):
        start, count = i, 1
        val = c[start]
        while p[start]-1 != i:
            start = p[start]-1
            count += 1
            val += c[start]

        start = i
        if val > 0:
            a = (k//count-1)*val
            ans = max(a, ans)
            num = k%count+count
        else:
            a = 0
            num = min(k, count)

        for j in range(num):
            start = p[start]-1
            a += c[start]
            ans = max(ans, a)
    return ans
print(main())



### FIXED CODE ###

from numba import jit
@jit
def main():
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    ans = -10**10
    
    for i in range(n):
        start, count = i, 1
        val = c[start]
        while p[start]-1 != i:
            start = p[start]-1
            count += 1
            val += c[start]

        start = i
        if val > 0:
            a = (k//count-1)*val
            ans = max(a, ans)
            num = k%count+count
        else:
            a = 0
            num = min(k, count)

        for _ in range(num):
            start = p[start]-1
            a += c[start]
            ans = max(a, ans)
    print(int(ans))

main()
### BUGGY CODE ###

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

for i in range(M):
    B, C = map(int, input().split())
    for j in range(B):
        if li[0] >= C:
            break
        li[0] = C
        li.sort()
print(sum(li))


### FIXED CODE ###

from heapq import heappop, heappush, heapify
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
heap = list(map(int, input().split()))
heapify(heap)

BC = []
for _ in range(M):
    B, C = map(int, input().split())
    BC.append([B, C])
BC.sort(key=lambda x: -x[1])

for B, C in BC:
    for _ in range(B):
        tmp = heappop(heap)
        if tmp < C:
            heappush(heap, C)
        else:
            heappush(heap, tmp)
            break
print(sum(heap))
### BUGGY CODE ###

import sys
X = int(input())
res = 0
for b in range(1, X+1):
    for p in range(2, X+2):
        val = b**p
        if (val <= X) and (val > res):
            res = val
print(res)


### FIXED CODE ###

import sys
X = int(input())
res = 0
for b in range(1, -(-X//2)+1):
    for p in range(2, -(-X//2)+2):
        val = b**p
        if (val <= X) and (val > res):
            res = val
print(res)
### BUGGY CODE ###

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

import collections

for i in range(N):
  ans=0
  c = collections.Counter(A)
  c[A[i]]=c[A[i]]-1
  B=list(c.values())
  for k in range(len(B)):
    ans+=B[k]*(B[k]-1)/2
  print(int(ans))
    

### FIXED CODE ###

import sys
input = sys.stdin.readline
N=int(input())
A=list(map(int,input().split()))

import collections
c = collections.Counter(A)
B=list(c.values())
ans=0
for k in range(len(B)):
    ans+=B[k]*(B[k]-1)/2
for i in range(N):
  anser=ans
  anser=anser+1-c[A[i]]
  print(int(anser))
### BUGGY CODE ###

_=input()
while True:
  pass

### FIXED CODE ###

#!/usr/bin/env python3
s, w = map(int, input().split())
print(['unsafe', 'safe'][s > w])
### BUGGY CODE ###

n,m = map(int,input().split())
h_inputs = [int(i) for i in input().split()]
ab_inputs = [[int(j) for j in input().split()]for i in range(m)]

map_li = [[0 for i in range(n)] for i in range(n)]
ans = 0
for line in ab_inputs:
    a,b = line[0],line[1]
    c,d = h_inputs[a-1],h_inputs[b-1]
    if c==d:
        map_li[a-1][b-1]=-1
        map_li[b-1][a-1]=-1
    else:
        map_li[a-1][b-1]=c-d
        map_li[b-1][a-1]=d-c

for i in range(n):
    if all(m>=0 for m in map_li[i]):
        ans+=1
print(ans)

### FIXED CODE ###

n,m = map(int,input().split())
h_inputs = [int(i) for i in input().split()]
ab_inputs = [[int(j) for j in input().split()]for i in range(m)]

map_li = [1]*n
for line in ab_inputs:
    a,b = line[0],line[1]
    if h_inputs[a-1]>h_inputs[b-1]:
        map_li[b-1]=0
    if h_inputs[a-1]<h_inputs[b-1]:
        map_li[a-1]=0
    if h_inputs[a-1]==h_inputs[b-1]:
        map_li[a-1]=0
        map_li[b-1]=0
print(sum(map_li))
### BUGGY CODE ###

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

ans = 0
for i in range(N):
    ans ^= A[i]

for i in range(N):
    A[i] = (~ans)&A[i]

A = [a for a in A if a != 0]
b = []

for i in range(60):
    if len(A) == 0:
        break
    M = max(A)
    A_ = []
    for i in range(len(A)):
        if len(bin(M))==len(bin(A[i])):
            A[i] ^= M
        if A[i] != 0:
            A_.append(A[i])
    b.append(M)
    A = A_

b = b[::-1]
ans_ = 0
for i in range(len(b)):
    M = b[i]
    for j in range(i+1,len(b)):
        m = b[j]
        if len(bin(M))==len(bin(M&m)):
            b[j] ^= M
    ans_ ^= M

ans += ans_*2
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = 0
for a in A:
    ans ^= a
M = 2**60-1
b = M^ans
for i in range(N):
    A[i] &= b
A.sort(reverse=True)
for i in range(min(60,N)):
    a = A[i]
    if a == 0:
        break
    l = len(bin(a))-3
    for j in range(N):
        if j==i:
            continue
        if A[j]//2**l%2==1:
            A[j] ^= a
        else:
            if i < j:
                break
    A.sort(reverse=True)
s = 0
for a in A:
    s ^= a
ans += 2*s
print(ans)
### BUGGY CODE ###

import sys
import re

str = sys.stdin.readline().rstrip()
_str = str #　結果と比較用
while True:
    tmp = str
    tmp = re.sub("10", "", tmp)
    tmp = re.sub("01", "", tmp)
    if str == tmp:
        break
    str = tmp

print(len(_str) - len(str))


### FIXED CODE ###

import sys

cubes = list(input()) # 入力受付
stack = []
count = 0

for cube in cubes:
    if not stack:
        stack.append(cube)
    elif stack[-1] != cube:
        count += 2
        stack.pop()
    else:
        stack.append(cube)
print(count)
### BUGGY CODE ###

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

def calc(s):
    res = []
    for v in s:
        v.append('-')
        tmp = []
        nc = ''
        nn = 0
        for c in v:
            if nc == '':
                nc = c
                nn += 1
                continue
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp = tmp + [0 for _ in range(nn)]
                else:
                    tmp = tmp + [nn for _ in range(nn)]
                nc = c
                nn = 1
        res.append(tmp)
    return res

def calc2(s):
    res = []
    for j in range(w):
        v = ['-']
        tmp = []
        nc = ''
        nn = 0
        for i in range(h+1):
            if i == h:
                c = '-'
            else:
                c = s[i][j]
            if nc == '':
                nc = c
                nn += 1
                continue
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp = tmp + [0 for _ in range(nn)]
                else:
                    tmp = tmp + [nn for _ in range(nn)]
                nc = c
                nn = 1
        res.append(tmp)
    return res

tate = calc2(S)
yoko = calc(S)
print(max([tate[j][i] + yoko[i][j] for i in range(h) for j in range(w) if tate[j][i] * yoko[i][j] != 0]) - 1)


### FIXED CODE ###

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

def calc(s):
    res = []
    for v in s:
        v = v + '-'
        tmp = []
        nc = v[0]
        nn = 0
        for c in v:
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        res.append(tmp)
    return res

def calc2(s):
    res = []
    for j in range(w):
        tmp = []
        nc = s[0][j]
        nn = 0
        for i in range(h):
            c = s[i][j]
            if nc == c:
                nn += 1
                continue
            else:
                if nc == '#':
                    tmp.extend([0 for _ in range(nn)])
                else:
                    tmp.extend( [nn for _ in range(nn)])
                nc = c
                nn = 1
        if nc == '#':
            tmp.extend([0 for _ in range(nn)])
        else:
            tmp.extend( [nn for _ in range(nn)])
        res.append(tmp)
    return res

tate = calc2(S)
yoko = calc(S)

print(max([tate[j][i] + yoko[i][j] for i in range(h) for j in range(w) if tate[j][i] * yoko[i][j] != 0]) - 1)
### BUGGY CODE ###

#-*-coding:utf-8-*-

def main():
    n = int(input())
    arry = [list(map(int, input().split())) for _ in range(n)]
    ans = [arry[0]]
    
    for i in range(1, n):
        a, b = arry[i]
        while True:
            if a >= ans[i-1][0] and b >= ans[i-1][1]:
                ans.append([a, b])
                break
            a += arry[i][0]
            b += arry[i][1]
            
    print(sum(ans[-1]))

if __name__ == '__main__':
    main()

### FIXED CODE ###

#-*-coding:utf-8-*-

def main():
    n = int(input())
    arry = [list(map(int, input().split())) for _ in range(n)]
    ans = [arry[0]]

    for i in range(1, n):
        a, b = arry[i]
        if a >= ans[i-1][0] and b >= ans[i-1][1]:
            ans.append([a, b])
        else:
            num = max(-(-ans[i-1][0] // a), -(-ans[i-1][1] // b))
            a *= num
            b *= num
            ans.append([a, b])
    print(sum(ans[-1]))

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

from itertools import accumulate as ac
from functools import reduce

n,k=map(int,input().split())
*ac,=ac([0]+list(map(int,input().split())))

l=[ac[j]-ac[i] for i in range(n+1) for j in range(i+1,n+1)]
count_bits=lambda n:sum(map(lambda x:x&n==n,l))

ans=0
for i in range(41)[::-1]:
    if count_bits(ans|1<<i)>=k:
        ans|=1<<i

print(ans)

### FIXED CODE ###

from itertools import accumulate as ac

n,k=map(int,input().split())
*a,=ac([0]+list(map(int,input().split())))

l=[a[j]-a[i] for i in range(n+1) for j in range(i+1,n+1)]
f=lambda n:sum(map(lambda x:x&n==n,l))

ans=0
for i in range(41)[::-1]:
    if f(ans|1<<i)>=k:
        ans|=1<<i

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

import numpy as np
import itertools as it

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

combinations_lis = list(it.combinations(a, 2))
#print(combinations_lis)

sum = 0
for i in range(len(combinations_lis)):
    sum += combinations_lis[i][0] * combinations_lis[i][1]
print(sum % (10 ** 9 + 7))

# sum = 0
# for i in range(n):
#     sum += 1 / a[i]
#print(sum)

# ans = int(sum * np.prod(a))
# print(ans % (10 ** 9 + 7))


### FIXED CODE ###

# import numpy as np
# import itertools as it

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

res = 0
for i in range(n):
    res += a[i] * a[i]

ans = sum(a) * sum(a)
print(((ans - res)//2) % (10 ** 9 + 7))


# sum = 0
# for i in range(n):
#     sum += 1 / a[i]
#print(sum)

# ans = int(sum * np.prod(a))
# print(ans % (10 ** 9 + 7))
### BUGGY CODE ###

N, W = map(int, input().split())
WV = (list(map(int, input().split())) for _ in range(N))

DP = [[0] * (W+1) for _ in range(N)]

for i, (w, v) in enumerate(WV):
  for j in range(W+1):
    if j-w >= 0:
      # toru
      dp1 = DP[i-1][j-w] + v 
      # toranai
      dp2 = DP[i-1][j]
      dp = max(dp1, dp2)
    else:
      # toranai
      dp = DP[i-1][j]
    DP[i][j] = dp
print(max(DP[N-1]))

### FIXED CODE ###

def dp():
  N, W = map(int, input().split())
  WV = (map(int, input().split()) for _ in range(N))

  DP = [0] * (W+1)
  for w, v in WV:
    for j in range(W, w-1, -1):
      dp = DP[j-w] + v 
      if DP[j] < dp:
        DP[j] = dp
  return max(DP)
print(dp())
### BUGGY CODE ###

N = int(input())
ans = 1
for a in [int(hoge) for hoge in input().split()]:
    ans *= a
if ans > 10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N = int(input())
A = [int(hoge) for hoge in input().split()]
if 0 in A:
    print(0)
else:
    ans = 1
    for a in A:
        ans *= a
        if ans>10**18:
            ans = -1
            break
    print(ans)