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

nmk=input("").split(" ")
n=int(nmk[0])
m=int(nmk[1])
k=int(nmk[2])
listin=[-1]*n
listf=[]
listb=[]
for i in range(n):
    listf+=[[]]
    listb+=[[]]
for i in range(m):
    ab=input("").split(" ")
    a=int(ab[0])-1
    b=int(ab[1])-1
    listf[a]+=[b]
    listf[b]+=[a]
for i in range(k):
    ab=input("").split(" ")
    a=int(ab[0])-1
    b=int(ab[1])-1
    listb[a]+=[b]
    listb[b]+=[a]
s=-1
listff=[]

for i in range(n):
    if(listin[i]==-1):
        s+=1
        listin[i]=s
        listff+=[[i]]
        cnt=0
        
        while(len(listff[s])>cnt):
            for ii in listf[listff[s][cnt]]:
                if(listin[ii]==-1):
                    listin[ii]=s
                    listff[s]+=[ii]
                    
            cnt+=1
listans=[]

for i in range(n):
    
    listans+=[str(len(set(listff[listin[i]])-set(listb[i]))-1-len(listf[i]))]
print(" ".join(listans))

    



    
    


### FIXED CODE ###

import numpy as np
from scipy.sparse.csgraph import connected_components
from scipy.sparse import csr_matrix

import sys
sys.setrecursionlimit(10**9)
n,m,k=[int(i) for i in input().split()]
frends_num=[0 for i in range(n)]
def make_frends(m,n):
    data=[1 for i in range(m)]

    row=[]
    col=[]
    for k in range(m):
        i,j=[int(l) for l in input().split()]
        new_i=min(i,j)-1
        new_j=max(i,j)-1
        row.append(new_i)
        col.append(new_j)
        frends_num[new_i]+=1
        frends_num[new_j]+=1
    frend_sparce_matrix=csr_matrix((data, (row, col)),shape=(n,n))
    return frend_sparce_matrix


frends=make_frends(m,n)
l,labels=connected_components(frends)
labels
labels=list(labels)

class Group:
    def __init__(self,labels):
        self.labels=labels
        self.group_num=[0 for i in range(l)]
        for i in labels:
            self.group_num[i]+=1
    def get_group_num(self,i):
        return self.group_num[self.labels[i]]

group=Group(labels)


def get_frend_num(i):
    return frends_num[i]


def make_block(k,n):
    block_num=[0 for i in range(n)]
    for p in range(k):
        i,j =[int(l)-1 for l in input().split()]
        new_i=min(i,j)
        new_j=max(i,j)
        if labels[new_i]==labels[new_j]:
            block_num[i]+=1
            block_num[j]+=1
    return block_num

block=make_block(k,n)

def get_block_num(i):
    return block[i]

ans=[]
for i in range(n):
    ans.append(str(group.get_group_num(i)-1-get_frend_num(i)-get_block_num(i)))
print(" ".join(ans))
### BUGGY CODE ###

x, y = map(int, input().split())

cnt = 0
t = x
while True:
    if t * y > 0:
        if t > 0:
            if t < y:
                t += 1
                cnt += 1
            elif y < t:
                t *= (-1)
                cnt += 1
        elif t < 0:
            if abs(t) <= abs(y):
                t *= (-1)
                cnt += 1
            elif abs(t) > abs(y):
                t += 1
                cnt += 1
    elif t * y < 0:
        if t > 0:
            if abs(t) >= abs(y):
                t *= (-1)
                cnt += 1
            elif abs(t) < abs(y):
                t += 1
                cnt += 1
        elif t < 0:
            if abs(t) <= abs(y):
                t *= (-1)
                cnt += 1
            elif abs(t) > abs(y):
                t += 1
                cnt += 1
    else:
        #t * y == 0 
        if t == 0:
            if t < y:
                t += 1
                cnt += 1
            elif y < t:
                t += 1
                cnt += 1
        elif y == 0:
            if t < y:
                t += 1
                cnt += 1
            elif y < t:
                t *= (-1)
                cnt += 1
    if t == y:
        break
print(cnt)    

### FIXED CODE ###

x, y = map(int, input().split())

cnt = 0
t = x
while True:
    if t > 0:
        if y >= 0:
            if t < y:
                cnt += y - t
                break
            elif t == y:
                break
            else:
                #t > y
                cnt += 1
                t *= (-1)               
        else:
            #y < 0
            #t > y
            if abs(t) >= abs(y):
                t *= (-1)
                cnt += 1
            else:
                #abs(t) < abs(y)
                cnt += (-1) * y - t
                t = (-1) * y
    elif t == 0:
        if y > 0:
            #t < y
            cnt += y - t
            break
        elif y == 0:
            #t == y
            break
        else:
            #y < 0
            #y < t
            #abs(t) < abs(y)
            cnt += (-1) * y - t
            t = (-1) * y
    else:
        #t < 0
        if y >= 0:
            #t < y
            if abs(t) <= abs(y):
                t *= (-1)
                cnt += 1
            else:
                #abs(t) > abs(y)
                cnt += (-1) * y - t
                t = (-1) * y
        else:
            #y < 0
            if t < y:
                cnt += y - t
                break
            elif t == y:
                break
            else:
                #t > y
                cnt += 1
                t *= (-1)
print(cnt)
### BUGGY CODE ###

import bisect
import itertools

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

cnt = 0

for v in itertools.combinations(L, 3):
    a = int(v[0])
    b = int(v[1])
    c = int(v[2])

    if a < b + c and b < a + c and c < a + b:
        cnt += 1
print(cnt)




### FIXED CODE ###

import bisect
N = int(input())
L = sorted(map(int, input().split()))

cnt = 0
for i in range(N-2):
    for j in range(i+1, N-1):
        ab = L[i] + L[j]
        c_index = bisect.bisect_left(L, ab)
        cnt += c_index - 1 - j
print(cnt)
### BUGGY CODE ###

import sys
import math
if sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd


def inv(x, mod):
    return pow(x, mod-2, mod)


def lcm(arr, mod = 10 ** 9 + 7):
    ret = 1
    for a in arr:
        ret = ret * a // gcd(ret, a)
    return ret

mod = 10 ** 9 + 7

N = int(input())
A = [int(x) for x in input().split()]
a = lcm(A)
print(sum(a // x % mod for x in A) % mod)


### FIXED CODE ###

import sys
import math
if sys.version_info.minor >= 5:
    from math import gcd
else:
    from fractions import gcd


def inv(x, mod):
    return pow(x, mod-2, mod)


def lcm(arr, mod = 10 ** 9 + 7):
    ret = 1
    for a in arr:
        ret = ret * a // gcd(ret, a)
    return ret

mod = 10 ** 9 + 7

N = int(input())
A = [int(x) for x in input().split()]
a = lcm(A)
print(sum(a * inv(x, mod) for x in A) % mod)
### BUGGY CODE ###

def main():

    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort(reverse = True)
    F.sort()

    if K >= sum(A): return 0

    B = [A[i] * F[i] for i in range(N)]
    l, r = 0, max(B)
    ans = float('inf')
    while l <= r:
        m = (l+r) // 2
        count = 0
        for i in range(N):
            if B[i] - m > 0:
                count += (B[i] - m) // F[i]
                if (B[i] - m) % F[i] != 0:
                    count += 1
        if count <= K:
            ans = min(ans, m)
            if r == m-1: break
            r = m-1
        else:
            if l == m+1: break
            l = m+1
        # print(l, r)
    return ans

if __name__ == '__main__':
    print(main())

### FIXED CODE ###

def main():
 
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    F = list(map(int, input().split()))
    A.sort(reverse = True)
    F.sort()
 
    if K >= sum(A): return 0
 
    B = [A[i] * F[i] for i in range(N)]
    l, r = 0, max(B)
    ans = float('inf')
    while l <= r:
        m = (l+r) // 2
        count = 0
        for i in range(N):
            if B[i] - m > 0:
                count += (B[i] - m) // F[i]
                if (B[i] - m) % F[i] != 0:
                    count += 1
        if count <= K:
            ans = min(ans, m)
            if r == m-1: break
            r = m-1
        else:
            if l == m+1: break
            l = m+1
        # print(l, r)
    return ans
 
if __name__ == '__main__':
    print(main())
### BUGGY CODE ###

from collections import defaultdict
B,W = map(int,input().split())
mod = 10**9+7

fact = [0]*(10**6+1)
fact[0] = 1
for i in range(10**6):
    fact[i+1] = fact[i]*(i+1)%mod

def comb_(n,k):
    return fact[n]*pow(fact[k],mod-2,mod)*pow(fact[n-k],mod-2,mod)*pow(2,(n+1)*(mod-2),mod)%mod

f_B = defaultdict(lambda:pow(2,mod-2,mod))
f_W = defaultdict(lambda:pow(2,mod-2,mod))
g = defaultdict(lambda:pow(2,W*(mod-2),mod))

for i in range(B,B+W):
    f_B[i+1] = f_B[i]-comb_(i-1,B-1)*pow(2,mod-2,mod)
    f_B[i+1] %= mod

for i in range(W,B+W):
    f_W[i+1] = f_W[i]-comb_(i-1,W-1)*pow(2,mod-2,mod)
    f_W[i+1] %= mod

for i in range(W+1,B+W):
    g[i+1] = g[i] + comb_(i-1,W-1)
    g[i+1] %= mod

for i in range(1,B+W+1):
    if i < W+1:
        print(f_B[i])
    else:
        print((f_B[i]+f_W[i]+g[i]-pow(2,mod-2,mod))%mod)



### FIXED CODE ###

from collections import defaultdict
B,W = map(int,input().split())
mod = 10**9+7

fact = [0]*(10**6+1)
fact[0] = 1
for i in range(10**6):
    fact[i+1] = fact[i]*(i+1)%mod

def comb_(n,k):
    return fact[n]*pow(fact[k],mod-2,mod)*pow(fact[n-k],mod-2,mod)*pow(2,(n+1)*(mod-2),mod)%mod

f_B = defaultdict(lambda:pow(2,mod-2,mod))
f_W = defaultdict(lambda:pow(2,mod-2,mod))
g = defaultdict(lambda:pow(2,W*(mod-2),mod))

for i in range(B,B+W):
    f_B[i+1] = f_B[i]-comb_(i-1,B-1)*pow(2,mod-2,mod)
    f_B[i+1] %= mod

for i in range(W,B+W):
    f_W[i+1] = f_W[i]-comb_(i-1,W-1)*pow(2,mod-2,mod)
    f_W[i+1] %= mod

for i in range(W+1,B+W):
    g[i+1] = g[i] + comb_(i-1,W-1)
    g[i+1] %= mod

for i in range(1,B+W+1):
    if i < W+1:
        print(f_B[i])
    else:
        print((f_B[i]+f_W[i]+g[i]-pow(2,mod-2,mod))%mod)
### BUGGY CODE ###

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

hdic = {}
wdic = {}
hws_h = {}
hws_w = {}

for m in range(M):
    h, w = map(int, input().split())
    if h in hdic.keys():
        hdic[h] += 1
        hws_h[h].append(w)
    else:
        hdic[h] = 1
        hws_h[h] = [w]
    
    if w in wdic.keys():
        wdic[w] += 1
        hws_w[w].append(h)
    else:
        wdic[w] = 1
        hws_w[w] = [h]

hmax = max(hdic.values())
wmax = max(wdic.values())

hs = []
ws = []

hs = [k for k, v in hdic.items() if v==hmax]
ws = [k for k, v in wdic.items() if v==wmax]

f = 1

if len(hs) < len(ws):
    for h in hs:
        wlist = hws_h[h]
        for w in ws:
            if w not in wlist:
                f = 0
                break
        if f == 0:
            break

else:
    for w in ws:
        hlist = hws_w[w]
        for h in hs:
            if h not in hlist:
                f = 0
                break
        if f == 0:
            break

print(hmax + wmax - f)


### FIXED CODE ###

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

hdic = {}
wdic = {}
hws_h = {}
hws_w = {}

for m in range(M):
    h, w = map(int, input().split())
    if h in hdic.keys():
        hdic[h] += 1
        hws_h[h].append(w)
    else:
        hdic[h] = 1
        hws_h[h] = [w]
    
    if w in wdic.keys():
        wdic[w] += 1
        hws_w[w].append(h)
    else:
        wdic[w] = 1
        hws_w[w] = [h]

hmax = max(hdic.values())
wmax = max(wdic.values())

hs = []
ws = []

hs = [k for k, v in hdic.items() if v==hmax]
ws = [k for k, v in wdic.items() if v==wmax]

f = 1

if len(ws) < len(hs):
    for h in hs:
        wlist = hws_h[h]
        for w in ws:
            if w not in wlist:
                f = 0
                break
        if f == 0:
            break
        
else:
    for w in ws:
        hlist = hws_w[w]
        for h in hs:
            if h not in hlist:
                f = 0
                break
        if f == 0:
            break

print(hmax + wmax - f)
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline())
L = tuple([int(x) for x in sys.stdin.readline().split()])

def tri_able(x, y, z):
    if x+y > z and y+z > x and z+x > y:
        return 1
    else:
        return 0

answer = 0

for i in range(len(L)-2):
    for j in range(i+1, len(L)-1):
        for k in range(j+1,len(L)):
            answer += tri_able(L[i], L[j], L[k])
print(answer)


### FIXED CODE ###

import sys
import bisect

N = int(sys.stdin.readline())
L = [int(x) for x in sys.stdin.readline().split()]
L.sort()

answer = 0

for i in range(len(L)-2):
    for j in range(i+1, len(L)-1):
        answer += bisect.bisect_left(L, L[i]+L[j])-j-1

print(answer)
### BUGGY CODE ###

import numpy as np
n,k = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [(10**4)*(10**5)]*n
dp[0]=0
for i in range(n-1):
     for j in range(1,k+1):
            if i+j>n-1: break
            dp[i+j] = min(dp[i+j],dp[i]+np.abs(h[i]-h[i+j]))
print(dp[n-1]) 

### FIXED CODE ###

n,k = map(int, input().split())
h = [int(i) for i in input().split()]
dp = [(10**4)*(10**5)]*n
dp[0]=0
for i in range(n-1):
    loop = min(k+1,n-i)
    for j in range(1,loop):
        dp[i+j] = min(dp[i+j],dp[i]+abs(h[i]-h[i+j])) 
print(dp[n-1])
### BUGGY CODE ###

Q = int(input())
Start = []
End = []
for _ in range(Q):
    l, r = map(int, input().split())
    Start.append(l)
    End.append(r)

e = max(End)


def primes(n):
    ass = set([])
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.add(i)
    return ass


def like_primes(n):
    A = [0]* (e+1)
    for i in n:
        if (i + 1) // 2 in n:
            A[i] = 1
    return A


A = like_primes(primes(e))
for i in range(Q):
    print(A[Start[i]:End[i]+1].count(1))


### FIXED CODE ###

Q = int(input())
Start = []
End = []
for _ in range(Q):
    l, r = map(int, input().split())
    Start.append(l)
    End.append(r)

e = max(End)


def primes(n):
    ass = set([])
    is_prime = [True] * (n + 1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5) + 1):
        if not is_prime[i]:
            continue
        for j in range(i * 2, n + 1, i):
            is_prime[j] = False
    for i in range(len(is_prime)):
        if is_prime[i]:
            ass.add(i)
    return ass


def like_primes(n):
    A = [0] * (e+2)
    for i in range(1, e+2):
        if (i in n) and ((i + 1) // 2 in n):
            A[i] = A[i-1] + 1
        else:
            A[i] = A[i-1]
    return A


A = like_primes(primes(e))
for i in range(Q):
    print(A[End[i]] - A[Start[i]-1])
### BUGGY CODE ###

A,B,K = map(int,input().split())
li = []
for i in range(A,B+1):
    if abs(A-i)<K:
        li.append(i)
    elif abs(B-i)<K:
        li.append(i)
li.sort()
for j in range(len(li)):
    print(li[j])

### FIXED CODE ###

A,B,K=map(int,input().split())
li=range(A,B+1)
ans=sorted(set(li[:K])|set(li[-K:]))
for i in ans:
    print(i)
### BUGGY CODE ###


s = input()
n = int(input())

flag = 0
for i in range(n):
    Q = input()
    if int(Q[0]) == 2:
        F = int(Q[2])
        C = Q[4]
        #print(F, C)
        if (F + flag) % 2 == 1:
            s = C + s
        else:
            s = s + C
    else:
        flag = (flag + 1) % 2 

print(s if flag == 0 else s[::-1])


### FIXED CODE ###


s = list(input())
n = int(input())

flag = 0
s1 = []
s2 = s
for i in range(n):
    Q = input()
    if Q[0] == "2":
        if Q[2] == "1":
            if flag == 1:
                s2.append(Q[4])
            else:
                s1.append(Q[4])
        else:
            if flag == 0:
                s2.append(Q[4])
            else:
                s1.append(Q[4])
    else:
        flag ^= 1
s2 = s1[::-1] + s2
print("".join(s2) if flag == 0 else "".join(s2[::-1]))
### BUGGY CODE ###

from collections import deque

N, X, Y = map(int, input().split())

graph = [[] for _ in range(N)]

for i in range(N - 1):
    graph[i].append(i + 1)
    graph[i + 1].append(i)

graph[X - 1].append(Y - 1)
graph[Y - 1].append(X - 1)

# print(graph)


def bfs(s):
    q = deque([])
    q.append(s)
    dist[s][s] = 0

    while q:
        x = q.popleft()

        for nx in graph[x]:
            if dist[s][nx] != 0:
                continue
            else:
                dist[s][nx] = dist[s][x] + 1
                q.append(nx)


inf = 10 ** 9

dist = [[0] * N for _ in range(N)]

dist_lis = [0] * N

for i in range(N):
    bfs(i)

for i in range(N):
    for j in range(i + 1, N):
        dist_lis[dist[i][j]] += 1

# print(dist)
# print(dist_lis)

for i in range(1, N):
    print(dist_lis[i])


### FIXED CODE ###

from collections import deque

N, X, Y = map(int, input().split())

graph = [[] for _ in range(N)]

for i in range(N - 1):
    graph[i].append(i + 1)
    graph[i + 1].append(i)

graph[X - 1].append(Y - 1)
graph[Y - 1].append(X - 1)

# print(graph)


def bfs(s):
    q = deque([])
    q.append(s)
    dist[s][s] = 0

    while q:
        x = q.popleft()

        for nx in graph[x]:
            if dist[s][nx] != 0:
                continue
            else:
                dist[s][nx] = dist[s][x] + 1
                q.append(nx)


inf = 10 ** 9

dist = [[0] * N for _ in range(N)]

dist_lis = [0] * N

for i in range(N):
    bfs(i)

for i in range(N):
    for j in range(i + 1, N):
        dist_lis[dist[i][j]] += 1

# print(dist)
# print(dist_lis)

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

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from pprint import pprint

N, M = map(int, input().split(' '))

A = []
B = []
for i in range(M):
    _a, _b = map(int, input().split(' '))
    A.append(_a)
    B.append(_b)

room_connection = [[] for n in range(N)]

for a, b in zip(A, B):
    room_connection[a - 1].append(b - 1)
    room_connection[b - 1].append(a - 1)

room_depth = [None] * N
room_depth[0] = 0
room_sign = [None] * N

stack = [0]
visited = []

# pprint(room_connection)

while stack:
    now = stack.pop()
    next_room = [r for r in room_connection[now] if r not in visited]
    # print('now=', now)
    # print('next_room', next_room)

    for r in next_room:
        if r not in visited or r not in stack:
            stack.append(r)

        if room_depth[r] is None or room_depth[r] > room_depth[now] + 1:
            room_depth[r] = room_depth[now] + 1
            room_sign[r] = now + 1

    visited.append(now)

    if set(visited) == set(range(N)):
        break


    # print('visited', visited)
    # print('depth', room_depth)
    # print('stack', stack)
    # print('sign', room_sign)
    # print('-----')

print('Yes')
for s in room_sign[1:]:
    print(s)

### FIXED CODE ###

# https://atcoder.jp/contests/abc168/tasks/abc168_d
from collections import deque

N, M = map(int, input().split(' '))

A = []
B = []

# 隣接リスト
route2 = [[] for n in range(N)]

for i in range(M):
    a, b = map(int, input().split(' '))
    A.append(a)
    B.append(b)

for a, b in zip(A, B):
    route2[a - 1].append(b - 1)
    route2[b - 1].append(a - 1)

room_sign = [None] * N

queue = deque([])
visited = set()

queue.append(0)
visited.add(0)

while len(queue) > 0:
    now = queue.popleft()
    for i in route2[now]:
        if i not in visited:
            queue.append(i)
            visited.add(i)

            room_sign[i] = now + 1

print('Yes')
for s in room_sign[1:]:
    print(s)
### BUGGY CODE ###


A = []

def update(i, x):
    A[i] = x

def find(s, t):
    return min(A[s:t+1])

if __name__ == "__main__":
    n, q = map(int, input().split())
    A = [2**31 - 1] * n 
    for i in range(q):
        com, x, y = map(int, input().split())
        if com == 0:
            update(x, y)
        else:
            m = find(x, y)
            print(m)



### FIXED CODE ###

import sys

INF = 2**31 - 1


class RMQ:

    def __init__(self, n):
        tmp = 1
        while tmp < n:
            tmp *= 2
        self.n = tmp * 2 - 1
        self.A = [INF] * (2 * self.n - 1)

    def update(self, i, x):
        i = self.n // 2 + i
        self.A[i] = x
        while i:
            i = (i - 1) // 2
            self.A[i] = min(self.A[i * 2 + 1], self.A[i * 2 + 2])

    def find(self, a, b, k, l, r):
        if r < a or b < l:
            return INF
        if a <= l and r <= b:
            return self.A[k]
        vl = self.find(a, b, k * 2 + 1, l, (l + r) // 2)
        vr = self.find(a, b, k * 2 + 2, (l + r) // 2 + 1, r)
        return min(vl, vr)


line = sys.stdin.readline()
n, q = map(int, line.split())
t = RMQ(n)
for i in range(q):
    line = sys.stdin.readline()
    com, x, y = map(int, line.split())
    if com == 0:
        t.update(x, y)
    else:
        print(t.find(x, y, 0, 0, t.n // 2))
### BUGGY CODE ###

#解説読んだ

import math

N, L = list(map(int, input().split()))
T = [int(input()) for _ in range(N)]

x, y = 0, 0
for i in range(N - 1):
  for j in range(i + 1, N):
    a = (T[i] + T[j]) / 2
    b = a + L / 2
    t = j - i - 1
    k = N - 2 - t
    x += k * math.cos(2 * math.pi * a / L)
    x += t * math.cos(2 * math.pi * b / L)
    y += k * math.sin(2 * math.pi * a / L)
    y += t * math.sin(2 * math.pi * b / L)
x /= N * (N - 1) * (N - 2) / 3 / 2
y /= N * (N - 1) * (N - 2) / 3 / 2
print(x, y)

### FIXED CODE ###

#解説読んだ

import math

N, L = list(map(int, input().split()))
T = [int(input()) for _ in range(N)]

K = N * (N - 1) * (N - 2) / 3 / 2
x, y = 0, 0
for i in range(N - 1):
  for j in range(i + 1, N):
    a = (T[i] + T[j]) / 2
    b = a + L / 2
    t = j - i - 1
    k = N - 2 - t
    x += k * math.cos(2 * math.pi * a / L) / K
    x += t * math.cos(2 * math.pi * b / L) / K
    y += k * math.sin(2 * math.pi * a / L) / K
    y += t * math.sin(2 * math.pi * b / L) / K
print(x, y)
### BUGGY CODE ###

def main():
    n = int(input())
    a = list(map(int,input().split()))
    mod = 10**9+7
    div = {}
    for i in range(n):
        c = 0
        while a[i]>0:
            if a[i]%2==1:
                if c not in div.keys():
                    div[c] = 1
                else:
                    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 = int(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 ###

def main():
    import sys
    n = int(input())
    a = list(map(int, input().split()))

    try:
        if a.index(0):
            print(0)
            sys.exit()
    except ValueError:
        pass

    ans = 1
    for i in range(n):
        ans *= a[i]
        if ans > 10 ** 18:
            print(-1)
            sys.exit()

    print(ans)


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

from collections import deque

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

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

gcd_max=1

import functools
import math

for i in range(N):
    a = A.popleft()
    gcd_max = max(gcd_max, functools.reduce(gcd, A))
    A.append(a)

print(gcd_max)


### FIXED CODE ###

from collections import deque
from copy import copy
from array import array

def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a

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

def get_prefix_gcd_list(Adeque):
    prefix_gcd = array('i', [0]*N)
    # marker
    prefix_gcd[0] = 0
    # the first itself is gcd
    prefix_gcd[1] = Adeque.popleft()
    for i in range(2,N):
        a = Adeque.popleft()
        prefix_gcd[i] = gcd(prefix_gcd[i-1], a)
        pass
    return prefix_gcd
        
    
# PREFIX_GCD[i]...i より前の要素のGCD
PREFIX_GCD = get_prefix_gcd_list(deque(copy(A)))

# PREFIX_GCD[i]...i より後の要素のGCD
POSTFIX_GCD=list(reversed(get_prefix_gcd_list(deque(reversed(A)))))

gcd_max=1

for i in range(N):
    pre = PREFIX_GCD[i]
    pos = POSTFIX_GCD[i]
    if pre == 0:
        _gcd = pos
    elif pos == 0:
        _gcd = pre
    else:
        _gcd = gcd(pre,pos)
    gcd_max = max(gcd_max, _gcd)
        
print(gcd_max)