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

from scipy.sparse.csgraph import minimum_spanning_tree
import sys
input = sys.stdin.readline
def solve():
  n = int(input())
  D = [[0]*n for _ in range(n)]
  xquery = []
  yquery = []
  for i in range(n):
    x,y = (int(i) for i in input().split())
    xquery.append((x,y,i))
    yquery.append((y,x,i))
  xquery.sort()
  yquery.sort()
  for i in range(n-1):
    tx,ty,place = xquery[i]
    tx2,ty2,place2 = xquery[i+1]
    cost = min(abs(tx2-tx),abs(ty2-ty))
    D[place][place2] = cost

    
    tx,ty,place = yquery[i]
    tx2,ty2,place2 = yquery[i+1]
    cost = min(abs(tx2-tx),abs(ty2-ty))
    D[place][place2] = cost
    
  D = minimum_spanning_tree(D)
  print(int(D.sum()))
solve()

### FIXED CODE ###

import heapq
import sys
input = sys.stdin.readline
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    def same_check(self, x, y):
        return self.find(x) == self.find(y)

def solve():
  n = int(input())
  query = []
  xquery = []
  yquery = []
  for i in range(n):
    x,y = (int(i) for i in input().split())
    xquery.append((x,y,i))
    yquery.append((y,x,i))
  xquery.sort()
  yquery.sort()
  for i in range(n-1):
    tx,ty,place = xquery[i]
    tx2,ty2,place2 = xquery[i+1]
    cost = min(abs(tx2-tx),abs(ty2-ty))
    if place > place2:
      place,place2 = place2,place
    heapq.heappush(query,(cost,place,place2))
    
    ty,tx,place = yquery[i]
    ty2,tx2,place2 = yquery[i+1]
    cost = min(abs(tx2-tx),abs(ty2-ty))
    if place > place2:
      place,place2 = place2,place
    heapq.heappush(query,(cost,place,place2))
  ct = 0
  uf = UnionFind(n)

  while len(query) > 0:
    cost,place1,place2 = heapq.heappop(query)
    if uf.same_check(place1,place2):
      continue
    else:
      uf.union(int(place1),int(place2))
      ct += cost
  print(ct)
      

solve()
### BUGGY CODE ###

import sys
readline = sys.stdin.buffer.readline

def main():
    def digit_dp(n, m):
        # dp[i][j][k] -> i: 現在見ている桁数
        #                j: n以下が保証されているかどうか
        #                k: m で割った余りの総和
        n = list(map(int, list(str(n))))
        n_len = len(n)
        dp_table = [[[0 for k in range(m)] for j in range(2)] for i in range(n_len + 1)]
        dp_table[0][0][0] = 1

        for i in range(n_len):
            for j in range(2):
                for k in range(m):
                    for d in range(0, 10 if j else n[i] + 1):
                        dp_table[i + 1][j or (d < n[i])][(k + d) % m] += dp_table[i][j][k]

        return dp_table[-1][0][0] + dp_table[-1][1][0] - 1
        #0 の分、1を減算


    a = int(readline())
    b = int(readline())
    mod = 10**9 + 7
    print(digit_dp(a, b) % mod)

if __name__ == "__main__":
    main()


### FIXED CODE ###

k = str(input())
d = int(input())

DP = [[[0 for _ in range(d)] for _ in range(2)] for _ in range(len(k)+1)]
DP[0][0][0] = 1

for i in range(len(k)):
    now = int(k[i])
    for j in range(2):
        for mod in range(d):
            for n in range(10):
                # 対象の数字未満が確定する場合
                if j==1 or (j==0 and n < now):
                    next_j = 1
                # 対象の数字とこの桁まで同じ場合
                elif n == now:
                    next_j = 0
                # 対象の数字よりも大きな値の場合
                else: 
                    continue

                n_mod = n % d
                next_mod = (mod + n_mod) % d
                DP[i+1][next_j][next_mod] = (DP[i+1][next_j][next_mod] + DP[i][j][mod]) % (10**9+7)

ans = (DP[len(k)][0][0] + DP[len(k)][1][0] -1) % (10**9+7)
print(ans)
# print(DP)
### BUGGY CODE ###

def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    ss = map(int, s)
    if 10%p == 0:
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    num = int(s)
    tens = 10**(n-1)
    for i, si in enumerate(ss):
        v = num%p
        mu[i] = v
        c[v] += 1
        num -= si*tens
        tens //= 10
    c[0] += 1
    for i in mu:
        c[i] -= 1
        ans += c[i]
        
    print(ans)
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    n, p = map(int, input().split())
    s = input()
    mu = [None]*n
    ans = 0
    c = [0]*p
    if 10%p == 0:
        ss = map(int, s)
        ss = list(ss)
        for i in range(n):
            if ss[i]%p == 0:
                ans += i+1
        print(ans)
        return
    sr = s[::-1]
    ssr = map(int, sr)
    tens = 1
    v = 0
    for i, si in enumerate(ssr):
        v = (v + (si%p)*tens)%p
        mu[i] = v
        c[v] += 1
        tens *= 10
        tens %= p
    c[0] += 1
    for i in c:
        if i:
            ans += ((i-1)*i)//2
        
    print(ans)
    

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

#import numpy as np
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as comb_with
from itertools import permutations as perm


N = int(input())
#H1,M1,H2,M2,K= map(int,input().split())
#A = list(map(int,input().split()))
#B = list(map(int,input().split()))
#S= str(input())
l=[]
for i in range(N):
    B = int(input())
    l.append(B)

for i in l:
    x=l.copy()
    x.remove(i)
    m=max(x)
    print(m)


### FIXED CODE ###

#import numpy as np
#from itertools import combinations as comb
#from itertools import combinations_with_replacement as comb_with
from itertools import permutations as perm


N = int(input())
#H1,M1,H2,M2,K= map(int,input().split())
#A = list(map(int,input().split()))
#B = list(map(int,input().split()))
#S= str(input())
l=[]
for i in range(N):
    B = int(input())
    l.append(B)
m=max(l)
x=l.copy()
x.remove(m)
n=max(x)
for i in l:
    if i!=m:
        print(m)
    else:
        print(n)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

end=[[] for i in range(N+2)]
LIST=set()#更新が必要な座標を選ぶ

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))
    LIST.add(l)
    LIST.add(r)
    LIST.add(r+1)

LIST=sorted(LIST)

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値

def updates(a,b,x,k,l,r):#区間[a,b)にxを加算
    
    if r<=a or b<=l:#区間[a,b)が対象区間の外にあれば終了
        return
    
    if a<=l and r<=b:
        ADD[k]+=x#そのノードのADD値を更新
        return
    
    updates(a,b,x,k*2+1,l,(l+r)//2)#それ以外のときは,SEG[k*2+1]とSEG[k*2+2]で場合分け
    updates(a,b,x,k*2+2,(l+r)//2,r)

    SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def update_solo(n,x,seg_el):#A[n]=xに更新（反映）
    i=n+seg_el-1
    SEG[i]=x
    i=(i-1)//2
    
    while i>=0:
        SEG[i]=max(SEG[i*2+1]+ADD[i*2+1],SEG[i*2+2]+ADD[i*2+2])
        i=(i-1)//2

for i in LIST:

    for b,x in end[i]:
        updates(b,i,x,0,0,seg_el)#点数がもらえる区間から出たときにその分を加算

    update_solo(i,SEG[0]+ADD[0],seg_el)#[0,i)の最大値はSEG[0]+ADD[0]と一致するはず

print(SEG[0]+ADD[0])

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

end=[[] for i in range(N+2)]

for i in [0]*M:
    l,r,a=map(int,input().split())
    end[r+1].append((l,a))

#Starry Sky tree
seg_el=1<<18#Segment treeの台の要素数

SEG=[0]*(2*seg_el-1)#Segment tree.色々考えると0で初期化してOKそう
ADD=[0]*(2*seg_el-1)#加算用Segment tree,SEG[k]+ADD[k]がkにおける本当の最大値
seg_el_list=[524286, 262142, 131070, 65534, 32766, 16382, 8190, 4094, 2046, 1022, 510, 254, 126, 62, 30, 14, 6, 2, 0]

def update(k):#SEGのkより上のノードを更新（反映）
    while k>=0:
        k=(k-1)//2
        if SEG[k]==max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2]):
            break
        SEG[k]=max(SEG[k*2+1]+ADD[k*2+1],SEG[k*2+2]+ADD[k*2+2])

def to_seg(a):#aが終点となる区間をSegment treeの座標へ変換  
    b=(a&(-a)).bit_length()
    return seg_el_list[b]+a//(1<<(b-1))

def add(a,b,x):#区間(a,b]にxを加算
    #print(a,b,x)
    while b!=0:
        ADD[to_seg(b)]+=x
        update(to_seg(b))
        b-=(b&(-b))

    while a!=0:
        ADD[to_seg(a)]+=-x
        update(to_seg(a))
        a-=(a&(-a))
    
for i in range(N+2):
    for b,k in end[i]:
        add(b,i,k)#点数がもらえる区間から出たときにその分を加算

    SEG[i+seg_el-1]=SEG[0]
    update(i+seg_el-1)

print(SEG[0])
### BUGGY CODE ###

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

dp = [[0]+[float('inf')]*100000 for _ in range(N+1)]

for i in range(1, N+1):
    for v in range(0, 100001):
        weight = WV[i-1][0]
        value = WV[i-1][1]
        dp[i][v] = min(dp[i-1][v], dp[i-1][v-value]+weight)
res = 0
for v, w in enumerate(dp[-1]):
    if w <= W: res = v

print(res)


### FIXED CODE ###

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

dp = [[0]+[float('inf')]*100000 for _ in range(N+1)]

for i in range(1, N+1):
    for v in range(0, 100001):
        weight = WV[i-1][0]
        value = WV[i-1][1]
        dp[i][v] = min(dp[i-1][v], dp[i-1][v-value]+weight)
res = 0
for v, w in enumerate(dp[-1]):
    if w <= W: res = v

print(res)
### BUGGY CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
s = input()

r = []
g = []
b = []
for i in range(n):
    if s[i] == "R":
        r.append(i)
    if s[i] == "G":
        g.append(i)
    if s[i] == "B":
        b.append(i)

l = list(itertools.product(r,g,b))

ans = len(l)
for i in range(len(l)):
    ll = sorted(l[i])
    if ll[1] - ll[0] == ll[2] - ll[1]:
        ans -= 1

print(ans)

### FIXED CODE ###

import sys, bisect, math, itertools, string, queue, copy
# import numpy as np
# import scipy
# from collections import Counter,defaultdict,deque
# from itertools import permutations, combinations
# from heapq import heappop, heappush
# from fractions import gcd
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n = inp()
s = input()

r = []
g = []
b = []
for i in range(n):
    if s[i] == "R":
        r.append(i)
    if s[i] == "G":
        g.append(i)
    if s[i] == "B":
        b.append(i)

ans = len(r)*len(g)*len(b)

for i in range(1,n):
    for j in range(n):
        k = j + 2 * i
        if k < n and s[j] != s[j + i] and s[j] != s[j + 2 * i] and s[j + i] != s[j + 2 * i]:
            ans -= 1

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

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

L.sort()

ans = 0
b = 1
c = 2
while b < N-1:
  sub = L[c] - L[b]

  a = 0
  while L[a] <= sub:
    a += 1
    if a >= b:
      b += 1
      c = b
      break
  else:
    ans += b-a
    
  c += 1
  if c >= N:
    b += 1
    c = b + 1

print(ans)

### FIXED CODE ###

N = int(input())
L = list(map(int, input().split()))
 
L.sort()
 
dp = [0]*(1005)
frm = 0
cnt = 0
Lcopy = [1001] + L[::-1]
while Lcopy:
  to = Lcopy.pop()
  for i in range(frm, to):
    dp[i] = cnt
  frm = to
  cnt += 1
  
ans = 0
b = 1
c = 2
while b < N-1:
  sub = L[c] - L[b]

  x = b - dp[sub]
  if x > 0:
    ans += x
  else:
    b += 1
    c = b
    
  c += 1
  if c >= N:
    b += 1
    c = b + 1

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

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
    sum=0
    c=0
    for j in range(n):
        if i==j:
            continue
        else:
            d=abs(c-a[j])
            sum+=d
            c=a[j]
    sum+=abs(c)
    print(sum)


### FIXED CODE ###

n=int(input())
x=list(map(int,input().split()))
a=[]
a.append(0)
for i in range(n):
    a.append(x[i])
a.append(0)
sum=0
for i in range(n+1):
    sum+=abs(a[i]-a[i+1])
for i in range(1,n+1):
    s=abs(a[i-1]-a[i+1])
    s1=abs(a[i-1]-a[i])
    s2=abs(a[i]-a[i+1])
    print(sum+s-(s1+s2))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)
def dfs(G,v,p):
    for nv in G[v]:
        if(nv==p):
            continue
        point[nv]+=point[v]
        dfs(G,nv,v)

N,Q=map(int,input().split())
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
point=[0]*N
for i in range(Q):
    p,x=map(int,input().split())
    point[p-1]+=x
dfs(G,0,-1)
print(*point)

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
def dfs(G,s,p):
    for nv in G[s]:
        if(nv==p):
            continue
        Count[nv]+=Count[s]
        dfs(G,nv,s)
    
N,Q=map(int,input().split())
Count=[0]*N
G=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x:int(x)-1,input().split())
    G[a].append(b)
    G[b].append(a)
for i in range(Q):
    p,x=map(int,input().split())
    Count[p-1]+=x
dfs(G,0,-1)
print(*Count)
### BUGGY CODE ###

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

for i in range(n):
    b.append(a[i])
    b.reverse()

print(' '.join(map(str, b)))

### FIXED CODE ###

n = int(input())
a = input().split()

print(' '.join(a[-1::-2] + a[(n % 2)::2]))
### BUGGY CODE ###

n=int(input())
l=[int(input()) for i in range(n)]
m=max(l)
nums=[i for i in range(n)]
for num in nums:
  if(l[num]==m and l.count(m)==1):
    print(sorted(l)[-2])
  else:
    print(m)


### FIXED CODE ###

n=int(input())
l=[int(input()) for i in range(n)]
s=sorted(l)
p=s[-1]
q=s[-2]
for i in range(n):
  if l[i]==p:
    print(q)
  else:
    print(p)
### BUGGY CODE ###


S=input()
Q=int(input())
lis=[]
for _ in range(Q):
    lis.append(input().split())
ans=S
cnt=0
for i in lis:
    if(int(i[0]) == 1):
        cnt= (cnt+1) % 2
    elif((cnt== 0 and i[1]=='1') or (cnt == 1 and i[1]=='2')):
        ans= i[2] + ans
    else:
        ans+=i[2]

print(ans[::-1]) if(cnt % 2 == 1) else print(ans)   


### FIXED CODE ###

from collections import deque
S=input()
Q=int(input())
ans=deque(S)
cnt=0
for _ in range(Q):
    i=(input().split())
    if(int(i[0]) == 1):
        cnt= (cnt+1) % 2
    elif((cnt== 0 and i[1]=='1') or (cnt == 1 and i[1]=='2')):
        ans.appendleft(i[2])
    else:
        ans.append(i[2])
ans=''.join(ans)
print(ans[::-1]) if(cnt % 2 == 1) else print(ans)
### BUGGY CODE ###

import bisect

n = int(input())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
c.sort()

ans = 0
for i in range(len(b)):
    a_idx = bisect.bisect_left(a, b[i])
    c_idx = bisect.bisect_right(c, b[i])
    l = len(c[c_idx:])
    ans += a_idx * (n - c_idx)
print(ans)


### FIXED CODE ###

import bisect

n = int(input())

a = list(map(int, input().split()))
b = list(map(int, input().split()))
c = list(map(int, input().split()))

a.sort()
c.sort()

ans = 0
for i in range(len(b)):
    a_idx = bisect.bisect_left(a, b[i])
    c_idx = bisect.bisect_right(c, b[i])
    ans += a_idx * (n - c_idx)
print(ans)
### BUGGY CODE ###

n = int(input())
A = input().split(sep=' ')
pro = 1
for el in A:
	pro *= int(el)

if pro > 1e18:
	print(-1)
else:
	print(pro)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
if 0 in A:
    print(0)
else:
    pro = 1;
    ok = True
    for el in A:
        pro *= el
        if(pro > 1e18):
            ok = False
            break

    if ok: print(pro)
    else: print(-1)
### BUGGY CODE ###

mod = 10**9+7
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
d = defaultdict(lambda:0)
ans = 0
for a in A:
    a = bin(a)[2:]
    for i in range(len(a)):
        if a[-i-1]=='1':
            d[i] += 1

for a in A:
    a = (60-len(bin(a))+2)*'0'+bin(a)[2:]
    for i in d:
        if a[-i-1]=='0':
            ans += pow(2,i,mod)*d[i]
        else:
            ans += pow(2,i,mod)*(N-d[i])

ans *= pow(2,mod-2,mod)
ans %= mod
print(ans)

### FIXED CODE ###

mod = 10**9+7
from collections import defaultdict
N = int(input())
A = list(map(int,input().split()))
d = defaultdict(lambda:0)
ans = 0
for a in A:
    a = bin(a)[2:]
    for i in range(len(a)):
        if a[-i-1]=='1':
            d[i] += 1

for i in range(60):
    ans += pow(2,i,mod)*d[i]*(N-d[i])

ans %= mod
print(ans)
### BUGGY CODE ###

import collections

S = input()

list1 = []
result = 0

for i in range(len(S)):
    list1.append(int(S[-i:])%2019)
    
a = collections.Counter(list1)

result += a[0]

val = list(a.values())
for j in range(len(a.values())):
    result += val[j]*(val[j]-1)/2
    
print(int(result))
        
  

### FIXED CODE ###

s = input()[::-1]
counts = [0] * 2019
counts[0] = 1
num, d = 0, 1
result = 0

for i in s:
    num += int(i) * d
    num %= 2019
    d *= 10
    d %= 2019
    counts[num] += 1
    
for cnt in counts:
    result += cnt*(cnt-1)//2
    
print(result)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
# D-Knapsack

'''
3 8
3 30
4 50
5 60
'''

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

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

dp = [[None] * (W+1) for _ in range(N+1)]
dp[0] = [0] * (W+1)
# print(dp)

for i in range(N):
    for j in range(W + 1):
        if j >= w[i]:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
        else:
            dp[i + 1][j] = dp[i][j]

# print(dp)
print(dp[N][W])


### FIXED CODE ###

# -*- coding: utf-8 -*-
# D-Knapsack

'''
3 8
3 30
4 50
5 60
'''

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

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

dp = [[None] * (W+1) for _ in range(N+1)]
dp[0] = [0] * (W+1)
# print(dp)

for i in range(N):
    for j in range(W + 1):
        if j >= w[i]:
            dp[i + 1][j] = max(dp[i][j], dp[i][j - w[i]] + v[i])
        else:
            dp[i + 1][j] = dp[i][j]

# print(dp)
print(dp[N][W])
### BUGGY CODE ###

def BinarySearch(A, n, key):
    left = 0
    right = n
    mid = 0
    while left < right:
        mid = (left+right)/2
        if A[mid] == key:
            return "FOUND"
        elif A[mid] > key:
            right = mid
        else:
            left = mid + 1
    return left

if __name__ == "__main__":
    n = int(raw_input())
    dic = []
    num = 0
    for i in range(n):
        t = raw_input().split()
        if t[0] == "insert":
            point = BinarySearch(dic, num, t[1])
            if point != "FOUND":
                dic.insert(point, t[1])
                num += 1
        if t[0] == "find":
            if(BinarySearch(dic, num, t[1]) == "FOUND"):
                print("yes")
            else:
                print("no")

### FIXED CODE ###

n = input()
table =	set()

for i in range(n):
    com	= raw_input().split()
    if(com[0][0] == "i"):
	table.add(com[1])
    else:
	if com[1] in table:
            print("yes")
	else:
            print("no")
### BUGGY CODE ###

a, b = [int(v) for v in input().split()]

count = 1
div = 3
if a % 2 == 0 and b % 2 == 0:
    count += 1
while a % 2 == 0:
    a //= 2
while b % 2 == 0:
    b //= 2
if a < b:
    a, b = b, a
while b > 1:
    if a % div == 0 and b % div == 0:
        count += 1
    while a % div == 0:
        a //= div
    while b % div == 0:
        b //= div
    div += 2
    if a < b:
        a, b = b, a

print(count)

### FIXED CODE ###

a, b = [int(v) for v in input().split()]

count = 1
div = 3
if a % 2 == 0 and b % 2 == 0:
    count += 1
while a % 2 == 0:
    a //= 2
while b % 2 == 0:
    b //= 2
if a < b:
    a, b = b, a
while b >= div * div:
    if a % div == 0 and b % div == 0:
        count += 1
    while a % div == 0:
        a //= div
    while b % div == 0:
        b //= div
    div += 2
    if a < b:
        a, b = b, a
if b > 1 and a % b == 0:
    count += 1

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

# D
import sys
sys.setrecursionlimit(100000)

hash_no = 10 ** 9 + 7
x, y = map(int, input().split())

counter = 0


def move(x, y, X, Y):
    global counter
    if (X + Y - x - y) % 3 != 0:
        return
    if x > X:
        return
    if y > Y:
        return
    if (x == X) and (y == Y):
        counter += 1
        return
    if Y > 2 * (X - x) + y:
        return
    if Y < (X - x) / 2 + y:
        return

    move(x + 1, y + 2, X, Y)
    move(x + 2, y + 1, X, Y)


move(0, 0, x, y)
print(counter % hash_no)


### FIXED CODE ###

# AtCoder Beginner Contest 145 D - Knight
import sys
from math import factorial

mod = 10 ** 9 + 7

X, Y = map(int, sys.stdin.readline().strip().split())

# 合計の移動回数は Total = X + Y / 3 
# 移動方法は A: (i + 1, j + 2)  B: (i + 2, j + 1) の2通り
# 移動回数は A: 2 * Total - X  B: X - Total 

# 到達不可能であるか判断する
if (X + Y) % 3 != 0:
    print(0)
    sys.exit()

if Y > 2 * X or Y < X * 0.5:
    print(0)
    sys.exit()


Total = (X + Y) // 3
A = Total * 2 - X
B = X - Total

# combination の計算
ans = 1
for i in range(1, Total + 1):
    ans *= i
    ans %= mod

ans = ans * pow(factorial(A), mod - 2, mod)
ans = ans * pow(factorial(B), mod - 2, mod)

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

a,b,n = map(int,input().split())
#(a*x)//b - a*(x//b) の最大値を求める
ax_list = [a*i for i in range(1,n+1)]
if b > n:
    # ax//b だけ考えればいい
    print(a*n//b)
else:
    # ax//b か　bより大きいx で探す
    x = 2*b-1
    print(a*(b-1)//b if a*(b-1)//b >= (a*x)//b-a*(x//b) else (a*x)//b-a*(x//b))

### FIXED CODE ###

a,b,n = map(int,input().split())
#(a*x)//b - a*(x//b) の最大値を求める
if b > n:
    # ax//b だけ考えればいい
    print(a*n//b)
else:
    # ax//b か　bより大きいx で探す
    x = 2*b-1
    first = a*(b-1)//b
    second = (a*x)//b - a*(x//b)
    print(first if first >= second else second)
### BUGGY CODE ###

import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
ba = np.array([[int(j) for j in list(format(i,'b').zfill(60))] for i in a]).T
mod = 10**9+7

#2^iをmodで割った余りを出しておく
twos = [1]
for i in range(1,60):
    twos.append((twos[i-1]*2)%mod)

#各baのbitごとに0の個数を求める
c0 = np.sum(ba, axis=1)

#答えは各bitごとの(0の数)*(1の数)より求まる
ans = 0
for i in range(60):
    ans += (((c0[59-i]*(n-c0[59-i]))%mod)*twos[i])%mod

ans %= mod
print(int(ans))


### FIXED CODE ###

import numpy as np
n = int(input())
a = np.array(input().split(),dtype=int)
mod = 10**9+7

twos = 1
ans = 0
for i in range(0,60):
    cou1 = np.count_nonzero((a >> i) & 1)
    ans += (cou1*(n-cou1)*twos)%mod
    twos = (twos*2)%mod

ans %= mod
print(ans)